集合框架

集合框架：

BitSet:???

HashMap的实现原理

添加动作：
对添加的KEY 通过一个哈希函数求值，然后根据当前存放Entry（key-value ）数组的长度做一个h & (length-1)运算，
获得当前存放的位置。
这时当前位置可能已经有值存放了，产生了冲突，解决的办法是，当前Entry与旧的Entry用链表连接起来。
HashMap 中使用一个单向的链表。

获取动作：
对传入的KEY 对添加的KEY 通过一个哈希函数求值，然后根据当前存放Entry（key-value ）数组的长度做一个h & (length-1)运算，
获得当前存放的位置（快的原因就在这里，不需要循环数组就直接定位）。
对当前位置的Entry中存放的KEY进行对比，如果相同（相等或equals返回真）就返回Entry的value。如果不相同，就看
Entry是否有后驱（因为产生冲突时是使用单向链表存放的），对该链表进行循环判断。

解决冲突的办法：
解决哈希表的冲突-开放地址法和链地址法
在实际应用中，无论如何构造哈希函数，冲突是无法完全避免的。

1 开放地址法


这个方法的基本思想是：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式描述：
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ， k ( k ≤ m – 1))
其中： H ( key ) 为关键字 key 的直接哈希地址， m 为哈希表的长度， di 为每次再探测时的地址增量。
采用这种方法时，首先计算出元素的直接哈希地址 H ( key ) ，如果该存储单元已被其他元素占用，则继续查看地址为 H ( key ) + d 2 的存储单元，如此重复直至找到某个存储单元为空时，将关键字为 key 的数据元素存放到该单元。
增量 d 可以有不同的取法，并根据其取法有不同的称呼：
（ 1 ） d i ＝ 1 ， 2 ， 3 ， …… 线性探测再散列；
（ 2 ） d i ＝ 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ， k^2， -k^2…… 二次探测再散列；
（ 3 ） d i ＝ 伪随机序列 伪随机再散列；

例1设有哈希函数 H ( key ) = key mod 7 ，哈希表的地址空间为 0 ～ 6 ，对关键字序列（ 32 ， 13 ， 49 ， 55 ， 22 ， 38 ， 21 ）按线性探测再散列和二次探测再散列的方法分别构造哈希表。
解：
（ 1 ）线性探测再散列：
32 ％ 7 = 4 ； 13 ％ 7 = 6 ； 49 ％ 7 = 0 ；
55 ％ 7 = 6 发生冲突，下一个存储地址（ 6 ＋ 1 ）％ 7 ＝ 0 ，仍然发生冲突，再下一个存储地址：（ 6 ＋ 2 ）％ 7 ＝ 1 未发生冲突，可以存入。
22 ％ 7 ＝ 1 发生冲突，下一个存储地址是：（ 1 ＋ 1 ）％ 7 ＝ 2 未发生冲突；
38 ％ 7 ＝ 3 ；
21 ％ 7 ＝ 0 发生冲突，按照上面方法继续探测直至空间 5 ，不发生冲突，所得到的哈希表对应存储位置：
下标： 0 1 2 3 4 5 6
49 55 22 38 32 21 13
（ 2 ）二次探测再散列：
下标： 0 1 2 3 4 5 6
49 22 21 38 32 55 13
   注意：对于利用开放地址法处理冲突所产生的哈希表中删除一个元素时需要谨慎，不能直接地删除，因为这样将会截断其他具有相同哈希地址的元素的查找地址，所以，通常采用设定一个特殊的标志以示该元素已被删除。
2 链地址法

链地址法解决冲突的做法是：如果哈希表空间为 0 ～ m - 1 ，设置一个由 m 个指针分量组成的一维数组 ST[ m ], 凡哈希地址为 i 的数据元素都插入到头指针为 ST[ i ] 的链表中。这种方法有点近似于邻接表的基本思想，且这种方法适合于冲突比较严重的情况。

例 2 设有 8 个元素 { a,b,c,d,e,f,g,h } ，采用某种哈希函数得到的地址分别为： {0 ， 2 ， 4 ， 1 ， 0 ， 8 ， 7 ， 2} ，当哈希表长度为 10 时，采用链地址法解决冲突的哈希表如下图所示。

HashTable:线程同步的。具体求在数组中的下标，算法上略有不同，但是原理是一样的。
当容器需扩大时，分循环原表中的每一个元素，重新计算下标，这时元素的位置和链接关系可能发生变化。相当于重新把原来的Entry重新加入到一个更长的数组当中。
从上可知：不同的容器长度，加入的先后顺序都会引起元素位置不同。更重要的时，在计算下标时会散列分布在数组中，并不是按顺序添加的。

LinkedHashMap:是HashMap的子类，重载了它的Entry的等实现，就是在添加Entry时，同时会往一个双向链表中添加元素，用来记录添加的顺序，这样在迭代时可以按顺序输出。
由于在维护散列表时，同时还会维护链表，添加时可能性能上不与HashMap，但是在遍历时，由于可能通过循环链表，不是散列表，避免了一些空值地址的访问。
在添加元素时，如果KEY相同，替换了原来的VALUE，这时链表中的Entry位置还是保持原来的位置，并不会改变，当扩大容器时也一样，链表中的顺度是不会变的。

TreeMap:其内部是红黑树的存储结构，迭代的元素是按升序排列的。可能会按照键的类的自然顺序 进行排序（参见 Comparable），或者按照创建时所提供的比较器进行排序。
return (comparator==null ? ((Comparable)k1).compareTo(k2)
                                 : comparator.compare(k1, k2));
该类不接受初始容量 和加载因子，每次空量增1，内部节点是通过指针进行连接，不像数组扩容量时需要移动原来的元素。

ArrayList：使用数组存放元素
LinkedList:使用双向链表存放元素
Vectory:与ArrayList的区别是，其操作是线程同步的。

HashSet:内部实际是使用了一个HashMap存放元素，元素被作为KEY值存放。
LinkedHashSet：内部使用LinkedHashMap

TreeSet：内部使用TreeMap进行支持。
TreeMap

Set:中存放的元素是非重复的，通过元素的equals方法进行判断是否重复，因此元素在实现是应该复写equals hashCode方法。hashCode影响元素散列分布。

List Set Map
这些子类的 iterator 或 listIterator 方法返回的迭代器是快速失败的。
Iterator迭代时，通过内部的一个版本号（modCount）进行判断是否在迭代过程中被修改（添加或修改元素）会抛异常ConcurrentModificationException，但是有些实现类是非同步的，因此不能依靠该异常进行同步的判断，这是不可靠的。异常继承于RuntimeException，因此不需要用户捕捉该异常。但是通过迭代器本身移除元素不会抛异常，

==================================================================
Collections:
提供了Read-only collections框架
unmodifiableList(List list)
unmodifiableMap
unmodifiableSet
unmodifiableSortedMap
unmodifiableSortedSet
如果对现有的集合框架进行添加、修改、删除操作会抛异常UnsupportedOperationException。
------------------------------------
synchronizedCollection
synchronizedList(List list)
synchronizedMap(Map map)
synchronizedSet(Set set)
synchronizedSortedMap(SortedMap map)
synchronizedSortedSet(SortedSet set)