JDK1.8
一、关键字段
//创建 HashMap 时未指定初始容量情况下的默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap 的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//HashMap 默认的装载因子,当 HashMap 中元素数量超过 容量*装载因子 时，进行 resize() 操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//用来确定何时将解决 hash 冲突的链表转变为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 用来确定何时将解决 hash 冲突的红黑树转变为链表
static final int UNTREEIFY_THRESHOLD = 6;
/* 当需要将解决 hash 冲突的链表转变为红黑树时，需要判断下此时数组容量，若是由于数组容量太小（小于 MIN_TREEIFY_CAPACITY ）导致的 hash 冲突太多，则不进行链表转变为红黑树操作，转为利用 resize() 函数对 hashMap 扩容 */
static final int MIN_TREEIFY_CAPACITY = 64;
//保存Node<K,V>节点的数组
transient Node<K,V>[] table;
//由 hashMap 中 Node<K,V> 节点构成的 set
transient Set<Map.Entry<K,V>> entrySet;
//记录 hashMap 当前存储的元素的数量
transient int size;
//记录 hashMap 发生结构性变化的次数（注意 value 的覆盖不属于结构性变化）
transient int modCount;
//threshold的值应等于 table.length * loadFactor, size 超过这个值时进行 resize()扩容
int threshold;
//记录 hashMap 装载因子
final float loadFactor;
二、算法特点
1.容量初始化
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
threshold 为阈值。1.7版本直接取 initialCapacity ，1.8做了运算，查看 tableSizeFor 方法
/**
* 找到大于或等于 cap 的最小2的幂
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
假设个数带入计算一下可以发现，其实就是将 cap 二进制的各位都转化为1，在最后返回前加上1，保证是2的幂
int n = cap - 1的作用是为了避免 cap 本来就是2的幂的情况，导致在 cap 的基础上又乘了次2
int 是32位，n 右移十六位后作或运算，正好将最高位以后的所有位都转化为了1，再右移32位（结果为0）作或运算就没有意义了
2.键在桶中位置
// 计算键的哈希值在哈希表（桶数组）中的位置
key.hash & (table.length-1)
等价于对桶数组长度取余
HashMap 中桶数组的长度 length 总是2的幂，这样在计算位置中，table.length-1的结果，二进制形式上各位都为1，在与 hash的&运算时，增加了结果的可能性，减少了哈希碰撞几率，让元素能够更均匀的分布在桶数组上。
3.哈希转换
/**
* 计算键的 hash 值
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看这个方法的逻辑好像是通过位运算重新计算 hash，那么这里为什么要这样做呢？为什么不直接用键的 hashCode 方法产生的 hash 呢？
当哈希表容量不大时，单纯利用 hashCode 和容量进行 & 运算，hashCode 只有低位参与了计算。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。
hashCode 方法产生的 hash 是 int 类型，32 位宽，前16位为高位，后16位为低位。
像上图中，让高位数据与低位数据进行异或，变相的让高位数据参与到计算中，以此加大低位信息的随机性。
除此之外，重新计算 hash 的另一个好处是可以增加 hash 的复杂度。当我们覆写 hashCode 方法时，可能会写出分布性不佳的 hashCode 方法，进而导致 hash 的冲突率比较高。通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。这也就是为什么 HashMap 不直接使用键对象原始 hash 的原因了。
4.扩容后重新计算在桶中位置
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历链表，并将链表节点按原顺序进行分组
do {
next = e.next;
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);
// 将分组后的链表映射到新桶中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
resize 扩容方法中的一段，当旧的表中有元素或链表，且链表还未转化为红黑树，对新表进行重新映射的实现
e.hash & oldCap - 1是对表容量取模，计算key在表中位置
注意e.hash & oldCap此运算，因为表容量一直为2的幂，所以 oldCap 的二进制形式除最高位以外，其余低位都为 0
与键的哈希值作 & 运算，可以判断键对应位上的值是1还是0
当为1时，e.hash & newCap - 1计算下的新位置，是原位置加上 oldCap 的值
当为0时，依旧为原位置，不发生变化
可以假设值带入验证。这样将原链表分为了两组，每组都用一个 Head 和 Tail 引用，形成两条链表，引用在新表上
三、构造
//构造方法１，指定初始容量及装载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的幂
//注意此种方法创建的 hashMap 初始容量的值存在 threshold 中
this.threshold = tableSizeFor(initialCapacity);
}
//构造方法２，仅指定初始容量，装载因子的值采用默认的 0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造方法３，所有参数均采用默认值
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
四、插入
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 初始化表
if ((tab = table) == null || (n = tab.length) == 0)
...
// 表对应位置为null，直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
...
// 表位置上已存在元素
else {
// 已存在，且在第一个位置上的情况
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
···
// 已树化的情况
else if (p instanceof TreeNode)
···
// 仍是链表的情况
else {
for (int binCount = 0; ; ++binCount) {
// 没有此元素，开始插入
if ((e = p.next) == null) {
...
// 链表数已大于树化阈值，插入后开始树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
···
}
// 链表中存在的情况
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
...
...
}
}
// 如果存在就进行替换
if (e != null) { // existing mapping for key
...
}
}
// 大于扩容阈值，开始扩容
if (++size > threshold)
...
return null;
}
- 必要的话初始化表
- 对应表中位置为null直接插入，不是null分情况讨论
- 根据树化、链化不同，实现不同；链化时超过了树化阈值进行树化
- 如果链表中或者树中已存在key，进行替换
- 最后再判断元素个数是否大于表阈值进行扩容
//读懂这个函数要注意理解 hash 冲突发生的几种情况
//１、两节点 key 值相同（hash值一定相同），导致冲突
//２、两节点 key 值不同，由于 hash 函数的局限性导致hash 值相同，冲突
//３、两节点 key 值不同，hash 值不同，但 hash 值对数组长度取模后相同，冲突
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
//从根节点开始查找合适的插入位置（与二叉搜索树查找过程相同）
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1; // dir小于０，接下来查找当前节点左孩子
else if (ph < h)
dir = 1; // dir大于０，接下来查找当前节点右孩子
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
//进入这个else if 代表 hash 值相同，key 相同
return p;
/*要进入下面这个else if,代表有以下几个含义:
1、当前节点与待插入节点 key 不同, hash 值相同
2、ｋ是不可比较的，即ｋ并未实现 comparable<K> 接口
（若 k 实现了comparable<K> 接口，comparableClassFor（k）返回的是ｋ的 class,而不是 null）
或者 compareComparables(kc, k, pk) 返回值为 0
(pk 为空 或者 按照 k.compareTo(pk) 返回值为０，返回值为０可能是由于
ｋ的compareTo 方法实现不当引起的，compareTo 判定相等，而上个 else if 中 equals 判定不等)*/
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//在以当前节点为根的整个树上搜索是否存在待插入节点（只会搜索一次）
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
//若树中存在待插入节点，直接返回
return q;
}
// 既然ｋ是不可比较的，那我自己指定一个比较方式
dir = tieBreakOrder(k, pk);
}//end else if
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//找到了待插入的位置，xp 为待插入节点的父节点
//注意TreeNode节点中既存在树状关系，也存在链式关系，并且是双端链表
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//插入节点后进行二叉树的平衡操作
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}//end for
}//end putTreeVal
static int tieBreakOrder(Object a, Object b) {
int d;
//System.identityHashCode()实际是利用对象 a,b 的内存地址进行比较
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
- 比较键与键之间 hash 的大小，如果 hash 相同，继续往下比较
- 检测键类是否实现了 Comparable 接口，如果实现调用 compareTo 方法进行比较
- 如果仍未比较出大小，就需要进行仲裁了，仲裁方法为 tieBreakOrder
五、扩容
final Node<K,V>[] resize() {
// 如果 table 不为空，表明已经初始化过了
if (oldCap > 0) {
// 当 table 容量超过容量最大值，则不再扩容
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; // double threshold
}
// 有参构造的情况开始初始化
else if (oldThr > 0) // initial capacity was placed in threshold
// 阈值暂存着桶数组初始容量，后续阈值重新计算
newCap = oldThr;
//调用无参构造方法时，桶数组容量为默认容量，
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 有参构造重新计算阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
...
}
...
// 将旧桶数组中的数据映射到新桶中
if (oldTab != null) {
//把 oldTab 中的节点 reHash 到 newTab 中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//若节点是单个节点，直接在 newTab 中进行重定位
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//若节点是 TreeNode 节点，要进行 红黑树的 rehash 操作
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//若是链表，进行链表的 rehash 操作
else { // preserve order
...
}
}
}
}
return newTab;
}
- 根据是否初始化桶数组，使用的有无参构造，计算新桶数组的容量 newCap 和新阈值 newThr
- 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
- 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。
// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
/*
* 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
* 下面的循环是对红黑树节点进行分组，与上面类似
*/
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
// 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
/*
* hiHead == null 时，表明扩容后，
* 所有节点仍在原位置，树结构不变，无需重新树化
*/
if (hiHead != null)
loHead.treeify(tab);
}
}
// 与上面类似
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
从源码上可以看得出，重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。
不同的地方在于，重新映射后，会将红黑树拆分成两条由 TreeNode 组成的链表。
如果链表长度小于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。
否则根据条件重新将 TreeNode 链表树化。
参考
HashMap 源码详细分析(JDK1.8)：https://segmentfault.com/a/1190000012926722?utm_source=tag-newest
JDK1.8源码阅读系列之四：HashＭap (原创)：https://www.cnblogs.com/Michaelwjw/p/6411176.html
网友评论