HashMap 数据结构

ゝ一纸荒年。 2024-04-01 12:58 65阅读 0赞

**思维导图：**

![Image 1][]

### 1，HashMap [集合][Link 1]简介 ###

HashMap 基于哈希表的 Map 接口实现，是以 **key-value** 存储形式存在，即主要用来存放键值对。HashMap 的实现不是同步的，这意味着它不是[线程安全][Link 2]的。它的 key、value 都可以为 null。此外，HashMap 中的映射不是有序的。

JDK1.8 之前的 HashMap 由数组 + [链表][Link 3]组成的，数组是 HashMap 的主体，链表则是主要为了节解决**哈希碰撞** (两个对象调用的 hashCode 方法计算的哈希码值一致导致计算的数组索引值相同) 而存在的（“拉链法” 解决冲突）。

JDK1.8 之后在解决哈希冲突时有了较大的变化，当**链表长度大于阈值**（或者红黑树的边界值，默认为 8）并且当前**数组的长度大于 64** 时，此时此索引位置上的所有数据改为使用红黑树存储。

数组里面都是 key-value 的实例，在 JDK1.8 之前叫做 Entry，在 JDK1.8 之后叫做 Node。

![Image 1][]

key-value 实例

由于它的 key、value 都为 null，所以在插入的时候会根据 key 的 [hash][] 去计算一个 index 索引的值。计算索引的方法如下：

/**
     * 根据key求index的过程
     * 1,先用key求出hash值
     */
    static final int hash(Object key) {
        
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    //2,再用公式index = (n - 1) & hash（n是数组长度）
    int hash=hash(key);
    index=(n-1)&hash;

这里的 Hash 算法本质上就是三步：取 key 的 hashCode 值、高位运算、取模运算。

这样的话比如说 put(“A”, 王炸)，插入了 key 为 “A” 的元素，这时候通过上述公式计算出插入的位置 index，若 index 为 3 则结果如下（即 hash(“A”)=3）：

![Image 1][]

插入索引为 3 的结点

那么，HashMap 中的链表又是干什么用的呢？

大家都知道数组的长度是有限的，**在有限的长度里面使用哈希函数计算 index 的值时，很有可能插入的 k 值不同，但所产生的 hash 是相同的**（也叫做哈希碰撞），这也就是哈希函数存在一定的概率性。就像上面的 K 值为 A 的元素，如果再次插入一个 K 值为 a 的元素，很有可能所产生的 index 值也为 3，也就是即 hash(“a”)=3；那这就形成了链表，这种解决哈希碰撞的方法也叫做拉链法。

![Image 1][]

**当这个链表长度大于阈值 8 并且数组长度大于 64 则进行将链表变为红黑树。**

**补充：**

将链表转换成红黑树前会判断，**如果阈值大于 8，但是数组长度小 64，此时并不会将链表变为红黑树。而是选择进行数组扩容**\*\*。\*\*

这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡。同事数组长度小于 64 时，搜索时间相对快一些。所以综上所述为了提高性能和减少搜索时间，底层在阈值大于 8 并且数组长度大于 64 时，链表才转换为红黑树。具体可以参考 treeifyBin 方法。

当然虽然增了红黑树作为底层[数据结构][Link 4]，结构变得复杂了，但是阈值大于 8 并且数组长度大于 64 时，链表转换为红黑树时，效率也变得更高效。

**特点：**

1.  存取无序的
2.  键和值位置都可以是 null，但是键位置只能是一个 null
3.  键位置是唯一的，底层的数据结构控制键的
4.  jdk1.8 前数据结构是：链表 + 数组 jdk1.8 之后是 ：链表 + 数组 + 红黑树
5.  阈值 (边界值) > 8 并且数组长度大于 64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。

### 2，HsahMap 底层数据结构 ###

#### 2.1，HashMap 存储数据的过程 ####

![Image 1][]

每一个 Node 结点都包含**键值对的 key，value** 还有计算出来的 **hash 值**，还保存着下一个 **Node 的引用 next**（如果没有下一个 Node，next = null），来看看 Node 的源码：

static class Node<K,V> implements Map.Entry<K,V> {
        
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
            ...
       }

HashMap 存储数据需要用到 put() 方法，关于这些方法的详解，我们下节再说，这里简要说一下；

public static void main(String[] args) {
        
            HashMap<String,Integer> hmap=new HashMap<>();
            hmap.put("斑",55);
            hmap.put("镜",63);
            hmap.put("带土",25);
            hmap.put("鼬",9);
            hmap.put("佐助",43);
            hmap.put("斑",88);
            System.out.println(hmap);
        }

当创建 HashMap 集合对象的时候，在 jdk1.8 之前，构造方法中会创建很多**长度是 16 的 Entry\[\] table** 用来存储键值对数据的。在 jdk1.8 之后不是在 HashMap 的构造方法底层创建数组了，是在**第一次调用 put 方法**时创建的数组，**Node\[\] table** 用来存储键值对数据的。

> 比方说我们向哈希表中存储 “斑”-55 的数据，根据 K 值 (“斑”) 调用 String 类中重写之后的 hashCode()方法计算出值（数量级很大），然后结合数组长度采用取余（(n-1)&hash）操作或者其他操作方法来计算出向 Node 数组中存储数据的空间的索引值。如果计算出来的索引空间没有数据，则直接将 “斑”-55 数据存储到数组中。跟上面的 “A - 王炸” 数据差不多。

我们回到上方的数组图，如果此时再插入 “A - 蘑菇” 元素，那么首先根据 Key 值 (“A”) 调用 hashCode()方法结合数组长度计算出索引肯定也是 3，此时比较后存储的 “A - 蘑菇” 和已经存在的数据 “A - 王炸” 的 hash 值是否相等，如果 hash 相等，此时发生 hash 碰撞。

那么底层会调用 “A” 所属**类 String 中的 equals 方法**比较两个 key 内容是否相等，若相等，则后添加的数据直接覆盖已经存在的 Value，也就是 “蘑菇” 直接覆盖 “王炸”；若不相等，继续向下和其他数据的 key 进行比较，如果都不相等，则规划出一个节点存储数据。

![Image 1][]

两个结点 key 值比较，是否覆盖

#### 2.2，哈希碰撞相关的问题 ####

> 哈希表底层采用何种算法计算 hash 值？还有哪些算法可以计算出 hash 值？

底层是采用 key 的 hashCode 方法的值结合数组长度进行**无符号右移（>>>）**、按位异或（^）、按位与（&）计算出索引的

还可以采用：平方取中法，取余数，伪随机数法。这三种效率都比较低。而无符号右移 16 位异或运算效率是最高的。

> 当两个对象的 hashCode 相等时会怎么样？

会产生哈希碰撞，若 **key 值内容相同则替换旧的 value**. 否则连接到链表后面，**链表长度超过阈值 8** 就转换为红黑树存储。

> 何时发生哈希碰撞和什么是哈希碰撞, 如何解决哈希碰撞？

只要**两个元素的 key 计算的哈希值相同**就会发生哈希碰撞。jdk8 前使用链表解决哈希碰撞。jdk8 之后使用链表 + 红黑树解决哈希碰撞。

> 如果两个键的 hashcode 相同，如何存储键值对？

hashcode 相同，通过 equals 比较内容是否相同。**相同：则新的 value 覆盖之前的 value 不相同：则将新的键值对添加到哈希表中**

#### 2.3，红黑树结构 ####

当位于一个链表中的元素较多，即 hash 值相等但是内容不相等的元素较多时，通过 key 值依次查找的效率较低。而 jdk1.8 中，哈希表存储采用数组 + 链表 + 红黑树实现，当链表长度 (阀值) 超过 8 时且当前数组的长度 > 64 时，将链表转换为红黑树，这样大大减少了查找时间。jdk8 在哈希表中**引入红黑树的原因只是为了查找效率更高。**

![Image 1][]

红黑树结构

JDK 1.8 以前 HashMap 的实现是 数组 + 链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了 红黑树（**查找时间复杂度为 O(logn)**）来优化这个问题。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。

#### 2.4，存储流程图 ####

HashMap 存放数据是用的 put 方法，put 方法内部调用的是 putVal() 方法，所以对 put 方法的分析也是对 putVal 方法的分析，整个过程比较复杂，流程图如下：

!\[\]\[img-7\]

**来看看 put() 源码：**

public V put(K key, V value) {
        
        //对key的hashCode()做hash，调用的是putVal方法
            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;
            /*
               1，tab为空则开始创建，
               2，(tab = table) == null 表示将空的table赋值给tab,然后判断tab是否等于null，第一次肯定是null
               3，(n = tab.length) == 0 表示没有为table分配内存
               4，tab为空，执行代码 n = (tab = resize()).length; 进行扩容。并将初始化好的数组长度赋值给n.
               5，执行完n = (tab = resize()).length，数组tab每个空间都是null
            */
           
            if ((tab = table) == null || (n = tab.length) == 0)
                //调用resize()方法进行扩容
                n = (tab = resize()).length;
             /*
            1，i = (n - 1) & hash 表示计算数组的索引赋值给i，即确定元素存放在哪个桶中
            2，p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给节点p
            3，(p = tab[i = (n - 1) & hash]) == null 判断节点位置是否等于null，
             如果为null，则执行代码：tab[i] = newNode(hash, key, value, null);根据键值对创建新的节点放入该位置的桶中
            小结：如果当前桶没有哈希碰撞冲突，则直接把键值对插入空间位置
        */ 
            if ((p = tab[i = (n - 1) & hash]) == null)
                //节点位置为null，则直接进行插入操作
                tab[i] = newNode(hash, key, value, null);
            //节点位置不为null，表示这个位置已经有值了，于是需要进行比较hash值是否相等
            else {
        
                Node<K,V> e; K k;
                 /*
              比较桶中第一个元素(数组中的结点)的hash值和key是否相等
                   1，p.hash == hash 中的p.hash表示原来存在数据的hash值  hash表示后添加数据的hash值 比较两个hash值是否相等
                   2，(k = p.key) == key ：p.key获取原来数据的key赋值给k  key表示后添加数据的key 比较两个key的地址值是否相等
                   3，key != null && key.equals(k)：能够执行到这里说明两个key的地址值不相等，那么先判断后添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等
            */
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                     /*
                     说明：两个元素哈希值相等（哈希碰撞），并且key的值也相等
                     将旧的元素整体对象赋值给e，用e来记录
                    */ 
                    e = p;
                // hash值不相等或者key不相等；判断p是否为红黑树结点
                else if (p instanceof TreeNode)
                    // 是红黑树，调用树的插入方法
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                // 说明是链表节点，这时进行插入操作
                else {
        
                    /*
                    1，如果是链表的话需要遍历到最后节点然后插入
                    2，采用循环遍历的方式，判断链表中是否有重复的key
                    */
                    for (int binCount = 0; ; ++binCount) {
        
                        /*
                     1)e = p.next 获取p的下一个元素赋值给e
                     2)(e = p.next) == null 判断p.next是否等于null，等于null，说明p没有下一个元     素，那么此时到达了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键
                     将该键值对插入链表中
                    */
                        if ((e = p.next) == null) {
        
                            p.next = newNode(hash, key, value, null);
                            //插入后发现链表长度大于8，转换成红黑树结构
                            if (binCount >= TREEIFY_THRESHOLD - 1) 
                                //转换为红黑树
                                treeifyBin(tab, hash);
                            break;
                        }
                        //key值以及存在直接覆盖value
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                //若结点为null，则不进行插入操作
                if (e != null) {
         
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            //修改记录次数
            ++modCount;
            // 判断实际大小是否大于threshold阈值，如果超过则扩容
            if (++size > threshold)
                resize();
            // 插入后回调
            afterNodeInsertion(evict);
            return null;
        }

小结：

1.  根据哈希表中元素个数确定是**扩容还是树形化**
2.  如果是树形化遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系
3.  然后让桶中的第一个元素指向新创建的树根节点，替换桶的链表内容为树形化内容

### 3，HashMap 的扩容机制 ###

我们知道，数组的容量是有限的，多次插入数据的话，到达一定数量就会进行扩容；先来看两个问题

#### 什么时候需要扩容？ ####

当 HashMap 中的**元素个数超过数组长度 loadFactor(负载因子)** 时，就会进行数组扩容，loadFactor 的默认值是 0.75, 这是一个折中的取值。也就是说，默认情况下，数组大小为 16，那么当 HashMap 中的元素个数超过 16×0.75=12(这个值就是阈值) 的时候，就把数组的大小扩展为 2×16=32，即扩大一倍，然后**重新计算每个元素在数组中的位置**，而这是一个非常耗性能的操作，所以如果我们已经预知 HashMap 中元素的个数，那么预知元素的个数能够有效的提高 HashMap 的性能。

#### 怎么进行扩容的？ ####

HashMap 在进行扩容时使用 resize() 方法，计算 table 数组的新容量和 Node 在新数组中的新位置，将旧数组中的值复制到新数组中，从而实现自动扩容。因为每次扩容都是翻倍，与原来计算的 (n-1)&hash 的结果相比，只是多了一个 bit 位，所以节点要么就在原来的位置，要么就被分配到 " **原位置 + 旧容量** " 这个位置。

因此，我们在扩充 HashMap 的时候，不需要重新计算 hash，只需要看看原来 hash 值新增的那个 bit 是 1 还是 0 就可以了，是 0 的话索引没变，是 1 的话索引变成 “原索引 + oldCap(**原位置 + 旧容量**)”。这里不再详细赘述，可以看看下图为 16 扩充为 32 的 resize 示意图：

!\[\]\[img-8\]

hashmap 扩容

### 4，HashMap 数组长度为什么是 2 的次幂 ###

我们先看看它的成员变量：

#### 序列化版本号 ####

private static final long serialVersionUID = 362498820763181265L;

#### 集合的初始化容量 initCapacity ####

//默认的初始容量是16 -- 1<<4相当于1*2的4次方---1*16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

初始化容量默认是 16，容量过大，遍历时会减慢速度，效率低；容量过小，那么扩容的次数变多，非常耗费性能。

#### 负载因子 ####

/**
         * The load factor used when none specified in constructor.
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

初始默认值为 0.75，若过大，会导致哈希冲突的可能性更大；若过小，扩容的次数也会提高。

#### 为什么必须是 2 的 n 次幂？ ####

当向 HashMap 中添加一个元素的时候，需要根据 key 的 hash 值，去确定其在数组中的具体位置。HashMap 为了提高存取效率，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法。

这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算。所以源码中做了优化, 使用 `hash&(length-1)`，而实际上`hash%length`等于`hash&(length-1)`的前提是 length 是 2 的 n 次幂。

#### 如果输入值不是 2 的幂会怎么样？ ####

如果数组长度不是 2 的 n 次幂，计算出的索引特别容易相同，及其容易发生 hash 碰撞，导致其余数组空间很大程度上并没有存储数据，链表或者红黑树过长，效率降低。

#### 小结： ####

1，当根据 key 的 hash 确定其在数组的位置时，如果 n 为 2 的幂次方，**可以保证数据的均匀插入**，如果 n 不是 2 的幂次方，可能数组的一些位置永远不会插入数据，**浪费数组的空间，加大 hash 冲突。**

2，一般可能会想通过 % 求余来确定位置，这样也可以，只不过性能不如 & 运算。而且当 n 是 2 的幂次方时：hash & (length - 1) == hash % length

3，因此，HashMap 容量为 2 次幂的原因，就是 **为了数据的的均匀分布，减少 hash 冲突**，毕竟 hash 冲突越大，代表数组中一个链的长度越大，这样的话会降低 hashmap 的性能

好了，今天就先分享到这里了，下期继续给大家带来 HashMap 面试内容！更多干货、优质文章，欢迎关注我的原创技术公众号~

[Image 1]: 
[Link 1]: https://so.csdn.net/so/search?q=%E9%9B%86%E5%90%88&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8&spm=1001.2101.3001.7020
[Link 3]: https://so.csdn.net/so/search?q=%E9%93%BE%E8%A1%A8&spm=1001.2101.3001.7020
[hash]: https://so.csdn.net/so/search?q=hash&spm=1001.2101.3001.7020
[Link 4]: https://so.csdn.net/so/search?q=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84&spm=1001.2101.3001.7020