hashmap的实现

1.hashmap的组成

  • 数组+链表+红黑树
    HashMap的实现使用了一个数组，每个数组项里面有一个链表的方式来实现，因为HashMap使用key的hashCode来寻找存储位置，不同的key可能具有相同的hashCode，这时候就出现哈希冲突了，也叫做哈希碰撞，为了解决哈希冲突，有开放地址方法，以及链地址方法。HashMap的实现上选取了链地址方法，也就是将哈希值一样的entry保存在同一个数组项里面，可以把一个数组项当做一个桶，桶里面装的entry的key的hashCode是一样的。在Java8中当一个桶entry数量超过8时,就会转化为红黑树

HashMap源码解析和安全性问题 - 图1

上面的图片展示了我们的描述，其中有一个非常重要的数据结构Node，这就是实际保存我们的key-value对的数据结构，下面是这个数据结构的主要内容：

  1. //单链表结构
  2.  static class Node<K,V> implements Map.Entry<K,V> {
  3.         final int hash;      
  4.         final K key;
  5.         V value;
  6.         Node<K,V> next;
  8.         Node(int hash, K key, V value, Node<K,V> next) {
  9.             this.hash = hash;
  10.             this.key = key;
  11.             this.value = value;
  12.             this.next = next;
  13.         }
  14.   }

2.源码解析

1.HashMap的put方法

  1.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                    boolean evict) {
  3.         Node<K, V>[] tab;
  4.         Node<K, V> p;
  5.         int n, i;
  6.         // table未初始化或者长度为0，进行扩容
  7.         if ((tab = table) == null || (n = tab.length) == 0)
  8.             n = (tab = resize()).length;
  9.         // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
  10.         if ((p = tab[i = (n - 1) & hash]) == null)
  11.             tab[i] = newNode(hash, key, value, null);
  12.             // 桶中已经存在元素
  13.         else {
  14.             Node<K, V> e;
  15.             K k;
  16.             // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
  17.             if (p.hash == hash &&
  18.                     ((k = p.key) == key || (key != null && key.equals(k))))
  19.                 // 将第一个元素赋值给e，用e来记录
  20.                 e = p;
  21.                 // hash值不相等，即key不相等；为红黑树结点
  22.             else if (p instanceof TreeNode)
  23.                 // 放入树中
  24.                 e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
  25.                 // 为链表结点
  26.             else {
  27.                 // 在链表最末插入结点
  28.                 for (int binCount = 0; ; ++binCount) {
  29.                     // 到达链表的尾部
  30.                     if ((e = p.next) == null) {
  31.                         // 在尾部插入新结点
  32.                         p.next = newNode(hash, key, value, null);
  33.                         // 结点数量达到阈值，转化为红黑树
  34.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  35.                             treeifyBin(tab, hash);
  36.                         // 跳出循环
  37.                         break;
  38.                     }
  39.                     // 判断链表中结点的key值与插入的元素的key值是否相等
  40.                     if (e.hash == hash &&
  41.                             ((k = e.key) == key || (key != null && key.equals(k))))
  42.                         // 相等，跳出循环
  43.                         break;
  44.                     // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
  45.                     p = e;
  46.                 }
  47.             }
  48.             // 表示在桶中找到key值、hash值与插入元素相等的结点
  49.             if (e != null) {
  50.                 // 记录e的value
  51.                 V oldValue = e.value;
  52.                 // onlyIfAbsent为false或者旧值为null
  53.                 if (!onlyIfAbsent || oldValue == null)
  54.                     //用新值替换旧值
  55.                     e.value = value;
  56.                 // 访问后回调
  57.                 afterNodeAccess(e);
  58.                 // 返回旧值
  59.                 return oldValue;
  60.             }
  61.         }
  62.         // 结构性修改
  63.         ++modCount;
  64.         // 实际大小大于阈值则扩容
  65.         if (++size > threshold)
  66.             resize();
  67.         // 插入后回调
  68.         afterNodeInsertion(evict);
  69.         return null;
  70.     }

流程图如下

HashMap源码解析和安全性问题 - 图2

2.resize机制

HashMap的扩容机制就是重新申请一个容量是当前的2倍的桶数组，然后将原先的记录逐个重新映射到新的桶里面，然后将原先的桶逐个置为null使得引用失效。

  1.     final Node<K, V>[] resize() {
  2.         //获得原来的table数组
  3.         Node<K, V>[] oldTab = table;
  4.         //原table数组的容量
  5.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
  6.         //原扩容阈值
  7.         int oldThr = threshold;
  8.         //定义新容量与阈值
  9.         int newCap, newThr = 0;
  10.         //如果原容量>0
  11.         if (oldCap > 0) {
  12.             //如果原容量已经达到最大了1<<30，则不进行扩容，只调整阈值为最大，随其碰撞了
  13.             if (oldCap >= MAXIMUM_CAPACITY) {
  14.                 threshold = Integer.MAX_VALUE;
  15.                 return oldTab;
  16.             }
  17.             //如果没达到最大，则变为原来容量的2倍
  18.             //其实这句可分解
  19.             //newCap = oldCap << 1
  20.             //如果扩容后的容量小于最大容量才会将阈值变为原来的2倍
  21.             //else if (newCap < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
  22.             //         newThr = oldThr << 1; // double threshold
  23.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  24.                     oldCap >= DEFAULT_INITIAL_CAPACITY)
  25.                 newThr = oldThr << 1; // double threshold
  26.         }
  27.         //如果oldCap = 0，oldThr > 0 这是适用于不同的构造函数的
  28.         else if (oldThr > 0) // initial capacity was placed in threshold
  29.             newCap = oldThr;
  30.             //默认构造器的处理
  31.         else {               // zero initial threshold signifies using defaults
  32.             newCap = DEFAULT_INITIAL_CAPACITY;
  33.             newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  34.         }
  35.         //如果扩容后的容量大于最大容量了1<<30
  36.         if (newThr == 0) {
  37.             float ft = (float) newCap * loadFactor;
  38.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
  39.                     (int) ft : Integer.MAX_VALUE);
  40.         }
  41.         //设置为新的值
  42.         threshold = newThr;
  43.         @SuppressWarnings({"rawtypes", "unchecked"})
  44.         Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
  45.         table = newTab;
  46.         //完成rehash
  47.         if (oldTab != null) {
  48.             //遍历原数组的每一个位置     所以rehash过程的是很耗费时间的
  49.             for (int j = 0; j < oldCap; ++j) {
  50.                 Node<K, V> e;
  51.                 //e = oldTab[j])
  52.                 if ((e = oldTab[j]) != null) {
  53.                     //将原位置设为null
  54.                     oldTab[j] = null;
  55.                     //如果没有碰撞，也就是只有这一个元素，直接定位设置到新数组的位置
  56.                     if (e.next == null)
  57.                         newTab[e.hash & (newCap - 1)] = e;
  58.                         //如果当前节点是TreeNode类型，说明已经树化了，红黑树的rehash过程
  59.                     else if (e instanceof TreeNode)
  60.                         ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
  61.                         //表明当前节点冲突是链表存储的，完成rehash   
  62.                         //注意：这是1.8的优化点，这也是容量声明为2的次幂的另一个应用
  63.                     else { // preserve order
  64.                         //rehash后将桶中的值重新分配
  65.                         Node<K, V> loHead = null, loTail = null;//记录低位链表头尾位置
  66.                         Node<K, V> hiHead = null, hiTail = null;//记录高位链表头尾位置
  67.                         Node<K, V> next;//记录当前链表元素在原来链表中的下一个元素，便于下次循环使用
  68.                         //遍历哈希桶的链表，拆分成高位和低位链表(为了更好的理解扩容,实际上只有一条单向链表)  
  69.                         do {
  70.                             next = e.next;
  71.                             if ((e.hash & oldCap) == 0) { //新增的有效哈希位为0，即当前元素扩容后分配到 低位链表 其实位置相比以前没变
  72.                                 if (loTail == null) //低位链表尚未初始化
  73.                                     loHead = e; //设置低位链表头部
  74.                                 else
  75.                                     loTail.next = e; //低位链表尾部增加当前元素，以保持原链表顺序
  76.                                 loTail = e; //更新低位链表的尾部
  77.                             } else { //新增的有效哈希位为1，即当前元素扩容后分配到 高位链表  扩容后的位置
  78.                                 if (hiTail == null) //高低位链表尚未初始化
  79.                                     hiHead = e; //设置高位链表头部
  80.                                 else
  81.                                     hiTail.next = e; //高位链表尾部增加当前元素，以保持原链表顺序
  82.                                 hiTail = e; //更新高位链表的尾部
  83.                             }
  84.                         } while ((e = next) != null);
  85.                         //更新两个链表到哈希表中
  86.                         if (loTail != null) { //扩容后低位链表不为空，需要处理
  87.                             loTail.next = null; //低位链表设置尾部结束
  88.                             newTab[j] = loHead; //哈希桶设置链表入口
  89.                         }
  90.                         if (hiTail != null) { //扩容后高位链表不为空，需要处理
  91.                             hiTail.next = null; //高位链表设置尾部结束
  92.                             newTab[j + oldCap] = hiHead; //哈希桶设置链表入口
  93.                         }
  94.                     }
  95.                 }
  96.             }
  97.         }
  98.         return newTab;
  99.     }

3.get方法（返回指定键所映射的值）

  1.     public V get(Object key) {
  2.       Node<K, V> e;
  3.       return (e = getNode(hash(key), key)) == null ? null : e.value;
  4.     }
  6.     final Node<K, V> getNode(int hash, Object key) {
  7.         Node<K, V>[] tab;
  8.         Node<K, V> first, e;
  9.         int n;
  10.         K k;
  11.         // table已经初始化，长度大于0，根据hash寻找table中的项也不为空
  12.         if ((tab = table) != null && (n = tab.length) > 0 &&
  13.                 (first = tab[(n - 1) & hash]) != null) {
  14.             // 桶中第一项(数组元素)相等
  15.             if (first.hash == hash && // always check first node
  16.                     ((k = first.key) == key || (key != null && key.equals(k))))
  17.                 return first;
  18.             // 桶中不止一个结点
  19.             if ((e = first.next) != null) {
  20.                 // 为红黑树结点
  21.                 if (first instanceof TreeNode)
  22.                     // 在红黑树中查找
  23.                     return ((TreeNode<K, V>) first).getTreeNode(hash, key);
  24.                 // 否则，在链表中查找
  25.                 do {
  26.                     if (e.hash == hash &&
  27.                             ((k = e.key) == key || (key != null && key.equals(k))))
  28.                         return e;
  29.                 } while ((e = e.next) != null);
  30.             }
  31.         }
  32.         return null;
  33.     }
  35.     final TreeNode<K, V> getTreeNode(int h, Object k) {
  36.         //找到红黑树的根节点并遍历红黑树
  37.         return ((parent != null) ? root() : this).find(h, k, null);
  38.     }
  40.     //找到从根p开始的节点和给定的散列和键。kc参数在第一次使用比较键时缓存了comparableClassFor。
  41.     final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
  42.         TreeNode<K, V> p = this;
  43.         do {
  44.             int ph, dir;
  45.             K pk;
  46.             TreeNode<K, V> pl = p.left, pr = p.right, q;
  47.             if ((ph = p.hash) > h)
  48.                 p = pl;
  49.             else if (ph < h)
  50.                 p = pr;
  51.             else if ((pk = p.key) == k || (k != null && k.equals(pk)))
  52.                 return p;
  53.             else if (pl == null)
  54.                 p = pr;
  55.             else if (pr == null)
  56.                 p = pl;
  57.             else if ((kc != null ||
  58.                     (kc = comparableClassFor(k)) != null) &&
  59.                     (dir = compareComparables(kc, k, pk)) != 0)
  60.                 p = (dir < 0) ? pl : pr;
  61.             else if ((q = pr.find(h, k, kc)) != null)
  62.                 return q;
  63.             else
  64.                 p = pl;
  65.         } while (p != null);
  66.         return null;
  67.     }

4.treeifyBin方法（将容器中的node变为treeNode）

  1.     final void treeifyBin(Node<K, V>[] tab, int hash) {
  2.         int n, index;
  3.         Node<K, V> e;
  4.         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  5.             resize();
  6.             //Node e=tab[该hash对应的角标]，e就是这个角标下的第一个元素。  
  7.         else if ((e = tab[index = (n - 1) & hash]) != null) {
  8.             TreeNode<K, V> hd = null, tl = null;
  9.             do {
  10.                 //replacementTreeNode == new TreeNode(),就是包装了一个TreeNode对象  
  11.                 TreeNode<K, V> p = replacementTreeNode(e, null);
  12.                 if (tl == null)
  13.                     //遍历链表上的第一个元素的时候，t1==null，将p赋值给hd  
  14.                     //也就是先记录一下，方便后面的元素记录pre，next  
  15.                     hd = p;
  16.                 else {
  17.                     //现在p是个tree了，pre记录上一个元素  
  18.                     p.prev = tl;
  19.                     //顺便把自己的引用在上一个元素上做记录  
  20.                     tl.next = p;
  21.                 }
  22.                 //将当前操作的元素的引用传递给t1  
  23.                 tl = p;
  24.                 //遍历整个链表，直到没有元素。  
  25.             } while ((e = e.next) != null);
  26.             if ((tab[index] = hd) != null)
  27.                 //遍历完了，再执行hd.treeify方法  
  28.                 //hd=p是在t1==null时执行，也就是只有在第一个元素的时候执行了一次  
  29.                 //所以hd代表的是这个树的根。  
  30.                 hd.treeify(tab);
  31.         }
  32.     }

5.remove方法（移除指定键的映射关系）

  1.     public V remove(Object key) {
  2.         Node<K, V> e;
  3.         return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
  4.     }
  6.     final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
  7.         Node<K, V>[] tab;
  8.         Node<K, V> p;
  9.         int n, index;
  10.         if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
  11.             Node<K, V> node = null, e;
  12.             K k;
  13.             V v;
  14.             // 直接命中
  15.             if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
  16.                 node = p;
  17.             else if ((e = p.next) != null) {
  18.                 // 红黑树中查找
  19.                 if (p instanceof TreeNode)
  20.                     node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
  21.                 else {
  22.                     // 链表中查找
  23.                     do {
  24.                         if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
  25.                             node = e;
  26.                             break;
  27.                         }
  28.                         p = e;
  29.                     } while ((e = e.next) != null);
  30.                 }
  31.             }
  32.             // 命中后删除
  33.             if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
  34.                 if (node instanceof TreeNode)
  35.                     ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
  36.                 else if (node == p)
  37.                     tab[index] = node.next;  // 链表首元素删除
  38.                 else
  39.                     p.next = node.next;  //多元素链表节点删除
  40.                 ++modCount;
  41.                 --size;
  42.                 afterNodeRemoval(node);
  43.                 return node;
  44.             }
  45.         }
  46.         return null;
  47.     }

hashmap为什么是线程不安全的

  • 多线程环境put的时候导致的数据不一致问题
    这个问题比较好想象，比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。下面是一个简单的例子
  1. public class Test {
  3.     private static final Map<String, String> hashMap = new HashMap<>();
  5.     public static void main(String[] args) {
  7.         Thread t1 = new Thread(() -> {
  8.             for (int i = 0; i < 25; i++) {
  9.                 hashMap.put(i + "", i + "");
  10.             }
  11.         });
  13.         Thread t2 = new Thread(() -> {
  14.             for (int i = 25; i < 50; i++) {
  15.                 hashMap.put(i + "", i + "");
  16.             }
  17.         });
  19.         t1.start();
  20.         t2.start();
  21.         try {
  22.             Thread.sleep(1000);
  23.         } catch (InterruptedException e) {
  24.             e.printStackTrace();
  25.         }
  27.         for (int i = 0; i < 50; i++) {
  28.             System.out.println(i + "/" + hashMap.get(i + ""));
  29.         }
  30.     }
  32. }

结果如下

  1.     0/0
  2.     1/1
  3.     2/2
  4.     3/3
  5.     4/4
  6.     5/null
  7.     6/6
  8.     7/7
  9.     8/8
  10.     9/9
  11.     10/10
  12.     11/null
  13.     12/12
  14.     13/13
  15.     14/14
  16.     15/null
  17.     16/16
  18.     17/17
  19.     18/18
  20.     19/19
  21.     20/20
  22.     21/21
  23.     22/22
  24.     23/23
  25.     24/24
  26.     25/25
  27.     26/null
  28.     27/27
  29.     28/28
  30.     29/29
  31.     30/30
  32.     31/31
  33.     32/32
  34.     33/null
  35.     34/34
  36.     35/35
  37.     36/36
  38.     37/37
  39.     38/null
  40.     39/39
  41.     40/40
  42.     41/41
  43.     42/42
  44.     43/43
  45.     44/44
  46.     45/45
  47.     46/46
  48.     47/47
  49.     48/48
  50.     49/49

JDK8 如何修复多线程扩容Bug

源码分析上面有

  • JDK8 中Node[] resize()每次扩容哈希表大小都增倍特性，每次扩容，一个哈希桶里的元素在扩容后的位置，只会是原位置，或者原位置+原哈希表。
  • 扩容后，原来哈希桶的链表被拆分为两个，两个链表中的元素都能继续维持原有的顺序。这样就算在多线程环境下同时扩容，一个线程A读取链表状态后停止工作，另一个线程B对同一链表的前几个元素进行扩容分成两个链表，此时线程A恢复工作，由于线程B对链表元素的顺序没有发生变化，所以线程A恢复工作后只是重复了拆分链表的工作，而不会因为链表已被改变顺序而导致环的生成，因此不会发生死循环的问题。
  • 也就是说 JDK8 的HashMap扩容方法不但效率提升了（根据哈希值特点拆分链表，红黑树），而且还维持了扩容前后的链表顺序，从而解决了多线程扩容使链表产生环，导致死循环的问题。