HashMap深入理解(源码,设计原理深入剖析)

蔚落 2023-03-12 09:27 14阅读 0赞

# 哈希表是什么? #

[散列表][Link 1]（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的[数据结构][Link 2]。也就是说，它通过把**关键码值映射到表中一个位置来访问记录，以加快查找的速度。**这个映射函数叫做[散列函数][Link 3]，**存放记录的[数组][Link 4]叫做[散列表][Link 1]。**

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

## 思考: ##

**多个 key 通过散列函数会得到相同的值，这时候怎么办？**

**1. [开放寻址法][Link 5]：**Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）为[散列函数][Link 6]，m为[散列表][Link 7]长，di为增量序列，可有下列三种取法：

1.1. di=1,2,3，…，m-1，称线性探测再散列；

1.2. di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）称二次探测再散列；

1.3. di=[伪随机数][Link 8]序列，称伪随机探测再散列。

**2. 再[散列法][Link 9]：**Hi=RHi(key),i=1,2，…，k RHi均是不同的[散列函数][Link 6]，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

**3. 链地址法（拉链法）**

4. 建立一个公共溢出区

当然以上作为了解,如果感兴趣可以自己深入去了解下,我们这里就主要关心  链地址法（拉链法）

# 什么是HashMap？ #

## HashMap定义 ##

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射，而且 key 和 value 都可以为 null。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd4dWVsZWkwMzY_size_16_color_FFFFFF_t_70][]

注:实线是继承关系(extends),虚线为接口实现关系(implements)

首先该类实现了一个 Map 接口，该接口定义了一组键值对映射通用的操作。储存一组成对的键-值对象，提供key（键）到value（值）的映射，Map中的key不要求有序，不允许重复。value同样不要求有序，但可以重复。但是我们发现该接口方法有很多，我们设计某个键值对的集合有时候并不像实现那么多方法，那该怎么办？

**我们发现 HashMap 类即继承了 AbstractMap 接口，也实现了 Map 接口，这样做难道不是多此一举？**

据 java 集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

HashMap 是一个利用**哈希表原理来存储元素的集合**。**遇到冲突时，HashMap 是采用的链地址法来解决**，在 **JDK1.7 中，HashMap 是由 数组+链表构**成的。但是在 J**DK1.8 中，HashMap 是由 数组+链表+红黑树**构成，新增了红黑树作为底层数据结构，结构变得复杂了，但是效率也变的更高效。下面我们来具体介绍在 JDK1.8 中 HashMap 是如何实现的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd4dWVsZWkwMzY_size_16_color_FFFFFF_t_70 1][]

## 红黑树是什么？ ##

![format_png][]

红黑树是一种平衡二叉查找树的变体，它的**左右子树高差有可能大于 1，所以红黑树不是严格意义上的[平衡二叉树][Link 10]（AVL）**，在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。**但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL(综合性能强)，即 牺牲了一些平衡性,但是减少了平衡调整的消耗（红黑树恢复平衡时需要的旋转次数比avl树少） (注:这也是为什么选红黑树而不是AVL 的原因,面试官可能会问哦**)。

### **红黑树有几种特性：** ###

1. 节点是红色或黑色。

2. 根节点是黑色。

3.所有叶子都是黑色。（叶子是NUIL节点）

4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）

5.. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束使红黑树具有这样一个关键属性：**从根节点到最远的叶子节点的路径长与到最近的叶子节点的路径长度相差不会超过2。 因为红黑树是近似平衡的。**

另外，**插入、删除和查找操作与树的高度成正比，所以红黑树的最坏情况，效率仍然很高。**（不像普通的二叉搜索树那么慢）

### 红黑树节点平衡调整方式： ###

1.旋转调整结构

2.节点颜色调整

这里也就简单介绍下,对红黑树有个概念,如果想深入了解,可以找些资料去了解下。

## 属性介绍 ##

//序列化和反序列化时，通过该字段进行版本一致性验证
        private static final long serialVersionUID = 362498820763181265L;
        //默认 HashMap 集合初始容量为16（必须是 2 的倍数）
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
        //集合的最大容量，如果通过带参构造指定的最大容量超过此数，默认还是使用此数
        static final int MAXIMUM_CAPACITY = 1 << 30;
        //默认的填充因子(比较重要的属性)
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        //当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)
        static final int TREEIFY_THRESHOLD = 8;
        //当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)
        static final int UNTREEIFY_THRESHOLD = 6;
        /**(JDK1.8新增)
         * 当集合中的容量大于这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，
         * 而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
         */
        static final int MIN_TREEIFY_CAPACITY = 64;

/**
         * 初始化使用，长度总是 2的幂
         */
        transient Node<K,V>[] table;
    
        /**
         * 保存缓存的entrySet（）
         */
        transient Set<Map.Entry<K,V>> entrySet;
    
        /**
         * 此映射中包含的键值映射的数量。（集合存储键值对的数量）
         */
        transient int size;
    
        /**
         * 跟前面ArrayList和LinkedList集合中的字段modCount一样，记录集合被修改的次数
         * 主要用于迭代器中的快速失败
         */
        transient int modCount;
    
        /**
         * 调整大小的下一个大小值（容量*加载因子）。capacity * load factor
         */
        int threshold;
    
        /**
         * 散列表的加载因子。
         */
        final float loadFactor;

下面我们重点介绍上面几个字段：

**①、Node<K,V>\[\] table**

我们说 HashMap 是由数组+链表+红黑树组成，这里的数组就是 table 字段（table中是一个是实现了Entry内部类的Node类,结构如下）。 JDK 声明数组的长度总是 2的n次方(一定是合数)，为什么这里要求是合数，一般我们知道哈希算法为了避免冲突都要求长度是质数，这里要求是合数，下面在介绍 HashMap 的hashCode() 方法(散列函数)，我们再进行讲解。

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

②**、size**

**　　**集合中存放key-value 的实时对数。

**③、loadFactor**

装载因子，是用来衡量 HashMap 满的程度，计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。capacity 是桶的数量，也就是 table 的长度length。

默认的负载因子0.75 ，如果**内存空间很多而又对时间效率要求很高，可以降低负载因子loadFactor 的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子 loadFactor 的值，**这个值可以大于1。这个参数是对**空间和时间效率的一个平衡选择。**

**④、threshold**

计算公式：capacity \* loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容)，扩容后的 HashMap 容量是之前容量的两倍

## 确定哈希桶数组索引位置 ##

前面我们讲解哈希表的时候，我们知道是用散列函数来确定索引的位置。散列函数设计的越好，使得元素分布的越均匀。HashMap 是数组+链表+红黑树的组合，我们希望在有限个数组位置时，尽量每个位置的元素只有一个，那么当我们用散列函数求得索引位置的时候，我们能马上知道对应位置的元素是不是我们想要的，而不是要进行链表的遍历或者红黑树的遍历，这会大大优化我们的查询效率。我们看 HashMap 中的哈希算法：

static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

主要分为三步：

①、取 hashCode 值： key.hashCode()

②、高位参与运算：h>>>16

③、**取模运算：(n-1) & hash（思考:不直接用 hash%length来获取）**

这里获取 hashCode() 方法的值是变量，但是我们知道，对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(Object key) 所计算得到的 hash码 值总是相同的。

为了让数组元素分布均匀，我们首先想到的是把获得的 hash码对数组长度取模运算( hash%length)，但是计算机都是二进制进行操作，取模运算相对开销还是很大的，那该如何优化呢？

HashMap 使用的方法很巧妙，它通过 hash & (table.length -1)来得到该对象的保存位，前面说过 HashMap 底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当 length 总是2的n次方时，hash & (length-1)运算等价于对 length 取模，也就是 hash%length，但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)

**这也解释了为什么要保证数组的长度总是2的n次方。**

**　　**再就是在 JDK1.8 中还有个高位参与运算，hashCode() 得到的是一个32位 int 类型的值，通过hashCode()的高16位 **异或** 低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

![format_png 1][]

## 添加操作 ##

//hash(key)就是上面讲的hash方法，对其进行了第一步和第二步处理
        public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
        /**
         * 
         * @param hash 索引的位置
         * @param key  键
         * @param value  值
         * @param onlyIfAbsent true 表示不要更改现有值
         * @param evict false表示table处于创建模式
         * @return
         */
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
             Node<K,V>[] tab; Node<K,V> p; int n, i;
             //如果table为null或者长度为0，则进行初始化
             //resize()方法本来是用于扩容，由于初始化没有实际分配空间，这里用该方法进行空间分配，后面会详细讲解该方法
             if ((tab = table) == null || (n = tab.length) == 0)
                 n = (tab = resize()).length;
             //注意：这里用到了前面讲解获得key的hash码的第三步，取模运算，下面的if-else分别是 tab[i] 为null和不为null
             if ((p = tab[i = (n - 1) & hash]) == null)
                 tab[i] = newNode(hash, key, value, null);//tab[i] 为null，直接将新的key-value插入到计算的索引i位置
             else {//tab[i] 不为null，表示该位置已经有值了
                 Node<K,V> e; K k;
                 if (p.hash == hash &&
                     ((k = p.key) == key || (key != null && key.equals(k))))
                     e = p;//节点key已经有值了，直接用新值覆盖
                 //该链是红黑树
                 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;
                         }
                         //key已经存在直接覆盖value
                         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;
        }

①、判断键值对数组 table 是否为空或为null，否则执行resize()进行扩容；

②、根据键值key计算hash值得到插入的数组索引i，如果table\[i\]==null，直接新建节点添加，转向⑥，如果table\[i\]不为空，转向③；

③、判断table\[i\]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④、判断table\[i\] 是否为treeNode，即table\[i\] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤、遍历table\[i\]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥、插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold，如果超过，进行扩容。

⑦、如果新插入的key不存在，则返回null，如果新插入的key存在，则返回原key对应的value值（注意新插入的value会覆盖原value值）

### 扩容机制 ###

扩容（resize），JDK1.8中 集合是由数组+链表+红黑树构成，向 HashMap 中插入元素时，如果HashMap 集合的元素已经大于了最大承载容量threshold（capacity \* loadFactor），这里的threshold不是数组的最大长度。那么必须扩大数组的长度，Java中数组是无法自动扩容的，我们采用的方法是用一个更大的数组代替这个小的数组

JDK1.7中扩容先创建一个新的大容量数组，然后依次重新计算原集合所有元素的索引(rehash一次)，然后重新赋值。如果数组某个位置发生了hash冲突，使用的是单链表的头插入方法，同一位置的新元素总是放在链表的头部，这样与原集合链表对比，扩容之后的可能就是倒序的链表了。

JDK1.8

final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;//原数组如果为null，则长度赋值0
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {//如果原数组长度大于0
                if (oldCap >= MAXIMUM_CAPACITY) {//数组大小如果已经大于等于最大值(2^30)
                    threshold = Integer.MAX_VALUE;//修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
                    return oldTab;
                }
                //原数组长度大于等于初始化长度16，并且原数组长度扩大1倍也小于2^30次方
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // 阀值扩大1倍
            }
            else if (oldThr > 0) //旧阀值大于0，则将新容量直接等于就阀值 
                newCap = oldThr;
            else {//阀值等于0，oldCap也等于0（集合未进行初始化）
                newCap = DEFAULT_INITIAL_CAPACITY;//数组长度初始化为16
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//阀值等于16*0.75=12
            }
            //计算新的阀值上限
            if (newThr == 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) {
                //把每个bucket都移动到新的buckets中
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;//元数据j位置置为null，便于垃圾回收
                        if (e.next == null)//数组没有下一个引用（不是链表）
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)//红黑树
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do {
                                next = e.next;
                                //原索引
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                //原索引+oldCap
                                else {
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            //原索引放到bucket里
                            if (loTail != null) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            //原索引+oldCap放到bucket里
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

**相比于JDK1.7，1.8使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。**

## 删除元素 ##

HashMap 删除元素首先是要找到 桶的位置，然后如果是链表，则进行链表遍历，找到需要删除的元素后，进行删除；如果是红黑树，也是进行树的遍历，找到元素删除后，进行平衡调节，注意，当红黑树的节点数小于 6 时，会转化成链表。

## 查找元素 ##

通过 key 找到计算索引，找到桶位置，先检查第一个节点，如果是则返回，如果不是，则遍历其后面的链表或者红黑树。其余情况全部返回 null。

**总结：HashMap的实现原理：**

1.  **利用key的hashCode重新hash计算出当前对象的元素在数组中的下标**
2.  **存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中或者红黑树节点中**
3.  **获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。**
4.  **理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表或红黑树，一旦发现冲突就在链表中做进一步的对比。**

[Link 1]: https://baike.baidu.com/item/%E6%95%A3%E5%88%97%E8%A1%A8/10027933
[Link 2]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450
[Link 3]: https://baike.baidu.com/item/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B0/2366288
[Link 4]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84/3794097
[Link 5]: https://baike.baidu.com/item/%E5%BC%80%E6%94%BE%E5%AF%BB%E5%9D%80%E6%B3%95
[Link 6]: https://baike.baidu.com/item/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B0
[Link 7]: https://baike.baidu.com/item/%E6%95%A3%E5%88%97%E8%A1%A8
[Link 8]: https://baike.baidu.com/item/%E4%BC%AA%E9%9A%8F%E6%9C%BA%E6%95%B0
[Link 9]: https://baike.baidu.com/item/%E6%95%A3%E5%88%97%E6%B3%95
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd4dWVsZWkwMzY_size_16_color_FFFFFF_t_70]: /images/20230312/ef64b97d18da44f3a5d285f25d45271d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd4dWVsZWkwMzY_size_16_color_FFFFFF_t_70 1]: /images/20230312/fbe298ead91942bc93b0f924ad71cc9b.png
[format_png]: /images/20230312/9e69cc3af5cf4eff8833695bf7f5af43.png
[Link 10]: https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91/10421057
[format_png 1]: /images/20230312/37f6d59627774cc287915f945dba5755.png