HashMap Hashtable TreeMap LinkedHashMap 分析

首先对hash的了解：就是关键字，和数据建立关系的映射。

　　hash常用算法：假设我们中的字符有相应的内部编码，当然在实际过程中，我们不可能将所有的编码当做hash值。

　　　　　　　　平方取中法，将所得的内部编码平方，取7-9位作为hashcode.

　　　　　　　　折叠法：将编码分割，然后相加。

　　　　　　　　除留取余法

　　即便是按照上面的计算，也有可能发生冲突。

1.HashMap 分析

　　基于哈希表的Map接口的非同步实现，不保证顺序，允许键值为null，但是只能有一个，它实际相当于链表和数组的结合体。

　　根据key计算数据在数组上面存储的位置，没有这个位置没有值，则放入值，如果有值，如果有key,进行数据的覆盖，如果不存在，那个这个值将以链表的方式存储，

　　新加入的放在链表的头部。（java8新加入红黑树）如果不存在key值，那么判断是否为红黑树，如果是，红黑树直接插入，如果不是，遍历准备插入，如果大于8，

　　转化为红黑树插入，否则，判断是否存在键，覆盖或者插入，最后，判断是否需要扩容。

　　数据的读取，根据key的hashcode，找到对应位置的数据，这个位置可能是一个，也有可能是多个，如果是多个值，然后通过key值的equals 方法进行对比，

　　找到元素。

2.Hashtable是线程安全的

　　值不能为空，否则抛出异常，原理和上面相同，数据新增过程中如果table[index]元素不为空，则进行迭代，如果遇到相同的key，则直接替换，并返回旧value；

　　否则，我们可以将其插入到table[index]位置

　　上面两个，里面的数据，会保存同位置的下一个数据的对象。

3.LinkedHashMap

　　维护一个双向链表，保存上一个和下一个数据的对象。

　　hashmap 的初始容量是16，乘以负载因子0.75，相当于是12个，在扩容过程中，需要重新计算hash值，计算位置，所以在创建的时候，我们尽量设置大小。

　　在java8中，引入了红黑树，就是避免拉链过长，默认情况下，当链表长度超过8时，就会转化为红黑树进行。

4.TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。 　

红黑树是二叉树的一种，每个节点要么是红的，要么是黑色的，根节点是红色的，红色节点的两个儿子一定是黑色的，

每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

5.在我们使用迭代的过程中，java中，使用了fail-fast机制，就是快速失败机制，也就是数据的安全性，就是多线程下，同时删除和新增，检测失败的一种机制，

　但是这种机制不是绝对不会失败，只是用于失败的检测，失败后，会抛出异常。　

巴特西