HashMap

前言

HashMap是我们日常开发中经常遇到的一种数据结构，其内部存储采用K,V的形式存储数据，随着JDK的升级，在1.8之后对其进行了优化，例如引入了红黑树和扩容优化等。

数组

数组是一类数据类型的数据的集合，相当于一个容器，容器中的数据都是相同的数据类型，下图为一个int类型的数组

数组因为其结构特性，查找数据时只需要用下标去相应的位置取就可以，效率高，但其添加和删除操作受其空间复杂度影响，每次删除添加都要进行移位，效率不高

链表

链表是一种物理存储上的非连续、非顺序的存储结构，其逻辑顺序是依靠其指针建立的，其结构是由一个个的Node节点构成

这是单链表的结构，双向链表在此基础上加了一个prev指针，指向前一个元素，从而构成双向 从图中我们可以看出，在链表中添加和删除数据，我们只需断开当前连接，然后改变指针就可以了，所以在添加和删除数据的时候简单；但因为其链式结构，我们查找的时候，需要从第一个节点开始遍历，直到找出当前数据才能结束，因此其查找速度没有数组快

HashMap 1.7

在JDK1.7时的HashMap采用数组+链表的结构 在存储时，会先根据key的hashcode通过hash算法得到hash值，再经过过 (n - 1) & hash得到其在数组中的下标，然后在该下标处添加元素，但是有时候两个元素他们的下标值会有相同的情况，这时先判断这两个元素的hash和key是否相同，如果相同直接覆盖，如果不相同，就会产生hash碰撞,此时采用拉链法来解决，1.7采用的是头插法，最终会形成如下结构

头插法，就是将新添加的元素放在链表的首位，然后整个链表向后移位的操作

在1.7中的hashmap并发环境下Rehash会发生死循环问题

HashMap 1.8

在JDK1.8后，HashMap引入了红黑树，当链表的长度大于阈值8的时候，会先尝试扩容数组，如果数组长度小于64，会先扩容数组，如果大于64，则转化为红黑树

HashMap的put方法

hashmap的put方法，先根据key的hash值经过扰动函数处理后获取索引值，然后放入

1
2
3
4
public V put(K key, V value) {
       //先根据key，取得hash值。 再调用上一节的方法插入节点
       return putVal(hash(key), key, value, false, true);
   }
1
2
3
4
5
//扰动函数
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

以下是put的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //tab存放 当前的哈希桶， p用作临时链表节点  
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果当前哈希表是空的，代表是初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            //那么直接去扩容哈希表，并且将扩容后的哈希桶长度赋值给n
            n = (tab = resize()).length;
        //如果当前index的节点是空的，表示没有发生哈希碰撞。 直接构建一个新节点Node，挂载在index处即可。
        //这里再啰嗦一下，index 是利用 哈希值 & 哈希桶的长度-1，替代模运算
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {//否则 发生了哈希冲突。
            //e
            Node<K,V> e; K k;
            //如果哈希值相等，key也相等，则是覆盖value操作
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;//将当前节点引用赋值给e
            else if (p instanceof TreeNode)//红黑树暂且不谈
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//不是覆盖操作，则插入一个普通链表节点
                //遍历链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {//遍历到尾部，追加新节点到尾部
                        p.next = newNode(hash, key, value, null);
                        //如果追加节点后，链表数量》=8，则转化为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果找到了要覆盖的节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //如果e不是null，说明有需要覆盖的节点，
            if (e != null) { // existing mapping for key
                //则覆盖节点值，并返回原oldValue
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                //这是一个空实现的函数，用作LinkedHashMap重写使用。
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null。

        //修改modCount
        ++modCount;
        //更新size，并判断是否需要扩容。
        if (++size > threshold)
            resize();
        //这是一个空实现的函数，用作LinkedHashMap重写使用。
        afterNodeInsertion(evict);
        return null;
    }

这是hashmap这个put过程

HashMap的get方法

get与put方法相似，都要先通过key的hash和key，然后去节点中查询

1
2
3
4
5
public V get(Object key) {
       Node<K,V> e;
       //传入扰动后的哈希值 和 key 找到目标节点Node
       return (e = getNode(hash(key), key)) == null ? null : e.value;
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//传入扰动后的哈希值 和 key 找到目标节点Node
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //查找过程和删除基本差不多， 找到返回节点，否则返回null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

getNode 方法会根据key的hash和key，先去首节点判断是不是当前元素，是的话就直接返回，首节点有next元素就要去遍历查找链表

HashMap的扩容

什么情况下会发生扩容

1、当往hashmap中put第一个数据的时候

2、当hashmap中的元素个数大于阈值（12）时

在扩容后，产生的新数组是原来的两倍，并且其阈值是新数组的容量乘负载因子

在扩容后，会将数据从原来的数组中复制到扩容后的数组中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
final Node<K,V>[] resize() {
      //oldTab 为当前表的哈希桶
      Node<K,V>[] oldTab = table;
      //当前哈希桶的容量 length
      int oldCap = (oldTab == null) ? 0 : oldTab.length;
      //当前的阈值
      int oldThr = threshold;
      //初始化新的容量和阈值为0
      int newCap, newThr = 0;
      //如果当前容量大于0
      if (oldCap > 0) {
          //如果当前容量已经到达上限
          if (oldCap >= MAXIMUM_CAPACITY) {
              //则设置阈值是2的31次方-1
              threshold = Integer.MAX_VALUE;
              //同时返回当前的哈希桶，不再扩容
              return oldTab;
          }//否则新的容量为旧的容量的两倍。 
          else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                   oldCap >= DEFAULT_INITIAL_CAPACITY)//如果旧的容量大于等于默认初始容量16
              //那么新的阈值也等于旧的阈值的两倍
              newThr = oldThr << 1; // double threshold
      }//如果当前表是空的，但是有阈值。代表是初始化时指定了容量、阈值的情况
      else if (oldThr > 0) // initial capacity was placed in threshold
          newCap = oldThr;//那么新表的容量就等于旧的阈值
      else {}//如果当前表是空的，而且也没有阈值。代表是初始化时没有任何容量/阈值参数的情况               // zero initial threshold signifies using defaults
          newCap = DEFAULT_INITIAL_CAPACITY;//此时新表的容量为默认的容量 16
          newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//新的阈值为默认容量16 * 默认加载因子0.75f = 12
      }
      if (newThr == 0) {//如果新的阈值是0，对应的是  当前表是空的，但是有阈值的情况
          float ft = (float)newCap * loadFactor;//根据新表容量 和 加载因子 求出新的阈值
          //进行越界修复
          newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
      }
      //更新阈值 
      threshold = newThr;
      @SuppressWarnings({"rawtypes","unchecked"})
      //根据新的容量 构建新的哈希桶
          Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
      //更新哈希桶引用
      table = newTab;
      //如果以前的哈希桶中有元素
      //下面开始将当前哈希桶中的所有节点转移到新的哈希桶中
      if (oldTab != null) {
          //遍历老的哈希桶
          for (int j = 0; j < oldCap; ++j) {
              //取出当前的节点 e
              Node<K,V> e;
              //如果当前桶中有元素,则将链表赋值给e
              if ((e = oldTab[j]) != null) {
                  //将原哈希桶置空以便GC
                  oldTab[j] = null;
                  //如果当前链表中就一个元素，（没有发生哈希碰撞）
                  if (e.next == null)
                      //直接将这个元素放置在新的哈希桶里。
                      //注意这里取下标 是用 哈希值 与 桶的长度-1 。 由于桶的长度是2的n次方，这么做其实是等于 一个模运算。但是效率更高
                      newTab[e.hash & (newCap - 1)] = e;
                      //如果发生过哈希碰撞 ,而且是节点数超过8个，转化成了红黑树（暂且不谈 避免过于复杂， 后续专门研究一下红黑树）
                  else if (e instanceof TreeNode)
                      ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                  //如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。
                  else { // preserve order
                      //因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位， 或者扩容后的下标，即high位。 high位=  low位+原哈希桶容量
                      //低位链表的头结点、尾节点
                      Node<K,V> loHead = null, loTail = null;
                      //高位链表的头节点、尾节点
                      Node<K,V> hiHead = null, hiTail = null;
                      Node<K,V> next;//临时节点 存放e的下一个节点
                      do {
                          next = e.next;
                          //这里又是一个利用位运算 代替常规运算的高效点： 利用哈希值 与 旧的容量，可以得到哈希值去模后，是大于等于oldCap还是小于oldCap，等于0代表小于oldCap，应该存放在低位，否则存放在高位
                          if ((e.hash & oldCap) == 0) {
                              //给头尾节点指针赋值
                              if (loTail == null)
                                  loHead = e;
                              else
                                  loTail.next = e;
                              loTail = e;
                          }//高位也是相同的逻辑
                          else {
                              if (hiTail == null)
                                  hiHead = e;
                              else
                                  hiTail.next = e;
                              hiTail = e;
                          }//循环直到链表结束
                      } while ((e = next) != null);
                      //将低位链表存放在原index处，
                      if (loTail != null) {
                          loTail.next = null;
                          newTab[j] = loHead;
                      }
                      //将高位链表存放在新index处
                      if (hiTail != null) {
                          hiTail.next = null;
                          newTab[j + oldCap] = hiHead;
                      }
                  }
              }
          }
      }
      return newTab;
  }

小结：

  • 运算尽量都用位运算代替，更高效。
  • 对于扩容导致需要新建数组存放更多元素时，除了要将老数组中的元素迁移过来，也记得将老数组中的引用置null，以便GC
  • 取下标 是用 哈希值 与运算 （桶的长度-1） i = (n - 1) & hash。 由于桶的长度是2的n次方，这么做其实是等于 一个模运算。但是效率更高
  • 扩容时，如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。
  • 因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位， 或者扩容后的下标，即high位。 high位= low位+原哈希桶容量
  • 利用哈希值 与运算 旧的容量 ，if ((e.hash & oldCap) == 0),可以得到哈希值去模后，是大于等于oldCap还是小于oldCap，等于0代表小于oldCap，应该存放在低位，否则存放在高位。这里又是一个利用位运算 代替常规运算的高效点
  • 如果追加节点后，链表数量》=8，则转化为红黑树
  • 插入节点操作时，有一些空实现的函数，用作LinkedHashMap重写使用。