聊聊HashMap

HashMap

jdk1.7实现版本

数组+链表

• 引入
  数组+链表。很简单，初始化一个数组，解决冲突的办法就是开链法：将hashCode相同的元素放入链表中。

  
  image.png
• 非线程安全
  hashmap是非线程安全的，即hashmap的实现中不涉及同步锁的概念。所以多个线程put或一个线程put一个线程get都会引起同步问题。
• resize操作
  • 装载因子：hashmap总元素个数/数组长度
  • 在put方法中，如果发现新增元素后，hashmap的装载因子过高（默认是0.75），就会自动触发resize操作。
  • resize操作的步骤：申请两倍大小的数组，将原数组中的链表一次转移到新的数组中。具体操作是修改对象引用，并不是完全new每个链表的每个结点。
  • 上述的转移操作可能会引发死循环问题：多个线程同时put，同时触发resize操作，在转移链表的过程中，引起了引用的回路，造成死循环。可能会把CPU打到100%。

jdk1.8实现版本

数组+链表+红黑树

• 并不解决线程安全问题，而是提升了get方法的效率。
• 当一个链表的个数打到某个阈值（默认8）时，就会使用红黑树来代替链表。显然get效率从之前的O(n)->O(logn)。

ConcurrentHashMap

上面说hashmap并不是线程安全的，ConcurrentHashMap就是用来解决线程安全的。

jdk1.7实现版本

数组+segment+链表
同步：segment+ReentrantLock

• 数据结构

  
  image.png

如图所示，map由1.7中的两级被分为了三级。首先hashmap中存的是segment数组。每个segment数组中存放一个实体数组，每个数组中是一个链表结构。

• 如何解决线程安全问题？
  • 每个segment对象继承了ReentrantLock，即对分段进行加锁管理。
  • put操作
    先获取锁：自旋的retryLock，一段时间后再进行阻塞的lock。
    然后再进行写入操作
  • get操作
    并不加锁。get操作使用的共享变量都被声明为valotile，保证了线程可见性，所以可以直接读取。除了需要链表顺序查找，这个设计还是很棒的。
• 缺点
  • size()得到的结果可能不是特别准
    jdk7对于ConcurrentHashMap size的内部实现：依次对每个segment进行size操作，然后将每个segment的size相加。整个map连续进行两次这样的操作，如果两次的结果相同则返回。否则锁住整张表。
  • 我们发现其实锁的粒度为segment，这个粒度还是有点粗，即修改同一个segment下的两个不同的元素也会被阻塞。如果可以是每个数组元素就很好了。

jdk1.8实现版本

数组+链表+红黑树
同步：CAS+synchronized

目的就是为了提高了1.7效率。
如何提高？

• 数据结构
  和jdk1.8中的hashmap一样，使用红黑树代替链表。
  取消了segment三层结构，使用和hashmap一样的两层结构。
• 锁的粒度
  上面我们知道1.7中锁的粒度为segment，而在1.8中取消了segment。锁的粒度变成了每个数组的元素（使用synchronized）。这样引发了一个问题，那么跨数组元素的操作怎么办？比如size操作。
  • 解决办法：将map的size变量设为原子性变量，比如AtomicInteger变量。每次put或remove维护这个变量即可。
• 具体操作
  • put操作。先使用CAS进行put，如果失败则使用synchronized加锁。
  • get操作。和1.7一样，使用valotile保证效率。
  • size操作。每次put或remove维护一个原子变量即可。