JDK源码研究之2Java集合设计

集合接口体系:

Iterable
           ---->Collection
                          ---->List
                           ---->Set  
                                  ---->SortedSet
                                 ---->NavigableSet(6.0)
                          ---->Queue
                                   ---->Deque

Map
           ---->SortedMap
                    ---->NavigableMap(6.0)

集合类体系：

Collection
          ---->AbstractCollection
  
               ---->AbstractList(implements List)
                        ---->AbstractSequentialList
                                  ---->LinkedList
                        ---->ArrayList
               ---->AbstractQueue(implements Queue)
                     ---->PriorityQueue   
            ---->AbstractSet(implements Set)
                       ---->EnumSet
                      ---->HashSet
                     ---->TreeSet
             ---->ArrayDeque(implements Deque)

Map
  ---->AbstractMap
            ---->EnumMap
            ---->HashMap
           ---->IdentityHashMap
          ---->TreeMap
           ---->WeakHashMap



1、Iterable里面只有一个方法Iterator<T> iterator()，该方法返回集合内部元素的叠代.在AbstractCollection 中就可以看出这种设计的好处了,在AbstractCollection中有两个未实现的方法iterator()跟size()，还有一个特殊的方法是add(E e)，总会抛出UnsupportedOperationException。
   其他Collection接口的方法实现均可以通过前两个方法来实现。当需要一个不可修改的集合时，只需要在子类实现iterator()与size()方法即可，如果还想可以修改内部的元素，在子类还需实现add(E e)方法。

2、与AbstractCollection类似,AbstractList也最大程度实现了List接口的方法，内部类里面还默认实现了一个Iterator，留下了add(int,E)，remove(int i),set(int,E),get(int i),size()方法给子类实现。AbstractQueue、AbstractSet同理。
  
3、Map与Collection是平行的，并没有相互继承，从技术上来说可以把(key,value)作为一个Entity看待，从而让Map继承Collection，但这样做会大大增加复杂度甚至可能导致接口的污染。Map属于集合，但不继承Collection，这种以引用代替继承的做法值得推荐，也告诉了我们一个道理：不要为了继承而继承！

4、List与Set的区别是Set中的元素不允许重复，而Map中的Key默认就是不允许重复的，事实上JDK中的Set就是通过引用Map来实现的，set元素作为map的key,value是一个默认的object。

5、ArrayDeque是一个双向队列，内部是一个由一个数组和两个指针组成的循环数组组成。

6、ArrayList里面也是一个数组，在大学数据结构中也学过，由于位置是连续的，get(i)这种随机操作速度快，而remove(i)因为删除之后要把i之后的元素向前移，速度慢。

7、在JDK1.0时候有一个接口Dictionary现在已经被Map代替了，它的实现类HashTable也被HashMap代替了，不过HashTable的每个方法都是有synchronized关键字的。

8、EnumMap以Enum作为Key，由于Enum内部维护了枚举成员的位置(从0开始)，所以get(key)类似的操作定位相当快，比HashMap要快。

9、EnumSet是一个抽象类，提供了N个静态方法来创建具有多个Enum的set。64个以内元素个数时用RegularEnumSet,64个以上时用JumboEnumSet

10、HashMap，这个最经常使用的类，很多人还不了解其内部实现。其实他内部也是维护了一个Entity数组，把key做hash后再经过余位等运算便可以找到其在数组中的位置。当元素个数 > 加载因子*容量 时会将容量增加一倍，如果HashMap较大，复制操作也颇为耗时，所以对于元素大小范围确定的HashMap，在new时就提供其初始容量是一个明智的选择。

11、HashSet，内部其实就维护着一个HashSet,LinkedHashSet内部维护的是LinkedHashMap。

12、IdentityHashMap，把equal换成了=，内部的rehash算法颇复杂。

13、Iterator里面三个方法hasNext(),next(),remove()，代替了Enumeration的很长的方法，ListIterator是一个可以双向移动的Iterator

14、LinkedHashMap，链式结构的HashMap，里面是一个双向链表，做put或get操作时先把已有的元素删除，再把新元素加到头里。这样近期最活跃的元素就处在顶端了，所以能用来做LRU实现。

15、LinkedList，List的链式实现，它的特性决定能作为堆栈、队列、双端队列使用。

16 NavigableSet接口扩展了SortedSet & NavigableMap接口扩展了SortedMap，提供了更细致的“子集合”方法。

17、Stack直接继承自废弃类Vector，Vector里每一个方法均为sychronized的，建议继承ArrayList实现一个非同步的Stack以得到在单线程下效率更高的堆栈实现。

18、TreeMap与TreeSet里面维护的是一个堆数据结构，大顶堆或小顶堆实现有序结构。

19、WeakHashMap，如果key为软引用，那么其value是会丢失的，GC会自动回收。

20、Collections里面包含N个static方法可以对collection操作（包括Map）或查询(如二分查询etc.)，里面有或干个包装器如synchronizedMap返回Map的包装器，返回同步实现。

21、其实数组是一个最原始的集合，Arrays类提供了N个static方法可以用数组进行操作或查询。