title: 【学习之路】HashMap源码分析
draft: true
tags:

JDK7底层实现

  • 在实列化以后，底层创建了一个长度是16的一维数组Entry[] table

HashMap - 图1

  • 当调用put()方法之后首先会调用当前key所在类的hashCode()方法计算key的hash值，通过计算以后，得到在Entry数组中的存放位置。
    如果此位置的上的数据为空，此时key-value添加成功
    如果此位置上的数据不为空（就意味着当前位置上存在一个或多个数据（以链表的形式存在）），比较key和已存在的一个或多个数据
    如果key的hash值与已经存在的数据的hash值都不相同，此时key-value添加成功
    如果key的hash值和已存在的某个数据hash值相同则调用当前key所在类的equals()方法继续比较
  1.             如果equals()返回false：此时key-value添加成功
  3.             如果equals()返回true：当前添加的key的value会替换已经添加的value

JDK8底层实现

  • new HashMap()：底层没有创建一个长度为16的数组

HashMap - 图2

  • jdk 8底层的数组是：Node[]，而非Entry[]

HashMap - 图3

  • 首次调用put()方法时候底层才会创建一个长度为16的数组

HashMap - 图4

HashMap - 图5

  • JDK7中的底层结构只有数组+链表。JDK8中底层结构：数组+链表+红黑树

当数组的某一个索引位置上的元素以链表的形式存在的个数大于8 且当前数组的长度 大于64时，此时索引位置上的所有数据修改为使用红黑树存储

源码解析

  1. public V put(K key, V value) {
  2.     // 先调用hash方法计算出当前key的hash值
  3.     return putVal(hash(key), key, value, false, true);
  4. }

hash值的计算过程

  1. static final int hash(Object key) {
  2.     int h;
  3.     /* 
  4.        判断当前key是否为空如果key为空那么hash值直接返回0，如果不为空,
  5.        调用当前key类型的hashCode方法(前提是当前类重写了hashCode)计算出来的hash值再进行无符号右移16后，
  6.        再进行异或运算减少hash碰撞 
  7.     */
  8.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  9. }

putVal()：key值的存储过程

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                boolean evict) {
  3.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  4.     // 初始化操作，判断当前table，数组是否为空或长度为0如果为true会使用resize()方法进行扩容
  5.     if ((tab = table) == null || (n = tab.length) == 0)
  6.         n = (tab = resize()).length;
  7.     // 判断当前数据存储所在位置，如果当前位置为空那么直接进行存储
  8.     if ((p = tab[i = (n - 1) & hash]) == null)
  9.         tab[i] = newNode(hash, key, value, null);
  10.     else {
  11.         Node<K,V> e; K k;
  12.         /* 
  13.         如果当前存储位置不为空，先判断当前需要存入key的hash值和当前位置已经存储key的hash值进行比较
  14.         如果两个hash值不相同if语句直接结束
  15.         如果两个hash值相同那么先判断已经存入的key和需要存入的key两个key地址是否相同
  16.         如果不相同就判断当前key是否为不为空，并且调用需要存入key的equals方法将已经存入key作为参数传入进行比较,
  17.         如果都为true，那么就代表当前key相同，将已经存入的key地址保存
  18.         */
  19.         if (p.hash == hash &&
  20.             ((k = p.key) == key || (key != null && key.equals(k))))
  21.             e = p;
  22.         // 如果上面的if条件不满足先判断当前p的对象是否为红黑树
  23.         else if (p instanceof TreeNode)
  24.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  25.         else {
  26.             // 判断当前位置下是否有更多链表元素
  27.             for (int binCount = 0; ; ++binCount) {
  28.                 // 如果p的next为空代表下面没有更多的元素，将需要存入的元素直接链接到已经存在元素的末尾
  29.                 if ((e = p.next) == null) {
  30.                     p.next = newNode(hash, key, value, null);
  31.                     // 判断当前链表是否大于等于8，如果是，那么就会进入方法让当前链表变为红黑树
  32.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  33.                         treeifyBin(tab, hash);
  34.                     break;
  35.                 }
  36.                 // 用来判断已经存入位置的下一个链表的hash值与equals()是否相同
  37.                 if (e.hash == hash &&
  38.                     ((k = e.key) == key || (key != null && key.equals(k))))
  39.                     break;
  40.                 p = e;
  41.             }
  42.         }
  43.         /* 
  44.           判断e是否不为空，进入当前if代表需要存入的key值已经存在，接下来会替换已经存入key的value
  45.         */
  46.         if (e != null) { // existing mapping for key
  47.             V oldValue = e.value;
  48.             if (!onlyIfAbsent || oldValue == null)
  49.                 e.value = value;
  50.             afterNodeAccess(e);
  51.             return oldValue;
  52.         }
  53.     }
  54.     ++modCount;
  55.     if (++size > threshold)
  56.         resize();
  57.     afterNodeInsertion(evict);
  58.     return null;
  59. }

一般为第一次添加数据时初始化过程，和红黑树形成后长度不足

  1. final Node<K,V>[] resize() {
  2.     Node<K,V>[] oldTab = table;
  3.     // 如果是第一次添加数据table值是null，先进性三目运算，把0赋给oldCap
  4.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  5.     // 如果是第一次添加数据也没有临界值，临界值是0
  6.     int oldThr = threshold;
  7.     int newCap, newThr = 0;
  8.     // 第一次添加数据oldCap是0所以这个if不会进入
  9.     if (oldCap > 0) {
  10.         if (oldCap >= MAXIMUM_CAPACITY) {
  11.             threshold = Integer.MAX_VALUE;
  12.             return oldTab;
  13.         }
  14.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  15.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  16.             newThr = oldThr << 1; // double threshold
  17.     }
  18.     // 第一次添加数据临界值也是0，if也不会进入
  19.     else if (oldThr > 0) // initial capacity was placed in threshold
  20.         newCap = oldThr;
  21.     else {               // zero initial threshold signifies using defaults
  22.         // 将DEFAULT_INITIAL_CAPACITY值给newCap，初始容量16
  23.         newCap = DEFAULT_INITIAL_CAPACITY;
  24.         // DEFAULT_LOAD_FACTOR加载因子为0.75 * 初始容量 16，newThr为12
  25.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  26.     }
  27.     // 判断临界点是否为0
  28.     if (newThr == 0) {
  29.         float ft = (float)newCap * loadFactor;
  30.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  31.                   (int)ft : Integer.MAX_VALUE);
  32.     }
  33.     // 临界值赋值
  34.     threshold = newThr;
  35.     @SuppressWarnings({"rawtypes","unchecked"})
  36.     // Node数组长度newCap第一次存入数据长度为16
  37.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  38.     // 将数组对象给table
  39.     table = newTab;
  40.     if (oldTab != null) {
  41.         for (int j = 0; j < oldCap; ++j) {
  42.             Node<K,V> e;
  43.             if ((e = oldTab[j]) != null) {
  44.                 oldTab[j] = null;
  45.                 if (e.next == null)
  46.                     newTab[e.hash & (newCap - 1)] = e;
  47.                 else if (e instanceof TreeNode)
  48.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  49.                 else { // preserve order
  50.                     Node<K,V> loHead = null, loTail = null;
  51.                     Node<K,V> hiHead = null, hiTail = null;
  52.                     Node<K,V> next;
  53.                     do {
  54.                         next = e.next;
  55.                         if ((e.hash & oldCap) == 0) {
  56.                             if (loTail == null)
  57.                                 loHead = e;
  58.                             else
  59.                                 loTail.next = e;
  60.                             loTail = e;
  61.                         }
  62.                         else {
  63.                             if (hiTail == null)
  64.                                 hiHead = e;
  65.                             else
  66.                                 hiTail.next = e;
  67.                             hiTail = e;
  68.                         }
  69.                     } while ((e = next) != null);
  70.                     if (loTail != null) {
  71.                         loTail.next = null;
  72.                         newTab[j] = loHead;
  73.                     }
  74.                     if (hiTail != null) {
  75.                         hiTail.next = null;
  76.                         newTab[j + oldCap] = hiHead;
  77.                     }
  78.                 }
  79.             }
  80.         }
  81.     }
  82.     return newTab;
  83. }

红黑树创建过程

  1. final void treeifyBin(Node<K,V>[] tab, int hash) {
  2.     int n, index; Node<K,V> e;
  3.     // 首先判断传入的当前数组是否为空，再判断当前数组长度是否大于64(MIN_TREEIFY_CAPACITY为64),
  4.     // 两个中有一个不满足就去扩容
  5.     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  6.         resize();
  7.     else if ((e = tab[index = (n - 1) & hash]) != null) {
  8.         TreeNode<K,V> hd = null, tl = null;
  9.         do {
  10.             TreeNode<K,V> p = replacementTreeNode(e, null);
  11.             if (tl == null)
  12.                 hd = p;
  13.             else {
  14.                 p.prev = tl;
  15.                 tl.next = p;
  16.             }
  17.             tl = p;
  18.         } while ((e = e.next) != null);
  19.         if ((tab[index] = hd) != null)
  20.             hd.treeify(tab);
  21.     }
  22. }

HashMap属性介绍

  1. // HashMap默认容量16
  2. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
  4. // HashMap最大支持容量
  5. static final int MAXIMUM_CAPACITY = 1 << 30;
  7. // HashMap默认加载因子
  8. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  10. // HashMap中链表最大长度默认值，大于该长度，转化为红黑树
  11. static final int TREEIFY_THRESHOLD = 8;
  13. // HashMap中红黑树存储小于该值那么转化为链表
  14. static final int UNTREEIFY_THRESHOLD = 6;
  16. // HashMap转化红黑树需要的数组长度，当数组长度大于该值并且链表长度大于8转化为红黑树
  17. static final int MIN_TREEIFY_CAPACITY = 64;
  19. // 存储元素的的数组
  20. transient Node<K,V>[] table;
  22. // 数组中HashMap键值对的数量
  23. transient int size;
  25. // 扩容的临界值，计算方式为 容量*填充因子
  26. int threshold;
  28. // 填充因子
  29. final float loadFactor;