JAVA 基础笔记（一）HashMap 实现原理与源码解析
> Author: shaobaobaoer
> Mail: shaobaobaoer@126.com
> WebSite: shaobaobaoer.cn
> Time: Sunday, 26. July 2020 11:52AM
HashMap 继承关系
Map 是 Key-Value 对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。
HashMap 是基于哈希表的 Map 接口的实现，以 Key-Value 的形式存在，即存储的对象是 Entry (同时包含了 Key 和 Value) 。
在HashMap中，其会根据hash算法来计算key-value的存储位置并进行快速存取。特别地， HashMap最多只允许一条 Entry 的键为Null(多条会覆盖)，但允许多条Entry的值为Null 。此外，HashMap 是 Map 的一个非同步的实现。
必须指出的是，虽然容器号称存储的是 Java 对象，但实际上并不会真正将 Java 对象放入容器中，只是在容器中保留这些对象的引用。也就是说，Java 容器实际上包含的是引用变量，而这些引用变量指向了我们要实际保存的 Java 对象。（justloveyou_）
HashMap 构造函数
HashMap 一共提供了四个构造函数，其中 默认无参的构造函数 和 参数为Map的构造函数 为 Java Collection Framework 规范的推荐实现，其余两个构造函数则是 HashMap 专门提供的。
1. public HashMap()
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
装填因子为0.75，其他数值都是默认的
2. HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能小于 0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) // 不大于2**30
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 装填因子不能小于0
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity); // HashMap 的容量必须是2的幂次方，超过 initialCapacity 的最小 2^n
}
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
3. public HashMap(int initialCapacity)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
该方法将直接调用2
4. public HashMap(Map<? extends K, ? extends V> m)
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
装载默认的装填因子，随后初始化table
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
// 在构造函数4的时候，table一定是null的，因此这么搞
// 构造一个与指定 Map 具有相同映射的 HashMap，其 初始容量不小于 16 (具体依赖于指定Map的大小)，负载因子是 0.75
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
} else {
// Because of linked-list bucket constraints, we cannot
// expand all at once, but can reduce total resize
// effort by repeated doubling now vs later
while (s > threshold && table.length < MAXIMUM_CAPACITY)
resize();
}
// 之后将Map里的东西重新塞进去。putVal函数会涉及到很细节的东西，下文细说
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
HashMap 数据结构
我们知道，在Java中最常用的两种结构是 数组 和 链表，几乎所有的数据结构都可以利用这两种来组合实现，HashMap 就是这种应用的一个典型。
实际上，HashMap 就是一个 链表数组，采用拉链法构建链表，如下所示：
后来JDK1.8之后，在table数组拉链法的基础上，当链表长度大于8之后，链表将自动转化为红黑树。利用红黑树快速增删改查的特点提高HashMap的性能。JDK1.8之后，HashMap table数组的样子如下所示：
其中，table数组的重要性不言而喻，其是通过Node类实现的（JDK<1.8为Entry类，实际上它们都实现了Map.Entry接口）
transient Node<K,V>[] table;
Node 为HashMap的内部类，实现了 Map.Entry 接口，其包含了键key、值value、下一个节点next，以及hash值四个属性。是哈希表所存储的元素的具体形式。
HashMap的快速存取
在HashMap中，我们最常用的两个操作就是：put(Key,Value) 和 get(Key)。我们都知道，HashMap中的Key是唯一的，那它是如何保证唯一性的呢？
确定哈希桶数组(table数组)索引位置。
定位Hash元素是增删改的基础，我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，不用遍历链表，大大优化了查询的效率。
来看看hash的实现方式
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 该方法仅存在与jdk1.7中
static int indexFor(int h, int length) {
return h & (length-1);
}
// 在jdk1.8后，该部分代码被挪了出来，写到了取桶索引的地方。
i = (n - 1) & hash(Object)
归纳来说，Hash算法为三步
- 取key的hashCode值
- 取高位字节码，与字节码异或
- 取模
在JDK1.8的实现中，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中.
保存元素与put方法
之前讲到了 putVal 方法，这是HashMap的非常重要的函数，它定义了插入HashMap元素的方法。网上找到了一张图，可以很形象得说明这个过程
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 创建一个 Node
//
Node<K,V>[] tab; Node<K,V> p; int n, i;
// (1) 如果table 为空则创建一个table，大小在resize()方法中有规定
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (2) 计算 index （链的位置）
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // 如果没有哈希冲突，非常棒棒，直接插入
else {
Node<K,V> e; K k;
// (3) 判断节点key是否存在
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 如果正好节点的key与待插入节点的key相同，则直接覆盖掉key
// (4) 判断该链是否为红黑树链
else if (p instanceof TreeNode)
// 如果是，则用红黑树的方法将带插入节点插入链中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// (5) 否则该链为链表
for (int binCount = 0; ; ++binCount) {
// 存在哈希冲突，没有关系，创建一个新的节点e，其为p.next
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与待插入节点的key相同，则直接覆盖掉key
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;
// (6) 扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
扩容机制与resize()
这里参考了https://blog.csdn.net/weixin_43664418/article/details/102164483 老哥的文章。
扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组。
≤JDK1.7
JDK1.8版本往上引入红黑树后，resize变得较为复杂。先来看一下JDK1.7的resize方法（其中的Entry类就是>1.8的Node类）
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 若 oldCapacity 已达到最大值，直接将 threshold 设为 Integer.MAX_VALUE
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return; // 直接返回
}
// 否则，创建一个更大的数组
Entry[] newTable = new Entry[newCapacity];
//将每条Entry重新哈希到新的数组中
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor); // 重新设定 threshold
}
void transfer(Entry[] newTable) {
// 将原数组 table 赋给数组 src
Entry[] src = table;
int newCapacity = newTable.length;
// 将数组 src 中的每条链重新添加到 newTable 中
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null; // src 回收
// 将每条链的每个元素依次添加到 newTable 中相应的桶中
do {
Entry<K,V> next = e.next;
// e.hash指的是 hash(key.hashCode())的返回值;
// 计算在newTable中的位置，注意原来在同一条子链上的元素可能被分配到不同的子链
int i = indexFor(e.hash, newCapacity); // indexFor 见确定索引位置的方法中
// int i= e.hash & (newCapacity-1); 实际对应如下这条语句
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
仔细观察将每条链的每个元素依次添加到 newTable 中相应的桶中的操作，不难发现这是一个头插法重建链表的操作。相信这对于学过数据结构的你来讲不难看懂。
很有意思的是，由于newCapacity变得比原来大了。这就会导致有些链会被分解开。这并不要紧，因为现在的获取桶位置的方法已经从 e.hash & (oldCapacity-1) => e.hash & (newCapacity-1) 了。
具体流程可以看下面的图片
≥JDK1.8
在JDK1.8中，现在使用了是2次幂的扩展(也就是长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
看下图可以明白这句话的意思
设n为table的长度
- 图（a）表示扩容前的key1和key2两种key确定索引位置的示例
- 图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)。因此在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCapacity”。这个Mask就是指最高位了。
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 扩展为两倍
}
else if (oldThr > 0) // 如果原本的阈值大于0，则保留
newCap = oldThr;
else { // 如果原本的阈值等于0（也就是构造函数中调用）则使用默认参数
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
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;
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 { // 链表优化重hash的代码块
// 做了两个链表，一个链表串起来高位结果，另一个链表串起来低位结果
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
// 判断高位结果和低位结果的方法是与原oldCapicity做&，为零就是低位
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCapacity
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到 table 里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到 table 里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab; // 返回table
}
获取元素与get方法
获取元素采用的是.get方法，其中涉及到的一个内部函数getNode，讲解在代码中
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final 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) {
// 如果table数组不为空，长度大于0，且锁定到桶首节点后，该节点非空
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k)))) // 正好key相等，发挥
return first;
if ((e = first.next) != null) { // 若key不相等，则查找下一个元素
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;
}
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
