HashMap

想来讨论一下HashMap，随笔记录一下吧。

HashMap主要在1.7和1.8的时候变动比较大一点，主要有以下方面

结构

1.7的HashMap的结构是数组+链表的组合，1.8之后变成了数组+链表+红黑树的组合，当你的链表长度超过8后自动转化为红黑树提高查询效率，当长度小于6时又会自动转换回来；

put

在你往HashMap中put一个值的时候，它会先去对你的Key进行hash然后得到数组下标，如果你数组的这个位置是空的没有元素，就直接添加进去，如果有元素则判断一下原来存在的元素的key值和新添加的是否相等，如果相等则更新它的value，如果不相等则插入新的元素；在1.7的时候是使用的头插法，1.8的话使用的是尾插法；头插法会有一个什么问题呢，当你容器进行扩容的时候，会进行resize然后去rehash，然后这个时候有可能会行成一个闭合的链，接着在你下次去get的时候，就有可能在这个点去行成一个死循环，所以1.8之后改用了尾插法。

线程安全

大概变动就这样，然后HashMap它还是一个线程不安全的容器，在高并发的环境下并不适用，所以一般我们一般使用concurrentHashMap这样的同步容器；为什么不使用hashTable呢？因为hashTable它其实是直接加了一个synchronize这样的重量级锁，锁住了整个对象，所以并发度比较低，然后concurrentHashMap用的是CAS + synchronize，它锁住的是你当前访问的一个节点，再加上1.6后对synchronize的一个优化，所以使用concurrentHashMap的并发度是更高的。

扩容

然后它还有一个扩容的过程，当你向容器中put一个元素的时候，它会去判断你容器中元素个数有没有超过一个阈值，这个阈值是它自己计算的，在你实例化HashMap的时候，如果没有对它的容器大小和负载因子设置的话，那默认的容器大小是16，负载因子是0.75，而它的阈值就是16 * 0.75 = 12，当元素个数超过12的时候，它就会去扩容，扩大一倍的容量，然后对元素进行resize、rehash重新确定元素对应的数组下标。