五、HashMap对象hash冲突的优化
HashMap并没有使用传统的hash算法而是对他进行了进一步的优化从而避免了hash冲突。
核心的代码:
public V put(K key, V value) {
// 存储数据的使用调用hash方法得到一个hash值
return putVal(hash(key), key, value, false, true);
}
//hash方法对hash算法进行了进一步的优化
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
从代码中可以看出来他是先得到了一个hash值然后再右移了16位然后再进行了一个按位异或的操作。
即使看看懂了他的算法可能还是很多有都会有一个疑问这样就可以降低hash冲突嘛？当前这样是不可以的但是但是在结合后面要说的高效寻址算法就可以,现在先简单的说一下这个寻址算法,该算法基本只会使用到hash值得低16位进行运算,而低16位最多表示到65535,范围并不大所以出现冲突得概率还是挺大的,但是如果加入了高16位的特征那么该hash值得低16位就多了很多的变化从而避免了hash冲突。
#
六、put方法存储数据
// onlyIfAbsent 如果为true则表示不修改存在的value
// evict 如果为false则表示hash表还处于创建模式
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; // 存储数据的Hash表
Node<K,V> p; //一个节点数据
int n, i;
//如果table为空
if ((tab = table) == null || (n = tab.length) == 0)
/*
执行resize扩容操作,如果hash表为null那么使用默认的容量来进行扩容
如果已经有了容量则在原来的基础上扩容2倍
如果容量已经大于了最大容量则扩容为int的最大值
*/
n = (tab = resize()).length; //hash表的容量
// 通过高效寻址算法得到一个索引然后获取当前索引的值,
// 如果值为null则直接再该节点上创建对象
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//如果获取的索引节点上已经存在了数据则走else
Node<K,V> e;
K k;
/*
如果获取到了索引上的节点的hash值等于传递进来的hash
且索引上节点的key值等于传递过来的key值同时key值不为null
则直接用新的数据替换老的数据-数据的修改操作
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果p已经是一个树形节点数据则走树形结构的添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 走链表的添加如果链表长度大于8则转换为树
for (int binCount = 0; ; ++binCount) {
//如果p没有下一个节点数据了则直接添加一个节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
/*
如果p还有下一个链表节点则获取下一个节点的hash和传递过来的hash进行比较
如果hash相等且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;
//如果存储的容量大于了threshold(总容量*负载因子)则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
值得注意的是当我们的链表长度到达了8的时候还会检测一下table的长度是否达到了MIN_TREEIFY_CAPACITY ,如果达到了则转换位树如果达不到则进行数组的扩容。
七、高效的寻址算法
在put数据的时候会通过高效的寻址算法来获取数组的下标,具体的高效算法如下:
(n - 1) & hash // n代表的是数组的length
一般情况下数组的长度都不会特别的大,同时之前也给大家讲过低16位全部是1就可以表示65535,所以该高效寻址算法基本上只会用到低16位进行运算,这也是为什么上面我们在讲高效hash算法的时候会把高16位全部设置位0的原因。
同时为什么这个算法是高效的的呢？这其实是一个相对的概念,如果让我们去求一个索引的下标可能很多人会使用取余的方式去实现,那么取余的数学运算相对于位运算来说位运算就要高效很多了。
八、hash冲突了如何解决
- 如果是在hash表中冲突了则判断是否是同一个可以如果是则修改数据
- 如果是在链表中冲突了则遍历链表看是否有key值相同的如果有则进行数据的修改如果没有则添加一个节点
- 如果添加的节点大于8且hash表的总容量小于64则会进行数组的扩容然后重新rehash此时整个数组和链表都会发生变化-因为扩容以后rehash以后原本hash冲突的现在可能不会冲突了
- 如果是在树中冲突了则通过变色或者旋转的方式来解决
九、resize以后链表的rehash过程
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
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 {
// preserve order
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;
}
}
}
}
}
数组扩容以后会重新rehash，然后重新计算一个数组下标的位置来存储数据,那么rehash的过程中他就会打破原来的链表比如原来链表中有四个数据的,rehash以后就可以只有2个数据另外2个数据在另一个索引下标中。
