序
有点心急，总想着赶紧码字，但是这周确实忙，周一晚上陪着小平过生日，吃的姜东虎烤肉，一下班就去排队，等了20几桌，一个半小时。单价170几的肉确实好吃，但是吃着肉也感觉到肉疼。撑到不行，印象中还是第一次吃烤肉没剩肉，以前在大学的时候，经常被室友拉着去吃烧烤，那家是他内蒙老乡开的，吃的我到现在完全对烧烤无感。现在那个内蒙莽汉也许久未联系了，以前能称得上穿一条裤子。周二晚上加班到10点半，打车的时候等了司机十几分钟最后说不来了，郁闷....周三晚上吃多了，不宜坐着，站着看了会B站，看了一会书《构建之法》，然后一看看到11点多，有时间写写读后感，出校门以后没写个读后感了。书归正题：HashMap源码解读。
注意：本文源码都是以JDK1.8版本讲解
HashMap 应该算我们在日常开发中用的最多的集合之一，所以有很大必要深入了解下，里面有很多细节以及优化技巧都值得我们深入学习。
1. 数据结构
在 JDK1.8 中，HashMap 是由 数组+链表+红黑树构成(以前是数组+链表)的链表散列。
Node<K,V> 类型的数组 table。Node 是一个内部类，用来表示一个key-value。它包含了四个字段，next 字段之向下一个 Node，可以看出 Node 是一个链表。
// 存储元素的数组
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 哈希值 在数组下标位置的关键
final K key;
V 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; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(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;
}
}
数组中的每个位置被当成一个桶，一个桶存放一个链表 Node。当添加Node时，通过key 的 hashCode()经过扰动函数处理过后得到 hash 值，然后通过 除留余数法 hash % n计算出桶的位置(n为数组的长度，实际hash % n优化成(n-1) & hash)。当一个桶中需要放多个时，判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
hashMap
可以看到如果
hash 相同 但是key不一样时，则用next连接起来，就像拉链一样，如果连的太长了，则查找的时候影响效率，所以在1.8的时候，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。除了拉链法，常见的解决hash冲突的方法：
- 开放地址法: 当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止.
- 线行探查法: 当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。
- 建立一个公共溢出区： 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表
类的基本属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*加载因子)超过临界值时，会进行扩容
int threshold;
// 加载因子
final float loadFactor;
}
threshold = size * loadFactor，当元素个数大于等于threshold(容量阈值)时，HashMap 会进行扩容操作。
负载因子为什么要设置为0.75：源码注释有解释：是时间和空间的权衡，负载因子是0.75的时，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。
put方法
HashMap 允许插入键为 null 的键值对。可以看到，key 为 null 时，无法计算出 hashCode, 默认 hash 值为0。
具体方法源码如下，已经加上基本注释
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 计算哈希值 与（&）、非（~）、或（|）、异或（^）
static final int hash(Object key) {
int h;
// 为null时 直接返回0。
// h和h>>>16异或。高16位和低16位都参与了计算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 实际调用的方法
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为空 或者长度为0 先初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//将p赋值为对应桶位置的头结点
//如果key对应的数组位置还是空着的 则直接new一个放进去
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// e为要插入的node
Node<K,V> e; K k;
// 如果头结点的hash 和key的hash一样 且key也一样 则该节点即为要插入的节点
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;
}
// 不是尾节点 则 比对hash 和 key是一样 是 退出循环 e已经在上面赋值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//p指向下一个节点
p = e;
}
}
// 如果e不为空 则替换e的value 并返回旧值
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;
}
为什么(n - 1) & hash 为什么等于 hash % n
这也是table数组长度永远为2的幂次方的原因。
我们都知道，当一个数为2的幂次方时，该数的二进制位必为1后面跟着全是0。比如32的二进制为100000。任何一个数和x和32的模的结果必定在031之间，即0000011111之间。这取决于x的二进制的低4位。
比如244和32取模
244 % 32 = 20
11110100 244
&
00011111 32-1
=
00010100 20
总结 HashMap put 过程。
- 计算 key 的 hash 值。
- 检查table是否为空或长度为0，为空需要进行扩容，初始化容量是 16 ，负载因子默认 0.75。
- 计算 key 在数组中的下标。(容量 - 1) & hash.
- 下标的位置为 null,直接插入
- 下标的位置有值
1 判断key是否一样，如果一样这直接覆盖。
2 反正，先判断是否为红黑树，是，则按照红黑树算法插入。
3 反正，正常遍历链表判断key是否一样，如果一样则直接替换。
4 没找到则在尾端插入。
5 判断链表长度是否大于8，则转成红黑树。 - 判断是否需要扩容，触发扩容
我们来看下JDK 1.7的put方法，主要不同点是，1.7为头插入法，即出现hash冲突时在头部插入的，而1.8是在尾部插入的，因为头插入在多线程环境下存在死循环问题，当然两者在多线程环境下都存在丢失数据的问题，所以要保证数据安全，多线程环境下还是使用ConcurrentHashMap 。
public V put(K key, V value)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 先遍历
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); // 再插入
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 头插法，链表头部指向新的键值对
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
resize() 扩容
HashMap 的 table 长度为 N，已经存在的元素格式为size。平均来算，那么每条链表的长度大约为 size/N，因此查找的复杂度为 O(size/N)。
为了查询效率，应该使 size/N 越小越好,而size是用户需要存放的数据，无法控制，所以只能控制table的长度N，也就是说 table 要尽可能大。但是也不能一上来就给N设置很多，这样造成浪费。HashMap 采用动态扩容来根据当前的 size 来调整 M 值，使得空间效率和时间效率都能得到保证。
扩容会进行一次重新hash分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 扩容再大 也不能大过最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 扩充为原来的2倍(左移 即为乘2)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// threshold>0说明调用了设置该值的构造方法
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 初始化
else {
// signifies using defaults
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) {
// 每个数组里面的Node链表都重新分配
// 不是带着原下标 就是待在(原下标+oldCap)的下标
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 {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// e.hash & oldCap，若为0则索引位置不变，不为0则新索引=原索引+旧数组长度
// 原索引
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;
}
扩容的时候重新确定下标，我们看到源码里是使用e.hash & oldCap的结果是否为0来处理的。
我们知道 e.hash & (oldCap-1) 来确定下标(n位的二进制),而且e.hash & oldCap 就是确定第n+1位的二进制数是否为0。
比如容量16的数组扩容为32:
oldCap: 00010000
newCap: 00100000
假如一个 Key，它的哈希值 hash 在第 5 位：
- 为 0，那么 hash%00010000 = hash%00100000，桶位置和原来一致；
- 为 1，hash%00010000 = hash%00100000 + 16，桶位置是原位置 + 16。
get
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;
// table不为空 长度不为0 并且hash所在的桶存在值
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 头结点 key一样
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;
}
equasl和hashcode
相信很多人都注意到了，比较两个key是否一样，显示hash值必须一样，然后再是equasl必须一样，所以HashMap的Key需要重写 equals()和 hashcode()方法？
原生的 hashcode 就是根据内存地址算出来的一个值,不可能存在一样的情况。
原生的 equals 方法就是用==比对对象是否一样。
后记
码字感觉很没效率。应该要找到高效的方法，最起码不能再一句话上纠结好几分钟....。本来也就没啥写作水平，改来改去也就那样。好几个小时也就也就憋出点东西，费时费力，希望能高效点，能保持积极性的同时保证质量。
对于很多人看来可能都是很基础的东西，为了尽量讲的通俗，尽量更深入，也还是花了点功。毕竟加深了自己的理解，希望大家能有所收获。
量变引发质变，经常进步一点点，期待蜕变的自己。
网友评论