Java教程
HashMap源码解析
本文主要是介绍HashMap源码解析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
HashMap 源码解析
1、概述
1.1、简介
-
HashMap 底层基于散列算法实现，采用 key/value 存储结构，每个 key 对应唯一的 value， 允许 key 和 value 为null，null 的哈希值为 0。
-
其底层数据结构是数组称之为哈希桶，每个桶里面放的是链表，链表中的每个节点，就是哈希表的每个元素。
-
在JDK8中，当链表的长度大于8并且表的长度大于64时，会将链表优化为红黑树，以提升它查询、插入的效率，查找效率从O(n)优化为O(logn)。
-
非线程安全。
-
JDK 1.8 之前，HashMap 底层数据结构为 数组+链表，JDK1.8 引入红黑树优化过长的链表。
2、字段
2.1、常量字段
// 序列号，序列化的时候使用 private static final long serialVersionUID = 362498820763181265L; // 默认容量，使用移位是因为移位是计算机基础运算，效率比加减乘除快。 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // 最大容量，2的30次幂 static final int MAXIMUM_CAPACITY = 1 << 30; // 加载因子，用于扩容使用。 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 当某个桶的链表长度大于8，且hash桶的长度大于64时，转为红黑树结构。 static final int TREEIFY_THRESHOLD = 8; // 当某个桶结点小于6时，会转化为链表，前提是当前是红黑树 static final int UNTREEIFY_THRESHOLD = 6; // 当某个桶的链表长度大于8，且hash桶的长度大于64时，转为红黑树结构。 static final int MIN_TREEIFY_CAPACITY = 64;
2.2、实例字段
//哈希桶数组，分配的时候，table的长度总是2的幂 transient Node<K,V>[] table; //HashMap将数据转换成set的另一种存储形式，这个变量主要用于迭代功能 transient Set<Map.Entry<K,V>> entrySet; //实际存储的数量，则HashMap的size()方法，实际返回的就是这个值，isEmpty()也是判断该值是否为0 transient int size; //hashmap结构被改变的次数，fail-fast机制 transient int modCount; //HashMap的扩容阈值，在HashMap中存储的Node键值对超过这个数量时，自动扩容容量为原来的二倍 int threshold; //HashMap的负加载因子，可计算出当前table长度下的扩容阈值：threshold = loadFactor * table.length final float loadFactor;
负载因子（loadFactor），源码中有个公式为threshold = loadFactor * 容量。HashMap和HashSet都允许你指定负载因子的构造器，表示当负载情况达到负载因子水平的时候，容器会自动扩容，HashMap默认使用的负载因子值为0.75f（当容量达到四分之三进行再散列（扩容））。当负载因子越大的时候能够容纳的键值对就越多但是查找的代价也会越高。所以如果你知道将要在HashMap中存储多少数据，那么你可以创建一个具有恰当大小的初始容量这可以减少扩容时候的开销。但是大多数情况下0.75在时间跟空间代价上达到了平衡所以不建议修改。
3、链表节点Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 哈希值
final K key; // key
V value; // 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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
// 每个节点的值，是将key的hashCode 和 value的hashCode 亦或得到的
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
// 设置新的value 同时返回旧的value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
由此可见，这是一个单链表。
每一个节点的hash值，是将key的hashCode 和 value的hashCode 亦或得到的。
4、构造函数
// 默认构造函数，加载因子为默认的0.75f
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//指定初始化容量的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//同时指定初始化容量 以及 加载因子， 用的很少，一般不会修改loadFactor
public HashMap(int initialCapacity, float loadFactor) {
//边界处理
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量最大不能超过2的30次方
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//显然加载因子不能为负数
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//设置阈值为 >= 初始化容量的 2的n次方的值
this.threshold = tableSizeFor(initialCapacity);
}
//新建一个哈希表，同时将另一个map m 里的所有元素加入表中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
计算容量
//根据期望容量cap，返回2的n次方形式的 哈希桶的实际容量 length。 返回值一般会>=cap
static final int tableSizeFor(int cap) {
//经过下面的 或 和位移 运算， n最终各位都是1。
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//判断n是否越界，返回 2的n次方作为 table（哈希桶）的阈值
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
至于为什么n = cap - 1，是因为如果cap正好是2的n次幂，如果不-1，那么就会返回2的n+1次幂，为了避免这种情况，需要先-1。
比如n一开始是1011（二进制），经过位运算，会变成1111（二进制），最后再n+1变成10000，实现初始容量为2的n次幂。
5、扩容 resize
初始化或者加倍哈希桶大小。
如果当前哈希桶是null，那么就分配符合当前阈值的初始容量目标（16）。
如果当前哈希桶容量超过阈值（threshold = loadFactor * table.length），那么将哈希桶容量扩容为以前的两倍。
final Node<K,V>[] resize() {
// oldTab 当前表的哈希桶
Node<K,V>[] oldTab = table;
// oldCap 当前哈希桶的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 当前的阈值
int oldThr = threshold;
// 初始化新的容量和阈值都为0
int newCap, newThr = 0;
// 如果当前容量大于0
if (oldCap > 0) {
// 如果当前容量已经到达上限
if (oldCap >= MAXIMUM_CAPACITY) {
// 则设置阈值为2的31次方-1
threshold = Integer.MAX_VALUE;
// 同时返回当前的哈希桶，不再进行扩容
return oldTab;
}
// newCap = oldCap << 1 否则设置新的容量为旧的容量的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) // 如果旧的容量大于等于默认初始容量16
// 那么新的阈值也等于旧的阈值的两倍
newThr = oldThr << 1;
}// 如果当前的表是空的，但是有阈值。代表是初始化的时候指定了容量、阈值的情况
else if (oldThr > 0)
newCap = oldThr; // 那么新表的容量就等于旧的阈值
else { // 如果当前表是空的，而且也没有阈值。代表初始化时没有任何容量/阈值参数的情况
newCap = DEFAULT_INITIAL_CAPACITY; // 此时新表的容量就等于默认的容量 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 新的阈值为默认容量16 * 默认加载因子
}
if (newThr == 0) { // 如果新的阈值是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) {
// 遍历老的哈希桶
for (int j = 0; j < oldCap; ++j) {
// 取出当前节点 e
Node<K,V> e;
// 如果当前桶中有元素，则将链表赋值给 e
if ((e = oldTab[j]) != null) {
// 将原哈希桶置空以便GC
oldTab[j] = null;
// 如果当前链表就只有e一个元素（没有发生哈希碰撞）
if (e.next == null)
// 直接将这个元素放置在新的哈希桶里
// 注意这里取下标 是用 哈希值 与 桶的长度-1。由于桶的长度是2的n次方，减1相当于低位全是1，这么做其实就相当于是取模运算。
newTab[e.hash & (newCap - 1)] = e;
// 如果发生过哈希碰撞，并且节点数超过8个转化成红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 如果发生过哈希碰撞，节点数小于8个。则需要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置
else {
// 因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位；或者扩容后的下标，即high位。high位 = 原哈希桶容量 + low位
// 低位链表的头结点、尾节点
Node<K,V> loHead = null, loTail = null;
// 高位链表的头结点、尾节点
Node<K,V> hiHead = null, hiTail = null;
// 临时节点 存放e的下一个节点
Node<K,V> next;
do {
next = e.next;
// 这里又是一个利用位运算，代替常规运算的高效点：利用哈希值 与 旧的容量，可以得到哈希值取模后，是大于等于oldCap还是小于oldCap，等于0代表小于oldCap，应该存放在低位，否则存放在高位。
if ((e.hash & oldCap) == 0) {
// 给低位的头结点赋值
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 给高位的头结点赋值
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
} // 循环直到当前哈希桶的链表结束
} while ((e = next) != null);
// 将低位链表存放在原index处
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 将高位链表存放在新index处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
6、增加修改 put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
如果参数onlyIfAbsent是true，那么就不会覆盖相同key的值value。如果evict是false，代表是在初始化时调用的。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab存放 当前的哈希桶 ，p用作临时链表节点
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果当前哈希表是空的或者哈希表长度为0，代表是初始化
if ((tab = table) == null || (n = tab.length) == 0)
// 那么直接去扩容哈希表，并且将扩容后的哈希桶的长度赋值给 n
n = (tab = resize()).length;
// 如果当前index的节点是空的，表示没有发生哈希碰撞。直接构建一个新节点Node，挂载在index处即可。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // 否则 发生了哈希碰撞
Node<K,V> e; K k;
// 如果hash值相等 并且 key也相等，则是覆盖value操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 将当前节点引用赋值给e
else if (p instanceof TreeNode) // 如果是p是红黑树，那么就执行红黑树的插入操作
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;
}
// 如果找到要覆盖的节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果e不是null，说明有需要覆盖的节点
if (e != null) {
// 则返回oldValue
V oldValue = e.value;
// 如果onlyIfAbsent为false，或者oldValue的值为null
if (!onlyIfAbsent || oldValue == null)
// 覆盖旧的值
e.value = value;
afterNodeAccess(e);
// 返回旧的值
return oldValue;
}
}
// 如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null
// 修改modCount
++modCount;
// 更新size，并判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
扰动函数
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
hash碰撞
而key的hash值，并不仅仅只是key对象的hashCode()方法的返回值，还会经过扰动函数的扰动，以使hash值更加均衡。
因为hashCode()是int类型，取值范围是40多亿，只要哈希函数映射的比较均匀松散，碰撞几率是很小的。
但就算原本的hashCode()取得很好，每个key的hashCode()不同，但是由于HashMap的哈希桶的长度远比hash取值范围小，默认是16，所以当对hash值以桶的长度取余，以找到存放该key的桶的下标时，由于取余是通过与操作完成的，会忽略hash值的高位。因此只有hashCode()的低位参加运算，发生不同的hash值，但是得到的index相同的情况的几率会大大增加，这种情况称之为hash碰撞。 即，碰撞率会增大。
扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征，并存放在低位，因此在位运算的时候，相当于高低位一起参加了运算，以减少hash碰撞的概率。
7、删除remove
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;}
从哈希表中删除某个节点，如果参数matchValue为true，则必须key、value都相等才删除
如果movable是false，在删除节点时，不移动其他节点。
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { // p 是待删除节点的前置结点 Node<K,V>[] tab; Node<K,V> p; int n, index; // 如果哈希表存在且不为空，并且哈希表索引处有节点 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { // node是待删除节点 Node<K,V> node = null, e; K k; V v; // 如果链表头结点就是要删除的节点 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 将待删除节点的引用赋给node node = p; else if ((e = p.next) != null) { // 否则循环遍历，找到待删除节点，赋值给node if (p instanceof TreeNode) // 如果p的类型是 树节点，那么调用红黑树的get方法找到待删除节点 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { // 循环当前链表，找到待删除节点 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } // 如果找到待删除节点，且matchValue为false，或者值相等 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { // 如果node是树节点，那么调用红黑树的remove方法 if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) // 如果node == p，说明是链表头是待删除节点 tab[index] = node.next; else // 否则待删除节点在链表中间，p是待删除节点的前置节点 p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null;}
以key value为条件的删除
@Override public boolean remove(Object key, Object value) { // 要求key和value都匹配才删除，所以matchValue为true return removeNode(hash(key), key, value, true, true) != null; }
8、查找get
以key为条件，找到返回value，没找到返回null
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value;}
// 传入扰动后的哈希值 和 key 找到目标节点Node，过程和remove差不多，找到返回节点，找不到返回nullfinal Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null;}
判断是否包含该key
public boolean containsKey(Object key) { return getNode(hash(key), key) != null;}
判断是否包含该value
public boolean containsValue(Object value) { Node<K,V>[] tab; V v; //遍历哈希桶上的每一个链表 if ((tab = table) != null && size > 0) { for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) { //如果找到value一致的返回true if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false;}
5、问题
1、为何HashMap的数组长度一定是2的次幂？
如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
以JDK1.8为例，查看下面一段代码：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
然后再点进putVal 方法，则会看到有下面的代码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // tab存放 当前的哈希桶 ，p用作临时链表节点 Node<K,V>[] tab; Node<K,V> p; int n, i; // 如果当前哈希表是空的或者哈希表长度为0，代表是初始化 if ((tab = table) == null || (n = tab.length) == 0) // 那么直接去扩容哈希表，并且将扩容后的哈希桶的长度赋值给 n n = (tab = resize()).length; // 如果当前index的节点是空的，表示没有发生哈希碰撞。直接构建一个新节点Node，挂载在index处即可。 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;1、为何HashMap的数组长度一定是2的次幂？如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。 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;}
其中有这么一段代码：
tab[i = (n - 1) & hash]
因为hashMap 的数组长度都是2的n次幂 ，那么对于这个数再减去1，转换成二进制的话，就肯定是最高位为0，其他位全是1 的数。
那以数组长度为8为例（默认HashMap初始数组长度是16），那8-1 转成二进制的话，就是0111 。 那我们举一个随便的hashCode值，与0111进行与运算看看结果如何：
数字8减去1转换成二进制是0111，即下边的情况：
第一个key： hashcode值：10101001 & 0111 0001 （十进制为1） ------------------------------------------- 第二个key： hashcode值：11101000 & 0111 0000 （十进制为0） -------------------------------------------- 第三个key： hashcode值：11101110 & 0111 0110 （十进制为6）
这样得到的数，就会完整的得到原hashcode 值的低位值，不会受到与运算对数据的变化影响。
数字7减去1转换成二进制是0110，即下边的情况：
第一个key： hashcode值：10101001 & 0110 0000 （十进制为0） ------------------------------------------ 第二个key： hashcode值：11101000 & 0110 0000 （十进制为0） -------------------------------------------- 第三个key： hashcode值：11101110 & 0111 0110 （十进制为6）
通过上边可以看到，当数组长度不为2的n次幂 的时候，hashCode 值与数组长度减一做与运算 的时候，会出现重复的数据，
因为不为2的n次幂 的话，对应的二进制数肯定有一位为0 , 这样不管你的hashCode 值对应的该位，是0还是1 ,
最终得到的该位上的数肯定是0，这带来的问题就是HashMap上的数组元素分布不均匀，而数组上的某些位置，永远也用不到。
2、为什么链表转红黑树的阈值是8？
桶中个数小于8，链表的查询性能和红黑树差不多，转化为树还要时间和空间，所以没有转化成树的必要。
这篇关于HashMap源码解析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Java语音识别项目资料：新手入门教程11-26
-
JAVA语音识别项目资料：新手入门教程11-26
-
Java语音识别项目资料：入门与实践指南11-26
-
Java云原生资料入门教程11-26
-
Java云原生资料入门教程11-26
-
Java云原生资料：新手入门教程11-26
-
Java创意资料：新手入门的创意学习指南11-25
-
JAVA对接阿里云智能语音服务资料详解：新手入门指南11-25
-
Java对接阿里云智能语音服务资料详解11-25
-
Java对接阿里云智能语音服务资料详解11-25
-
JAVA副业资料：新手入门及初级提升指南11-25
-
Java副业资料：入门到实践的全面指南11-25
-
Springboot应用的多环境打包项目实战11-25
-
SpringBoot应用的生产发布项目实战入门教程11-25
-
Viite多环境配置项目实战：新手入门教程11-25
栏目导航
