java2集合框架的一些个人分析和理解(二)

LinkedList我们知道内部结构是个线性链表，首先看它继承的不是AbstractList，而是继承自AbstractSequentialList，这是AbstractList的子类，实现了线性链表的骨架方法，如get/set，均是通过ListIterator迭代器来遍历实现。为什么要创造出AbstractSequentialList这个类？因为线性的不只有链表，但线性的都只有通过迭代器才能找到元素，与之对应的是随机读取——也就是数组，因此在AbstractSequentialList的类注释里明确说明：如果是随机读取的，则使用AbstractList更合适(AbstractList并没有提供随机读取的实现，类注释的意思只是说如要随机读取，则AbstractSequentialList没有任何帮助，不如实现AbstractList更准确)。事实上，为了表明集合是否可以根据索引随机读取，Collection框架专门定义了一个空接口RandomAccess，以标识该类是否可随机读，ArrayList、Vector都实现了这个接口，而没有实现这个接口的，则是不可以通过下标索引来寻址的。

LinkedList有比ArrayList在接口上有更丰富的功能，比如addFirst()、addLast()、push()、pop(),、indexOf()，同时它的listIterator()也要比iterator()更常用一些。我们以前常说对于经常删除、增加的集合，使用LinkedList比ArrayList效率要高，这是容易被误解的，LinkedList的寻址相比数组来说非常地慢，如果在频繁增/删之前需要寻址定位，那么仍然比ArrayList要慢很多，数十倍地慢，所以使用它的时候要谨慎，不能耍小聪明。LinkedList根据索引寻址的get(int index)方法，使用的是简单的“二分法”，即如果index小于size的一半，则从前往后迭代；大于size一半则从后往前迭代。这也是没有办法的事情，LinkedList是需要保证插入顺序的，所以不能做任何排序，也就不能使用任何如冒泡、快速排序之类的算法。有没有不需要保证插入顺序从而能够快速寻址的集合呢？TreeSet/HashSet可以快速寻址，但不能有重复值；TreeMap/HashMap同样是不能有重复值；Collection框架并没有给出能有重复值同时又能允许排序的List，应该是他们认为ArrayList就可以满足这种场景了，但类库中有个类IdentityHashMap，它的hash()方法用的是System.identityHashCode()而不是HashMap所用的key.hashCode。System.identityHashCode()意思是不管对象是否实现了hashCode，都取Object的hashCode也就是对象的内存地址来作为key，这样即使两个对象hashCode相等，也会被重复插入(在该类的注释中说到了它的一些使用场景，有兴趣的可以仔细看下)。

我们知道通常的集合都是非线程安全的，表现在多个线程同时增/删时，集合大小会不可预测，同时Iterator尽量保证在迭代过程中操作是安全的(不保证准确，但尽量保证不会有越界问题)，即当某线程迭代读取集合时，如有其他线程修改此集合的结构(扩大/缩小)，则会抛出ConcurrentModificationException。那么它是如何实现的呢？在集合中都会维护一个内部计数器modCount，如果有影响集合结构的操作(增加、删除、合并等，而修改不是)，modCount都会自增1。在对集合迭代时，都会检查当前迭代时的操作计数器副本expectedModCount(迭代前初始化为和modCount相等)和modCount是否相等

int expectedModCount = modCount;

final void checkForComodification() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

}

同样，Set、Map(获得Entry的HashIterator迭代器)中都有modCount这样的操作计数器。

Set用的相对少一些，同时它基本是依托于Map实现的。HashSet依托于HashMap，TreeSet依托与TreeMap，所以先从Map说起。

都知道Map是不继承自Collection的，是顶级接口，为什么这么设计？从根本上来说，Collection是一维的，而Map是二维的，那么是否存在三维的？j2se并没有提供这样的类库，但google的guava框架提供了这样的，如com.google.common.collect.Table，其中R是行key、C是列key，而V就是对应的值，也就是说j2se类库考虑的情况会比较多，而各开源框架就可以根据自己的定位设计出更专业化的类库。

Map接口的方法和Collection差不多，不过从键的维度、值的维度以及把键值作为一个整体的维度，有了keySet()、values()、entrySet()这样的接口方法。

Map提供了抽象类AbstractMap，使用entrySet的迭代器循环，提供如get、remove、containKey这样的默认实现。为什么Map不实现Iterable接口呢？我觉得没有必然的原因，Map实现Iterable接口也无不可，本身它内部就有以entrySet的Iterator来做遍历的使用，只是作为Map这样的结构来说，实现Iterable有些混淆，到底是迭代K呢，还是迭代V呢，或者是迭代整体？所以干脆Map本身就不提供迭代器，而是提供了分别按键、值、键值对三个迭代器接口。

HashMap也就是哈希表，我们都知道它内部是一个数组链表的结构，即一个数组，

transient Entry[] table = (Entry[]) EMPTY_TABLE;

其中放的是Entry对象的引用，而每个Entry内部又维持hash相同的下一个Entry引用形成链表。

static class Entry implements Map.Entry {

final K key;

V value;

Entry next;

int hash;

Entry(int h, K k, V v, Entry n) {

value = v;