[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<K,V> 节点构成的 set

size

当前 map 中存储节点的数据

modCount

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

threshold、loadFactor

扩容阙值和装载因子。

源码知识点必备

getGenericInterfaces 和 getInterfaces 区别

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

ParameterizedType

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

getRawType

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

getActualTypeArguments

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

getOwnerType

获得这个类型的所有者的类型，主要对嵌套定义的内部类而言。列如对 java.util.Map.Node<K,V> 调用 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）。

综合上图我们也会发现问题了。key 的个数是无限的。但是我们的 hash 表是有限的。如何能保证 hash(key)不会落在同一个位置呢。答案是不能。换句话说就是我们 hash(key)无法保证。也就是 hashMap 会发生 hash 碰撞的。hash 函数只能尽量避免 hash 碰撞。上面的 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) 就是为了让 hash 更加分散点。这一点上面也作出了解释。

HashMap 数组长度是 2^n？

上面解释了 hashmap 中 hash 函数为什么要 ^。那么深度源码的小伙伴可能会问，为什么 hashmap 默认容量是 16 以及后期每次扩容的时候为什么是翻倍扩容。简而言之。为什么 hashMap 数组长度永远是 2 的倍数呢。
上面我们知道如何通过 hash 确定在数组中位置的。
(n - 1) & hash
关于这个 n 是数组的长度，hash 就是 key 值通过 hash 函数计算出来的 hash 值。
& 运算规则是：全部为 1 则为 1，否则为 0
假设目前 hashMap 容量是 16，我们来看看在扩容前后我们 key 的在是数组中的索引。

经过图片鲜明的对比我们发现，扩容前后是不会影响原来数据 (高位为 0) 的索引位置的。这里要注意的是并不是说所有数据不受影响，只要原来从右至左第五位为 0 的 hash 会受影响，其他不会。这样大大减少了数组位置调换的操作。性能上也大大的提高了。从这里也可以看出 hashmap 容量越大，扩容是越复杂，因为容量越大，需要换位置的索引越多。
那么如果我们扩容是不是选择扩大 2 倍，我们看看会发生什么样情况。

上图中是有 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 遍历的时候和我们添加不一致的了。

put 流程跟踪

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

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

上面的代码可以看出来 put 实际调用的方法是 putVal();
int hash：key 对应的 hash 值
K key,：key
V value,：value
onlyIfAbsent : 如果存在则忽略，默认 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;
}

寒暄一句

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

加入战队

<span id=”addMe”> 加入战队 </span>

微信公众号