HashMap原理。图文并茂式解读。这些注意点你一定还不了解

谁借莪１个温暖的怀抱￠ 2024-04-18 10:36 47阅读 0赞

\[TOC\]

# 概述 #

本篇文章我们来聊聊大家日常开发中常用的一个集合类 - HashMap。HashMap 最早出现在 JDK 1.2中，底层基于散列算法实现。HashMap 允许 null 键和 null 值，在计算哈键的哈希值时，null 键哈希值为 0。HashMap 并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。另外，需要注意的是，HashMap 是非线程安全类，在多线程环境下可能会存在问题。

# 属性详解 #

DEFAULT*INITIAL*CAPACITY 默认初始容量MAXIMUM\_CAPACITY 最大容量DEFAULT*LOAD*FACTOR 默认负载因子TREEIFY\_THRESHOLD 一个桶的树化阈值(超过此值会变成红黑树)UNTREEIFY\_THRESHOLD 一个树的链表还原阈值(小于此值在resize的时候会变回链表)MIN*TREEIFY*CAPACITY 哈希表的最小树形化容量(为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 \* TREEIFY\_THRESHOLD)

## table ##

HashMap中的数组(hash表)。hash表的长度总是在2^n。至于原因吗，后面专门会说的。数组里存储的是Node节点的数据

## entrySet ##

Node 　节点构成的 set

## size ##

当前map中存储节点的数据

## modCount ##

hashMap发生结构性变化的次数，节点转红黑树、扩容等操作。

## threshold、loadFactor ##

扩容阙值和装载因子。

# 源码知识点必备 #

## getGenericInterfaces和getInterfaces区别 ##

getGenericInterfaces获取直接接口getInterfaces获取所有接口

## ParameterizedType ##

是Type的子接口，表示一个有参数的类型。就是我们俗称的泛型。实现这个接口的类必须提供equals方法。

## getRawType ##

返回最外层<>前面那个类型，即Map 的Map。

## getActualTypeArguments ##

获取“泛型实例”中<>里面的“泛型变量”（也叫类型参数）的值，这个值是一个类型。因为可能有多个“泛型变量”（如：Map ）,所以返回的是一个Type\[\]。注意：无论<>中有几层<>嵌套，这个方法仅仅脱去最外层的<>，之后剩下的内容就作为这个方法的返回值，所以其返回值类型是不确定的。

## getOwnerType ##

获得这个类型的所有者的类型，主要对嵌套定义的内部类而言。列如对java.util.Map.Node 调用getOwnerType方法返回的是interface java.util.Map接口

## comparableClassFor ##

HashMap类中有一个comparableClassFor(Object x)方法，当x的类型为X，且X直接实现了Comparable接口（比较类型必须为X类本身）时，返回x的运行时类型；否则返回null。通过这个方法，我们可以搞清楚一些与类型、泛型相关的概念和方法

## (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) ##

hashCode与自己的高16为进行异或 。 这样更分散ps:& ： 全部为1则为1，否则为0 偏0| ： 有一个为1则为1，否则为0 偏1^ ： 相同为0 不同为1 更加均衡。 均匀(分散)

# hash表维护 #

在文章开头我们就解释了HashMap中table就是我们的hash表。直观上我们可以理解成一个开辟空间的数组。HashMap通过hash(key)这个方法获取hash值。然后通过hash值确定key在hash表中的位置（`(n - 1) & hash`）。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70][]综合上图我们也会发现问题了。key的个数是无限的。但是我们的hash表是有限的。如何能保证hash(key)不会落在同一个位置呢。答案是不能。换句话说就是我们hash(key)无法保证。也就是hashMap会发生hash碰撞的。hash函数只能尽量避免hash碰撞。上面的`(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)`就是为了让hash更加分散点。这一点上面也作出了解释。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 1][]

# HashMap 数组长度是2^n ？ #

上面解释了hashmap中hash函数为什么要^ 。 那么深度源码的小伙伴可能会问，为什么hashmap默认容量是16以及后期每次扩容的时候为什么是翻倍扩容。简而言之。为什么hashMap数组长度永远是2的倍数呢。上面我们知道如何通过hash确定在数组中位置的。`(n - 1) & hash`关于这个n是数组的长度，hash就是key值通过hash函数计算出来的hash值。& 运算规则是： 全部为1则为1，否则为0假设目前hashMap容量是16 ， 我们来看看在扩容前后我们key的在是数组中的索引。![扩容前后][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 2]经过图片鲜明的对比我们发现，扩容前后是不会影响原来数据(高位为0)的索引位置的。这里要注意的是并不是说所有数据不受影响，只要原来从右至左第五位为0的hash会受影响，其他不会。这样大大减少了数组位置调换的操作。性能上也大大的提高了。从这里也可以看出hashmap容量越大，扩容是越复杂，因为容量越大，需要换位置的索引越多。那么如果我们扩容是不是选择扩大2倍 ， 我们看看会发生什么样情况。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 3][]上图中是有16扩展成了24容量。这个时候我们会发现除了(从右至左)第五位以为第四位的数据也发生了变化。这样造成的接口是第四位和第五位的数据都会变化。这样增加了索引位置的数量。所以我们需要在每次扩容为原来的2倍。

# 神奇的hashmap遍历 #

做Java的肯定会遇到的一种情况是，为什么我的map遍历的顺序和我添加的顺序不一致呢。有时候我们做列表展示的时候对顺序是有要求的。但是hashmap偏偏和我们想的不一样。今天华仔带你看看为什么会出现这种神奇的遍历。

public final void forEach(Consumer<? super K> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length;   i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

从上面的代码我们可以看出来hashmap在遍历时候，是先遍历数组然后取到数组中链表(红黑树)按照顺序获取node节点的。也即是说我们先按数组再按链表顺序。而不是按照你添加先后的顺序。而上面我们了解添加的node决定其位置的是key的hash值。所以这就解释了为什么hashmap遍历的时候和我们添加不一致的了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 4][]

# put 流程跟踪 #

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 5][]

其他方法原理是相同的。值得注意的是remove后临界情况会发生红黑树转链表。所以转红黑树的这个阙值的选取有时候会影响性能的高低。下面看看put的实际源码吧。拜读下大佬的代码。

上面的代码可以看出来put实际调用的方法是putVal();int hash ： key对应的hash值K key, ： keyV value, ： valueonlyIfAbsent : 如果存在则忽略，默认false表示新值会覆盖旧值boolean evict： 表示是否在构造table时调用

/**
    * Implements Map.put and related methods
    *
    * @param hash hash for key
    * @param key the key
    * @param value the value to put
    * @param onlyIfAbsent if true, don't change existing value
    * @param evict if false, the table is in creation mode.
    * @return previous value, or null if none
    */
    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);
    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;
    }

# 寒暄一句 #

个人几天时间总结的，有网上前辈的总结，也有加入个人的想法。再次申明：以上图片部分来自网络。

加入战队

### 加入战队 ###

## 微信公众号 ##

![微信公众号][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 6]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190905145420978.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d2697d8344a044e093cc74d511524411.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190905145421760.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/597836b367b84fdc859fd3bf4fc27e7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ca6ef0033dd64c8e82351d1bb3b8be9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/36ed51c65b774714be7fd195ba40a847.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2019090514542449.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMxMzIwNTE=,size_16,color_FFFFFF,t_70