1. HashMap 简介

java.util.Map 中，此接口有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap, 类继承关系图如下所示：

concurrentHashMap - 图1

各类特点如下：

  • HashMap: 根据hashCode 存储数据，访问速度快，仅允许一条记录key = null,允许多条记录的值为null;
  • LinkedHashMap: hashMap 的子类，保存了插入的顺序，遍历时根据插入顺序遍历；
  • TreeMap: 实现SortMap 接口，能够根据键值排序；key必须实现Comparable接口；

存储结构

HashMap 是数组+链表+红黑树（JDK1.8增加了红黑树）；

concurrentHashMap - 图2

1） 数据存储在Node[]table (即 哈希桶数组)这个成员变量里；

  1. static class Node<K,V> implements Map.Entry<K,V> {
  2.         final int hash;    //用来定位数组索引位置
  3.         final K key;
  4.         V value;
  5.         Node<K,V> next;   //链表的下一个node
  7.         Node(int hash, K key, V value, Node<K,V> next) { ... }
  8.         public final K getKey(){ ... }
  9.         public final V getValue() { ... }
  10.         public final String toString() { ... }
  11.         public final int hashCode() { ... }
  12.         public final V setValue(V newValue) { ... }
  13.         public final boolean equals(Object o) { ... }
  14. }

Node是内部类，存储了键、值、哈希值；

2）哈希冲突的解决，链地址法，即数组+链表；

功能方法

hash值计算

  1. // 方法一：
  2. static final int hash(Object key) {   //jdk1.8 & jdk1.7
  3.      int h;
  4.      // h = key.hashCode() 为第一步 取hashCode值
  5.      // h ^ (h >>> 16)  为第二步 高位参与运算
  6.      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  7. }
  9. // 方法二：
  10. static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
  11.      return h & (length-1);  //第三步 取模运算
  12. }

注： 方法1、方法2 实质上 java7、8是都有的；只不过java8 没有把indexFor抽象成一个方法；

put方法

  1. public V put(K key, V value) {
  2.      // 对key的hashCode()做hash
  3.      return putVal(hash(key), key, value, false, true);
  4.  }
  6.  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  7.                 boolean evict) {
  8.      Node<K,V>[] tab; Node<K,V> p; int n, i;
  9.      // 步骤①：tab为空则创建
  10.      if ((tab = table) == null || (n = tab.length) == 0)
  11.          n = (tab = resize()).length;
  12.      // 步骤②：计算index，并对null做处理 
  13.      if ((p = tab[i = (n - 1) & hash]) == null) 
  14.          tab[i] = newNode(hash, key, value, null);
  15.      else {
  16.          Node<K,V> e; K k;
  17.          // 步骤③：节点key存在，直接覆盖value
  18.          if (p.hash == hash &&
  19.              ((k = p.key) == key || (key != null && key.equals(k))))
  20.              e = p;
  21.          // 步骤④：判断该链为红黑树
  22.          else if (p instanceof TreeNode)
  23.              e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  24.          // 步骤⑤：该链为链表
  25.          else {
  26.              for (int binCount = 0; ; ++binCount) {
  27.                  if ((e = p.next) == null) {
  28.                      p.next = newNode(hash, key,value,null);
  29.                       //链表长度大于8转换为红黑树进行处理
  30.                      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
  31.                          treeifyBin(tab, hash);
  32.                      break;
  33.                  }
  34.                   // key已经存在直接覆盖value
  35.                  if (e.hash == hash &&
  36.                      ((k = e.key) == key || (key != null && key.equals(k)))) 
  37.                             break;
  38.                  p = e;
  39.              }
  40.          }
  42.          if (e != null) { // existing mapping for key
  43.              V oldValue = e.value;
  44.              if (!onlyIfAbsent || oldValue == null)
  45.                  e.value = value;
  46.              afterNodeAccess(e);
  47.              return oldValue;
  48.          }
  49.      }
  51.      ++modCount;
  52.      // 步骤⑥：超过最大容量 就扩容
  53.      if (++size > threshold)
  54.          resize();
  55.      afterNodeInsertion(evict);
  56.      return null;
  57.  }

concurrentHashMap - 图3

扩容机制

新建一个新数组，迁移数据；

  1.   Node<K,V> loHead = null, loTail = null;
  2.   Node<K,V> hiHead = null, hiTail = null;
  3.   Node<K,V> next;
  4. if ((e.hash & oldCap) == 0) {
  5.     if (loTail == null)
  6.         loHead = e;
  7.     else
  8.         loTail.next = e;
  9.     loTail = e;
  10. }

经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置

注意点：扩容后数据的保存位置可能不一样。位置 = key的哈希与高位运算结果 + oldCap;

concurrentHashMap - 图4

2. ConcurrentHashMap

Map的派生类，api基本与HashMap一致，加入了同步操作；

1.7版本ConcurrentHashMap由一个个Segment组成，简单来说，ConcurrentHashMap是一个Segment数组，通过继承ReentrantLock来进行加锁，通过每次锁住一个segment来保证segment内的操作的线程安全性；
点击查看【processon】

理论上最多支持16个并发写入操作；

相对于1.7版本，1.8的改进

1）取消了segment的分段设计，直接采用Node数组来保存数据，并采用Node数组元素作为锁（减少并发冲突的概率）；

2）由数组+单向链表，改为数组+单向链表+红黑树结构；链表数量大于8，自动变为红黑树，查询复杂度降低至O(logN)；

3) 计算元素个数 方式不一样；
1.7 是连续计算两次 数量，如果两次一样则返回； 如果不一样，则给每一个segement 加锁重新计算元素个数：
1.8 是volatitle baseCount , cellCount[] , 累加起来；

addCount

// putVal（） 采用synchronized对同步代码块加锁；最后调用addCount()

// x:这次需要在表中新增的元素个数，check标识是否需要进行扩容检查（>0,检查）；

  1. private final void addCount(long x, int check) {
  2.    CounterCell[] as; long b, s;
  3.    // 判断 counterCells 是否为空，
  4.     1. 如果为空，就通过 cas 操作尝试修改 baseCount 变量，对这个变量进行原子累加操
  5.         作(做这个操作的意义是：如果在没有竞争的情况下，仍然采用 baseCount 来记录元素个数)
  6.     2. 如果 cas 失败说明存在竞争，这个时候不能再采用 baseCount 来累加，而是通过
  7.         CounterCell 来记录
  10.    if ((as = counterCells) != null ||
  11.        !U.compareAndSwapLong(this, BASECOUNT, b =    baseCount, s = b + x)) {
  12.        CounterCell a; long v; int m;
  13.        boolean uncontended = true;
  14.        if (as == null || (m = as.length - 1) < 0 ||
  15.            (a = as[ThreadLocalRandom.getProbe() &    m]) == null ||
  16.            !(uncontended =
  17.              U.compareAndSwapLong(a, CELLVALUE, v =    a.value, v + x))) {
  18.            fullAddCount(x, uncontended);
  19.            return;
  20.        }
  21.        if (check <= 1)
  22.            return;
  23.        s = sumCount();
  24.    }
  26.     //....
  27. }

CounterCells初始化图解

初始化长度为 2 的数组，然后随机得到指定的一个数组下标，将需要新增的值加入到对应下
标位置处

concurrentHashMap - 图5

3. 经典问题

1）JDK1.8 HashMap扩容为神马是原数组的两倍？

为了减少hash次数，通过与运算（ node.hash() & oldCapSize ），得出0，1；
0位置不用变，1位置 = 当前位置+capSize

2) 链表神马时候变为红黑树？

单个链数量大于8 且总元素大于 64
小于6转化成链表

参考

Java 8系列之重新认识HashMap
ConcurrentHashMap实现线程安全的底层原理, 1.7和1.8的比较
hashmap头插法和尾插法区别_一个跟面试官扯皮半个小时的HashMap