Hashtable不推荐使用ConcurrentHashMap推荐使用

HashMap

链表jdk1.7/数组链表红黑树jdk1.8当链表长度超过阈值8将链表转为红黑树

时间复杂度降低为O(logn)

当A线程put()数据时都发现空间不够执行resize()时而同时B线程也put()数据也发现空间不够执行resize()有可能在A线程rehash()生成新表时节点i-k而B线程rehash()生成新表时又将节点k-j导致生成了死循环i.nextk;k.nexti;当一旦进入这个链表就会导致死循环。

扩容造成死循环和数据丢失

假设现在有两个线程A、B同时对下面这个HashMap进行扩容操作

但是当线程A执行到上面transfer函数的第11行代码时CPU时间片耗尽线程A被挂起。

即如下图中位置所示

当线程A的时间片耗尽后CPU开始执行线程B并在线程B中成功的完成了数据迁移

重点来了根据Java内存模式可知线程B执行完数据迁移后此时主内存中newTable和table都是最新的也就是说7.next3、3.nextnull。

接着继续执行下一轮循环此时e7从主内存中读取e.next时发现主内存中7.next3此时next3并将7采用头插法的方式放入新数组中并继续执行完此轮循环结果如下

上轮next3e3执行下一次循环可以发现3.nextnull所以此轮循环将会是最后一轮循环。

接下来当执行完e.nextnewTable[i]即3.next7后3和7之间就相互连接了当执行完newTable[i]e后3被头插法重新插入到链表中执行结果如下图所示

上面说了此时e.nextnull即nextnull当执行完enull后将不会进行下一轮循环。

到此线程A、B的扩容操作完成很明显当线程A执行完后HashMap中出现了环形结构当在以后对该HashMap进行操作时会出现死循环。

并且从上图可以发现元素5在扩容期间被莫名的丢失了这就发生了数据丢失的问题。

其中第六行代码是判断是否出现hash碰撞假设两个线程A、B都在进行put操作并且hash函数计算出的插入下标是相同的当线程A执行完第六行代码后由于时间片耗尽导致被挂起而线程B得到时间片后在该下标处插入了元素完成了正常的插入然后线程A获得时间片由于之前已经进行了hash碰撞的判断所有此时不会再进行判断而是直接进行插入这就导致了线程B插入的数据被线程A覆盖了从而线程不安全。

除此之前还有就是代码的第38行处有个size我们这样想还是线程A、B这两个线程同时进行put操作时假设当前HashMap的zise大小为10当线程A执行到第38行代码时从主内存中获得size的值为10后准备进行1操作但是由于时间片耗尽只好让出CPU线程B快乐的拿到CPU还是从主内存中拿到size的值10进行1操作完成了put操作并将size11写回主内存然后线程A再次拿到CPU并继续执行(此时size的值仍为10)当执行完put操作后还是将size11写回内存此时线程A、B都执行了一次put操作但是size的值只增加了1所有说还是由于数据覆盖又导致了线程不安全。

首先HashMap本身线程不安全其次HashMap的key值可以为空

下面是HashMap的hash方法可以看出如果key值为空hash方法的返回值为0

HashMap

Hashtable源码中的put方法中的key如果为空hashCode方法会抛出空指针异常

2.1**HashTable的线程安全只是简单的把关键方法加上了

synchronized

一个Hashtable只有一把锁两个线程访问Hashtable中的任意数据都会出现锁竞争就如上图有两个线程要操作这两个元素由于是一把大锁就会产生竞争但是仔细分析这两操作在不同的哈希桶上不牵扯修改同一个变量因此就不会发生线程安全所以上面的锁竞争是没有必要的。

如果两个修改落到同一个哈希桶上有线程安全风险

ConcurrentHashMap

相比之下ConcurrentHashMap就做出了重大的改进把锁的粒度细化了

volatile

此时一个哈希表上面的桶的个数可能会非常多导致出现锁冲突的概率大大降低了

8里的在Java1.7里ConcurrentHashMap不是每个桶一个锁而是“分段锁”一个锁管若干个桶

ConcurrenHashMap的key也不可以为空看下面的源码中的put方法如果keynull则会抛出空指针异常

HashMap: