[数据结构与算法] HashMap

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> HashMap -> 正文阅读

[数据结构与算法]HashMap

1 `HashMap`的数据结构

HashMap就是以key-value的方式进行数据存储的一种数据结构，在JDK 1.7中，HashMap的底层数据结构是数组+链表，使用Entry来存储key和value，在JDK 1.8中，HashMap的底层数据结构是数组+链表/红黑树，使用Node存储key和value。（Entry和Node并没有什么不同）。

HashMap

其中，桶数组是用来存储数据元素的，链表是用来解决冲突的，红黑树是为了提高查询效率。

根据key的hash值计算出数据元素在数组中的索引；
如果发生hash冲突，从冲突的位置添加一个链表，插入冲突的元素；
如果链表长度 > 8 & 数组大小 >= 64，链表转为红黑树；
如果红黑树节点个数 < 6，转为链表；

Hash（散列函数）：把任意长度的输入通过散列算法变换成固定长度的输出，输出的就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不能从散列值来确定唯一的输入值。

什么是红黑树，为什么不用平衡树/二叉树呢？

红黑树

红黑树本质上是一种二叉查找树，为了保持平衡，它在二叉树的基础上增加了一些规则：

每个节点要么是红色，要么是黑色；
根结点永远是黑色；
所有的叶子结点都是黑色，这里所说的叶子结点就是图中的NULL节点；
每个红色节点的两个子节点一定都是黑色的；
从任一节点到其子树中每个叶子结点的路径都包含相同数量的黑色节点；

这些约束强制了红黑树的关键性质：从根节点到叶子节点的最长的可能路径不多于最短的可能路径的两倍，结果是这个数大致上是平衡的，因为操作比如插入、删除和查找某个值的最坏情况事件都要与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏的情况下都是高效的，而不同于普通的二叉查找树。

红黑树是一种平衡的二叉树，插入、删除、查找最坏的时间复杂度都是O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。而平衡二叉树是比红黑树更严格的平衡树，为了保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

红黑树是怎么保持平衡的？红黑树有两种范式保持平衡：旋转和染色

2 `JDK 1.8`中的`HashMap`

在JDK 1.8中使用名为table的数组存储所有的键值对：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
  transient Node<K,V>[] table;

  static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // 下一个节点

    Node(int hash, K key, V value, Node<K,V> next) {
      this.hash = hash;
      this.key = key;
      this.value = value;
      this.next = next;
    }
  }
}

每个节点都会保存自身的hash、key、value以及下个节点next：

HashMap示意图

在进行数据插入（put）时，会使用哈希函数计算出key的hash值，根据hash来确定元素在桶数组的位置。比如计算出的结果是2：

插入元素

采用链表的形式是因为数组的长度是有限的，在有限的数组上使用哈希函数计算索引值，哈希冲突是无法避免的，很有可能有多个元素计算出的索引值是相同的，这个时候是如何解决哈希冲突呢？—— 拉链法，就是把哈希后值相同的元素放在同一条链表上：

hash冲突

**这里就会有一个问题，就是hash严重冲突时，在数组上形成的链表就会变得越来越长，由于链表不支持索引，想要在链表中找到某个元素就需要遍历一遍链表，效率比较低。为此，JDK 1.8中引入了红黑树，当链表的长度大于8并且数组长度大于等于64的时候就会转化成红黑树，如果数组的长度是小于64，HashMap会优先对数组进行扩容resize，而不是把链表转换成红黑树，**以下是JDK 1.8的HashMap的完整示意图：

![JDK 1.8 HashMap](https://img-blog.csdnimg.cn/382386938fff44b68dd71e28706a09ef.png#pic_center =60%x60%#pic_center =60%x60%)

以下是HashMap.put方法的相关源码：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

  public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true); // put方法直接调用putVal方法
  }
  
  static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 进行一次高低位的异或运算，key呈散列状态
  }

  final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1. 判断数组是否为空，如果为空则进行扩容操作
    if ((tab = table) == null || (n = tab.length) == 0) 
      n = (tab = resize()).length;
    // 2. 根据数组的长度(n-1)与key的hash值进行与运算，得出在数组中的索引，如果索引制定的位置为null，直接插入节点
    if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newNode(hash, key, value, null); 
    else {
      Node<K,V> e; K k;
      // 3. 如果当前key存在，则进行替换操作
      if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
      // 4. 如果出现hash冲突的节点是树类型，则在树中追加新的节点
      else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
      // 5. 如果出现hash冲突的节点是链表节点
      else {
        for (int binCount = 0; ; ++binCount) {
          // 6.如果出现hash冲突的节点的下一个节点为空，则将新节点直接放到下一个节点
          if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            // 7. 节点插入后判断当前链表的长度是否超过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;
        }
      }
      // 10. 如果替换成功，则返回旧的value
      if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
          e.value = value;
        afterNodeAccess(e);
        return oldValue;
      }
    }
    ++modCount;
    // 7 所有元素处理完成后，判断是否超过阈值，超过就进行扩容
    if (++size > threshold)
      resize();
    afterNodeInsertion(evict);
    return null;
  }
  
  final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 8. 如果链表的长度大于等于8，但数组的长度还小于64，那么进行扩容操作
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
      resize();
    // 9. 如果链表的长度大于等于8，且数组的长度大于等于64，则进行链表到红黑树的转换
    else if ((e = tab[index = (n - 1) & hash]) != null) {
      TreeNode<K,V> hd = null, tl = null;
      do {
        TreeNode<K,V> p = replacementTreeNode(e, null);
        if (tl == null)
          hd = p;
        else {
          p.prev = tl;
          tl.next = p;
        }
        tl = p;
      } while ((e = e.next) != null);
      if ((tab[index] = hd) != null)
        hd.treeify(tab);
    }
  }
}

首先判断数组是否为空，如果是空，则进行数组扩容；
根据key的hash值计算出元素在数组中的索引，如果索引指定的位置为空，则直接插入一个节点；
如果索引所在的位置不为空，则判断当前的key是否存在，如果存在则进行替换；如果key不存在，说明数组的索引位置已经有元素，这个时候就出现了hash冲突；
判断当前节点是否是树类型，如果是树类型的话，则按照树的操作添加节点；如果是链表节点，则进入循环，找到下一个节点为空的节点，并将新节点插入；
插入节点后判断，当前链表上的元素个数是否超过了8，如果是，则判断当前数组的长度是否小于64，如果是，则进行扩容操作；如果数组的长度大于等于64则进行链表到树的转换，并插入节点；
最后，进行容量判断，如果超过阈值，则进行扩容；

以下是流程图：

HashMap.put

数组容量是有限的，如果数据多次插入并达到一定的数量就会进行数组扩容（resize）。什么时候会进行resize呢？与两个因素有关：

Capacity：HashMap当前最大容量/长度；
LoadFactory：负载因子，默认值是0.75f；

capacity [k??p?s?ti] 容积；生产量，生产能力

**如果当前存入的数据量大于Capacity * LoadFactory的时候，就会进行数组扩容。**就比如当前的HashMap的最大容量为100，当要存入第76的元素的时候，判断发现需要进行扩容了。

以下是HashMap.get的相关源码：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
  public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
  }

  final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 1. 如果数组不为null，且数组的长度大于0，且数组对应的索引的节点不为空
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
      // 2. 首先和第一个节点比较，key的hash值和第一个节点的hash值相等，且key的地址或值相等，则返回第一个节点
      if (first.hash == hash && // always check first node
          ((k = first.key) == key || (key != null && key.equals(k))))
        return first;
      // 3. 如果key和第一个节点不匹配，则看first.next是否为空，如果不为空则继续比较
      if ((e = first.next) != null) {
        // 4. 如果是红黑树的结构，则进行处理树节点的搜索
        if (first instanceof TreeNode)
          return ((TreeNode<K,V>)first).getTreeNode(hash, key);
        do {
          // 5. 如果是链表结构，则继续遍历查询
          if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
        } while ((e = e.next) != null);
      }
    }
    return null;
  }
}

首先根据key的hash值计算出元素在数组中的索引；
如果数组不为空且长度大于0且第一个节点不为空，则进入查找流程；
首先key的hash值和第一个节点的hash值比较，之后再通过==和equals方法比较key是否相等；如果相等则返回第一个节点；
如果第一个节点不符合查找条件，则判断第二个节点，如果是树节点，则按照红黑树的结构执行相应的查询；如果是链表结构则按照链表的结构执行相应的查询；

以下是流程图：

HashMap get

3 `JDK 1.7`中的`HashMap`

在JDK 1.7中，新节点在插入链表的时候，是怎么插入的？—— 头插法：

头插法

在JDK 1.8中改用了尾插法，这是因为，采用头插法在多线程环境下可能会造成循环链表问题。

头插法：

头插法

如果进行扩容：

HashMap进行扩容后，假设节点A、B、C经过Hash后得到的数值依然相同，在新的HashMap中顺序是C->B->A。

死循环是因为并发HashMap扩容导致的，并发扩容的第一步，线程T1和线程T2要对HashMap进行扩容，此时T1和T2指向的是链表的头节点元素A，而T1和T2指向的是链表的头节点A，而T1和T2的下一个节点，也就是T1.next和T2.next指向的是B节点，如下所示：

旧HashMap

如果此时线程T2时间片用完进入休眠钟头，而线程T1开始执行扩容操作，一直到线程T1扩容完成后，线程T2才背唤醒，扩容之后的场景是：

从上图中可以看到线程T1执行之后，因为都是头插法，所以HashMap的顺序已经发生了改变，但线程T2对于发生的一切是不可知的，所以它指向的元素依然没有变化，T2指向的是A元素，T2.next指向的节点是B元素。

当线程T1执行完毕后，线程T2恢复执行时，死循环就建立了，如下所示：

死循环

4 `JDK 1.7`中的`HashMap`和`JDK 1.8`中的`HashMap`

HashMap线程不安全的表现有哪些？在JDK 1.7的HashMap的线程不安全是因为会出现环形链表。虽然JDK 1.8采用尾插法避免了环形链表的问题，但是它仍然是不安全的。比如说HashMap.put的源码：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

  public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
  }

  final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
      n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newNode(hash, key, value, null); // --> 1
    else {
      Node<K,V> e; K k;
      if (p.hash == hash &&
          ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
      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);
            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;
        }
      }
      if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
          e.value = value;
        afterNodeAccess(e);
        return oldValue;
      }
    }
    ++modCount;
    if (++size > threshold)
      resize();
    afterNodeInsertion(evict);
    return null;
  }
}

在注释1处如果没有发生hash冲突就会直接插入元素。假设线程1和线程2同时进行put操作，恰好这两条不数据的hash值是一样的，并且该位置数据为null这样线程1和线程2都会进入这段代码进行插入元素。假设线程1进入后还没有开始进行元素插入就被挂起，而线程2正常执行，并且正常插入数据，随后线程1得到CPU调度后进行元素插入，这样，线程2插入的数据就被覆盖了。

总结一下：

多线程下扩容死循环。JDK 1.7中的HashMap使用头插法插入元素，在多线程的环境下，扩容的时候可能会导致环形链表的出现，形成死循环。因此，JDK 1.8使用尾插法插入元素，在扩容时会保持链表元素的原本顺序，不会出现环形链表的问题；
多线程的put操作可能导致元素的丢失。多线程同时put，如果计算出的索引位置时相同的，可能会造成前一个key被后一个key覆盖，从而导致元素的丢失。此问题在JDK 1.7和JDK 1,8中都存在；
put和get并发时，可能导致get为null。线程1执行put时，因为元素的个数查过threshold而导致rehash，线程2此时执行get，有可能导致这个问题。这个问题在JDK 1.7和JDK 1.8中都存在；

如何保证HashMap线程安全？Java中有HashTable、Collections.synchronizedMap以及ConcurrentMap可以实现线程安全的Map：

HashTable是直接在操作方法上加synchronized关键字；
使用Collections.synchronizedMap包装一下HashMap，得到线程安全的HashMap，其原理就是对所有的修都加上synchronized；
使用线程安全的ConcurrentHashMap，该类在JDK 1.7和JDK 1.8的底层原理有所不同，JDK 1.7采用数组+链表，使用分段锁Segment（Segment继承自ReentrantLock）保证线程安全；JDK 1.8采用的是数组+链表/红黑树存储数据，使用CAS（内存位置、预期原职、新值，如果内存位置的值与预期原址相匹配，那么处理器会更新为新值）+synchronized保证线程安全；

concurrent [k?n?k??r?nt] （两个或两个以上徒刑判决）同时执行的 segment [?seɡm?nt] 部分，片段

以下是JDK 1.7中的ConcurrentHashMap的相关流程：

Segment

整个流程和HashMap非常类似，只不过是先定位到具体的Segment，然后通过ReentrantLock去操作而已，后面的流程，就和HashMap基本上是一样的：

计算hash，定位到segment，segment如果是空就先初始化；
使用ReentrantLock加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获取锁成功；
遍历HashEntry，就是和HashMap一样，数组中key和hash一样就直接替换，不存在就再插入链表，链表同样操作

JDK 1,7 分段锁

以下是JDK 1.8中的ConcurrentHashMap.put流程：

CAS+synchronized

JDK 1.8对HashMap做了哪些优化？

数据结构：数组+链表改成了数组+链表/红黑树，这是因为发生了hash冲突，元素会存入链表，链表过长转为红黑树，将查询元素的时间复杂度由O(n)降低为O(logn)；
链表插入方式从头插法改为尾插法，这是因为JDK 1.7扩容时，头插法会发生链表反转，多线程的环境下会产生环形链表；
扩容：扩容时，JDK 1.7需要对原数组中的元素重新进行hash定位新数组中的位置，JDK 1.8采用更简单的判断逻辑，不需要重新hash计算位置，新的位置不变或索引+新增容量大小。原因是，提高扩容的效率，更快扩容；
扩容机制：在插入时，JDK 1.7先判断是否需要扩容，再插入，JDK 1.8先进性插入，插入后再判断是否需要扩容；
哈希/散列/扰动函数：JDK 1.7做了四次位移和四次异或，JDK 1.8做了一次，原因是做4次，边际效用也不大，改为1次提升效率；

扩容（resize）分为两步：

扩容：创建一个新的Entry/Node空数组，长度是原数组的2倍；
rehash(JDK 1.7)：遍历原Entry/Node数组，把所有的Entry/Node节点重新hash到新数组；

参考

https://baijiahao.baidu.com/s?id=1712744857260389238&wfr=spider&for=pc
https://baijiahao.baidu.com/s?id=1722255125227536994&wfr=spider&for=pc
https://developer.51cto.com/article/699495.html
https://blog.csdn.net/weixin_48286142/article/details/124251482
https://blog.csdn.net/qq_45369827/article/details/114935265