浅析HashMap、ConcurrentHashMmap

1、JAVA1.7HashMap的原理分析

①HashMap实现原理？

答：HashMap是数组+链表的形式，主干是数组，链表主要是解决哈希冲突问题。在数组某个位置没有链表时，查找、添加操作很快，但是当有了链表后，虽然添加操作很快，但是由于链表的特性，查询操作非常慢。当添加数据时，出现了哈希值一样的数据，是在该节点的头部添加（这种方式比在尾部添加快），添加完成之后再将链表向下移动一位，将新的头节点赋给数组。

②HashMap的自增

答：当集合的长度达到了HashMap的阈值的时候，HashMap会以翻倍扩容（如：HashMap默认初始容量是16，默认加载因子是0.75，所以当集合的填充量达到了12的时候，会自动扩容到32）。

③HashMap扩容带来的死循环问题？

答：在HashMap扩容的时候，由于HashMap每次添加链表数据的时候都是在头节点添加，所以会导致扩容后的集合中链表的顺序会和之前相反。此时如果是多线程在进行访问，那么就会造成死循环问题。

④为什么HashMap的长度都是2的次幂？

答：比如初始容量是16，二进制是0001 0000，源码中将容量减一，那么就是15,二进制0000 1111；而源码中是将容量&哈希值进行计算的，如果哈希值是0101 1010，那么进行了&运算过后，得到的值是1010，这个值一定是在0-15之间的，所以这样保证了集合的散列性，且不会越界。

2、JAVA1.8HashMap的原理分析

①java的HashMap1.8对比1.7作出的改动？

答：HashMap1.7使用的是数组+链表的数据结构，1.8使用的是数组+链表+红黑树的数据结构。实现原理和1.7差不多，但是在链表长度达到8的时候，HashMap会将链表自动转换为红黑树（当链表长度过长的时候，查询起来会非常的麻烦，但是红黑树相对链表来说会简单很多）；当红黑树的节点少于6的时候，又会自动转换为链表。

②1.8对比1.7作出的一些优化？

答：1.7当多线程情况下数组进行扩容的时候，可能会造成死循环的问题（因为链表每次添加数据的时候是在头节点进行添加的）；但是在1.8中链表添加数据时在尾部进行添加，所以杜绝了死循环问题。

3、JAVA1.7ConcurrentHashMap的原理分析

①1.7ConcurrentHashMap结构图

②实现方式？

答：实现方式依然是数组+链表的形式。核心是引入了分段锁的机制，一个segment管理几个节点（Segment类继承了ReentrantLock，所以线程安全），当一个线程占用一个segment时，不会影响到其它的segment。

4、JAVA1.8ConcurrentHashMap的原理分析

①1.8ConcurrentHashMap结构图

②实现方式?

1、在数据结构上使用数组+链表+红黑树的方式。

2、抛弃了原来分段锁的机制，而采用了 CAS + synchronized 来保证并发安全性。