RandomAccess接口里，JDK自带的说明有点奇怪

无意中在RandomAccess接口里，看到JDK自带的说明有如下一段

It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice.Such a List implementation should generally implement this interface. As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:

     for (int i=0, n=list.size(); i < n; i++)
         list.get(i);

runs faster than this loop:
     for (Iterator i=list.iterator(); i.hasNext(); )
         i.next();

这段话的意思，难道遍历List for 循环遍历 要比 get 更比Iterator 更快？

凭直觉应该是 Iterator 更快吧。

说到随机访问的话，HashMap 应该更多地进行随机访问吧，可JDK 里偏偏 HashMap 没有实现 RandomAcess接口

我觉得你没有看懂这段英文。。

E文不过关,特地去看了中文的API.
------------------------------------

java.util
接口 RandomAccess

所有已知实现类：
ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector

public interface RandomAccessList 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。

将操作随机访问列表的最佳算法（如 ArrayList）应用到连续访问列表（如 LinkedList）时，可产生二次项的行为。如果将某个算法应用到连续访问列表，那么在应用可能提供较差性能的算法前，鼓励使用一般的列表算法检查给定列表是否为此接口的一个 instanceof，如果需要保证可接受的性能，还可以更改其行为。

现在已经认识到，随机和连续访问之间的区别通常是模糊的。例如，如果列表很大时，某些 List 实现提供渐进的线性访问时间，但实际上是固定的访问时间。这样的 List 实现通常应该实现此接口。实际经验证明，如果是下列情况，则 List 实现应该实现此接口，即对于典型的类实例而言，此循环：

     for (int i=0, n=list.size(); i < n; i++)
         list.get(i);
的运行速度要快于以下循环：
     for (Iterator i=list.iterator(); i.hasNext(); )
         i.next();
此接口是 Java Collections Framework 的成员。


------------------------

看来是指某些集合, 当随机访问,即 list.get(index) 算法实现上,性能比顺序访问 即 Iterator.next() 更快. 那么应当继承此接口.

而 LZ 所说的.
HashMap 是hash 表.不是链表或者线性表,不属于这个范围的.

Map的遍历其实是 Set<Map.Entry<K, V>> ,而 Set 集合看起来不属于上面所说的情况.

so...

hash表啊神马的,在尚未毕业的时候都丢干净了, 幸好年前偶然看了下数据结构的书,隐约回忆起一些东西. 如果有错请轻拍.......

看中文API 更头大，像机翻的一样。

网上找着答案了：

http://stackoverflow.com/questions/10173375/does-hashmap-use-random-access

HashMap 的 key-value 对 是以 Entry 的形式存储在一个数组中的。而数组本身其实实现了数组自身的 Random Access 逻辑。

顺便查看了HashMap 的源码，
1、HashMap 在用 key 找 value 时， 算出 key 的 hashcode 之后，用 key 的 hashcode 与 entrytable 的当前size 求  & 操作，找到对应的 index。
2、再用数组操作找到同 hashcode 的 Entry 链。（此处应当运用了数组自带的 random access）
3、在Entry 链中找到 与 key  == 或 equal 的 Entry返回 value

The primary
* purpose of this interface is to allow generic algorithms to alter their
* behavior to provide good performance when applied to either random or
* sequential access lists

主要是为随机或顺序访问线性表搞的
你说hashmap与list本身存储方式就不一样，没得比

是的，我原以为 Collections 存储方式都基本一样，结果HashMap 是如下结构

[entry, entry, entry, null, entry, entry, null, entry ]
         |
         .next
         |
         entry
         |
         .next
         |
         entry

======================
values bucket