HashMap和ConcurrentHashMap的浅析

HashMap的内部数据结构

不同的JDK实现方式不同

JDK1.6、1.7中：位桶+链表

首先它是一个数组实现，其解决冲突的方式为开链法。即多个元素hashCode相同时，放在链表里。如下图所示。

JDK1.8中：位桶+链表+红黑树

上面方式的缺点是，当相同hashCode的元素比较多时，单链表的查询效率比较低。由于，当某个单链表的个数达到一个数目(默认8)时，就采用红黑树的数据结构。

当加载因子达到0.75时，就会将位桶的长度增加一倍，然后将原有的数据拷到新的位桶中。

HashMap和ConcurrentHashMap

显然HashMap是非线程安全的。

而ConcurrentHashMap是线程安全的，一般情况下，在需要用到线程安全的场景下时，ConcurrentHashMap是第一选择。

ConcurrentHashMap相比较于HashTable的好处是啥？

HashTable是全表的锁，即一个线程在写的时候，另一个线程就不允许写了。不管他们写的是哪个key。

而ConcurrentHashMap也是锁，只是锁的粒度不同。即把整个数组分为多个段(Segment)，锁只是针对每个段进行。即一个线程在写段1，另一个线程是可以写段2的。如图：

还是很容易理解的。

存在的问题：

有些操作是跨段的，这就需要进行锁住整张表。这里就会按照段的顺序进行逐步加锁，直至锁住整张表，操作完毕后，再按照顺序释放所有锁。注意这里的“顺序是很重的”，保证顺序性才能防止死锁的产生。

为什么？这里就多说一点。为何顺序加锁就不会导致死锁？

“顺序的申请和释放资源”其实就是防止死锁的一个很重要的解决方法。

我们来分析一下：

死锁的产生的场景：A线程占6申请7，B线程占7申请6，这样就会产生死锁。而如果我们都按照顺序的大小申请资源。即B线程占7之后，就一定不会申请比7小的资源。这样就不会产生死锁了。

其实死锁相关的知识还是比较多的，这里只是大概说一下。