HashMap线程不安全，怎么解决？

  • Collections.synchronizedMap(map)
  • Hashtable

  • ConcurrentHashMap

    Collections.synchronizedMap怎么实现线程安全的？

    内部维护了一个普通对象Map，和一个排斥所mutex
    image.png
    所有操作map的时候都会加synchronized锁。如果传入mutex参数，则对象排斥锁赋值为当前对象。
    HashTable类似，加synchronized

    Hashtable和HashMap的区别

  • Hashtable不允许键或值为null, HashMap允许

    为什么？ image.png Hashtable使用安全失败机制（fail-safe）,这种机制会使你此次读到的数据不一定是最新的数据。 如果使用null值，就无法判断对应的key是不存在还是为空，因为你无法再调用一次containsKey(key)来判断key是否存在进行判断，ConcurrentHashMap同理。

  • 实现方式不同

    hashtable是继承Dictionary类，HashMap是继承AbstractMap

  • 初始化容量不同

    HashMap是16， Hashtable是11， 两者的负载因子默认都是0.75

  • 扩容机制不同

    当现有容量大于总容量*负载因子的时候，HashMap是2倍扩容，Hashtable是当前容量翻倍+1

  • 迭代器不同

    hashMap的Interator是fast-fail， hashtable的Enumertator不是fast-fail. 所以，当其他线程修改了HashMap的结构，如增删，会报错ConcurrentModificationException， 而Hashtable不会

fail-fast是啥？

快速失败是集合里的一种机制，在用迭代器去遍历一个对象的时候，如果遍历过程中对集合对象的内容做了修改（增加、删除、修改）,则会抛出ConcurrentModificationException.

原理是啥？

迭代器在遍历时直接访问集合中的内容，并在遍历过程中使用一个modCount变量。集合在遍历期间如果内容发生变化，就会改变modCount的值。每个迭代器使用hasNext()/next()遍历下一个元素的时候，都会检测modCount是否为expectedmodCount，是的话就返回遍历，否则抛出异常，终止遍历。

ConcurrentHashMap

数据结构是啥？为啥并发度高？

1.7 底层是数组+链表。

1.7 是由Segment数组、HashEntry组成。和HashMap一样，数组+链表。
image.png
HashEntry和HashMap差不多，不同点是使用volatile去修饰了它的数据value还有下一个节点next。
并发度高的原因：
分段锁技术，Segment继承于ReentrantLock。每个线程占用锁访问一个Segment的时候，不会影响到其他的Segment. 如果容量大小是16，那它的并发度就是16，可以允许16个线程操作16个Segment而且是线程安全的。

put方法

第一步会尝试获得锁，如果失败说明存在其他线程竞争，自旋
自旋到最大次数则改为阻塞锁获取，保证锁能获得成功

get方法

将key通过hash定位到具体的segment，再通过hash定位到具体的元素。由于HashEntry的value属性是volatile修饰的，保证了内存可见性。整个过程不需要加锁。

1.8 底层是数组+链表+红黑树

抛弃了Segment分段锁，采用CAS+Synchronized来保证并发安全性。
跟HashMap很像，把hashEntry改成了Node，但是作用不变，把值和next都用volatile修饰，保证了可见性，并且引入了红黑树，在链表大于一定值的时候会转换，默认是8.

put方法
  1. 先根据key计算出hashCode
  2. 判断是否需要进行初始化
  3. 即当前的key定位的Node，如果为空，表示当前位置可以写入数据，利用CAS尝试写入，失败则自旋保证成功
  4. 如果当前位置的hashCode == MOVED == -1 ,则需要进行扩容
  5. 如果都不满足，则利用synchronized锁住数据

  6. 如果数量大于TREEIFY_THRESHOLD （默认值8）, 则转换为红黑树。

    get方法

  7. 根据计算出的hashCode寻址

  8. 如果是红黑树就按照树的方式获取值
  9. 不满足就按照链表的方式获取值。

    为什么1.8会用Synchronized?

    synchronized之前都是重量级的锁，1.8升级之后采用了锁升级的方式去做的。

    针对Synchronized获取锁的方式，JVM采用了锁升级的优化方式，就是先用偏向锁优先同一线程然后再次获得锁，如果失败，就升级为CAS轻量级的锁，如果失败就会短暂的自旋，防止线程被系统挂起。如果以上还是失败，就升级为重量级的锁。

扩容机制

ConcurrentHashMap的扩容机制

1.7 版本

  1. 1.7的ConcurrentHashMap是基于Segment分段锁实现的
  2. 每个Segment相当于一个小型的HashMap
  3. 每个Segment内部会进行扩容，和HashMap的扩容逻辑类似
  4. 先生成新的数组，然后转移原数组到新的数组中
  5. 扩容的判断也是每个Segment内部单独判断的，判断是否超过阈值

1.8版本

  1. 1.8的ConcurrentHashMap不再基于Segment实现，基于Node
  2. 当某个线程进行put时，如果发现ConcurrentHashMap正在进行扩容，那么该线程一起进行扩容
  3. 如果某个线程put时，发现没有正在进行扩容，则将key-value添加的ConcurrentHashMap中，然后判断是否超过了阈值，超过了则进行扩容
  4. 支持多线程同时扩容
  5. 扩容前也是先生成一个数组
  6. 在转移元素时，先将原数组 分组，将每组分给不同的线程来进行元素的转移，每个线程负责一组或者多组的元素转移工作。