HashMap稍微详细的理解
- 2020 年 12 月 7 日
- 筆記
此文章用来记录hashmap的一些特点（在学习中的所了解的，如有不足，请指正）
什么是hash表
概念
先来一段百度百科的的解释
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
所谓的hash表在我看来嘛就是映射嘛，以前嘛要查找一个数或者一个值嘛是通过遍历的形式，这样的话就会有一个问题，那就是太浪费时间了，时间效率非常低，也不能非常低嘛，时间复杂度是O(n)。于是呢，人们为了更快的找到需要查找的值呢就想到了一种办法，将存储的位置与存储的值对应起来，这样查找的效率不就高了很多。但是怎么转换呢，聪明的人类想到了一种办法，利用一种函数映射的形式来解决，这个映射用的函数就叫做hash函数，这个表呢就叫hash散列表，但是呢这是有问题的。那就是
hash表冲突
很好理解嘛，不同的值可能经过hash函数生成同样的索引，这样的话就有冲突了，怎么解决？请看
hash表冲突的解决
我所了解的常用的
- 直接寻址，也叫开放地址法，就是这个不能放我不放了，我放到下一个去，要是下一个还有就继续往后直到找到可以插入的位置，要是都没有，那就考虑一下扩容呗
- hash再散列，就是用别的hash算法再算一遍
- 拉链法，这个方法就是hashmap中用到的方法。不是有冲突嘛，统统拿来，统统放这，一个别想跑。其实就是利用链表，冲突了就追加节点（不是同一个的话才追加）
- 建立公共溢出区，就是冲突了嘛，没坑了，那就走吧，不要呆在这里了
以上就是我所了解的，估计也是常用的吧，不然我也不会了解
HashMap
map的意思嘛，就是映射，才不是地图。Java中的HashMap就是利用hash表加链表实现的K,V形式的数据结构，和python中的字典是一样的。hashmap中的hash冲突的解决利用的是拉链法。1.7之前的拉链是只有链表，而在1.8增加了一个红黑树结构，这是因为，当链表长度太长的时候查找效率比较低。所以在hash桶数据的容量大于等于64以及hash桶内的元素数量大于等于8时就会转换为红黑树。今天我们进入源码一探究竟，先来看个静态常量
static final int MIN_TREEIFY_CAPACITY = 64;
树化:treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果说table 为null或者说容量小于64就扩容，不执行树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 如果说 所在的位置表不为空
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
上面的就是进行树化的条件了，具体流程就算了吧，不看了
扩容：resize()方法
先准备一个重要的方法，resize()方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//判断老表是否为null为null的话长度就是0
int oldThr = threshold; // 保存原来的老阈值
int newCap, newThr = 0; //先将新表的长度 阈值设置为0
if (oldCap > 0) {
//如果说老表的容量大于0且容量大于等于最大容量（MAXIMUM_CAPACITY = 1 << 30）
//就将阈值设为Integer.MAX_VALUE,然后直接返回也就是不再扩容了，仅仅将阈值增大就行了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果说老容量乘以2小鱼最大容量以及大于等于默认的容量（ DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16）
// 就将原来的阈值也扩充为两倍 就是说这里没啥意外容量就定下来了，也是一般的扩容情况
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果说老表的容量小于等于0，但是老阈值大于0，就将新的容量设置为老阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//如果老表的容量以及老阈值都不大于0，就执行初始操作，将新表的容量设置为16，计算新表的阈值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果说得出的新表阈值等于0的话就用新表的容量乘以负载因子，然后如果说新表的容量小于最大值以及新的阈值小于最大值，就将新阈值设为所求，否则就是Integer.MAX_VALUE
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
MAX_VALUE (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循环
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;
//如果说e是treeNode节点，也就是说，这个hash桶里边的节点已经树化过了
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//下面这个else的意思是如果有下一个节点而且没有树化，也是说是链表形式的至少有两个节点
else { // preserve order
//这里就是将链表分成两种一种是高位链表一种是低位链表，至于什么是高低位链表，咱们往下看
//loHead低位头节点
//loTail低位尾节点
Node<K,V> loHead = null, loTail = null;
//hiHead高位头节点
//hiTail低位尾节点
Node<K,V> hiHead = null, hiTail = null;
//next节点
Node<K,V> next;
//开始do..While循环，因为肯定有next节点嘛，不然也到不了这里
do {
//保存一下next节点
next = e.next;
//注意这个与的 是与原来的容量进行比较的没有进行减一哈，减一是求索引用的。
//这里的意思举个例子来说就是比如原来的容量就是16吧，因为这里是位运算嘛，转换成二进制就是10000
//因为这里是等于0 的情况嘛，所以就假设e.hash二进制为1011001111吧，索引算出来就是1111
//运算开始 因不足用0补齐嘛
//1011001111
// 10000
//----------
//0000000000
//嗯 就是这种情况，因为原来容量二进制是5位也就是说如果hash值第五位是0，那么就扩容以后不会有任何变化
//因为扩容是变为原来的2倍，也就是左移一位变为100000。
//那么减1以后就是11111，刨去后边的4个1，两个最高位都是1也就是相同的，可以直接运算
//如果说此时元素的hash值在这个最高位是0的话，那么算出的索引与原来是一样的，这也就是低位索引
//这里只是将低位放在一起
if ((e.hash & oldCap) == 0) {
//如果尾节点为空就初始化（说明头节点也没值）
if (loTail == null)
//这里的头节点指示头所在的位置，以后追加就是用为节点了，高位链表一样如此
loHead = e;
else
//让尾节点的next指向e，
loTail.next = e;
//然后尾节点向后移一位
//这里写成loTail=loTail.next我感觉比较好理解一些
loTail = e;
}
//如果说不是0的话，说明hash值的高位是1，经过运算后就是11111就是原来的索引加上2^4
//就是原来的表的长度，所以高位链表只需要原来的索引加上原来的表的长度就是新的索引
//这里只是将高位放到一起
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//循环结束后，如果说低位链表不为空的话就说明执行了分高低位的工作，而且有低位的存在
//然后只需要将hash桶的节点指向低位链表的头节点，而且因为是低位链表嘛，索引跟原来的一样
if (loTail != null) {
//这里将为节点的next设置为null,因为这再遍历的时候尾节点的next与尾节点指向同一个位置
//因为已经遍历完了嘛，next也就没有值了，所以就清空。高位链表类似
loTail.next = null;
newTab[j] = loHead;
}
//这里判断高位链表是否为空，空的就说明没有高位链表嘛
//不空的话就将原来的索引加上老表的容量，至于为什么，上面已经解释过
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//至此返回新的链表
return newTab;
}
你以为到这里就结束了？no，no，no，还有一个重要的方法，那就是如果是红黑树的话，怎么进行操作呢，就是这个红黑树节点里边的split(this, newTab, j, oldCap)方法了
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index,
int bit//这个bit什么意思呢，我猜是老表的容量，上面传过来的oldCap
) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
//开头雷击，梦回链表
//这怎么和链表的操作差不多呢，也是分成高低位
//其实注释上面也写了嘛
//将树箱中的节点拆分为较高和较低的树箱，如果现在太小，则取消树化。
//为什么红黑树的节点也可以这样呢，因为
/**
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
// needed to unlink next upon deletion
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
*/
//所以有个成员变量是next，那不就跟链表一样了
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
//这个lc吧 low count：低位的数量
//hc呢 high count：高位的数量
int lc = 0, hc = 0;
//显而易见，这里遍历treeNode
//这里为什么不用while循环呢，是不用在外面声明变量嘛
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//这里高低位一分，对应的count++就不展开细说了
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) {
if (lc <= UNTREEIFY_THRESHOLD)
//如果说数量小于等于UNTREEIFY_THRESHOLD=6，就弄成链表
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
//如果不小于6且高位链表不为null就树化
//为啥需要高位链表不为空呢，
/**
这里个人理解，高位链表如果为空，说明旧数组下的红黑树中的元素在新数组中仍然全部在同一个位置，
且先后顺序没有改变，也就是注释中的已经树化了，没有必要再次树化；而当高位节点不为空，
说明原链表元素被拆分了，且位红黑树节点个数大于6，不满足转链表条件，需要重新树化。
此处来自//blog.csdn.net/hengwu1817/article/details/107095871/
*/
//下面的高位链表也是如此
if (hiHead != null) // (else is already treeified)
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);
}
}
}
插入数据 put
调用put(k,v)方法实际上调用的是putVal方法
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//文档给的是创建表的模式，我的理解是可读可写
) {
Node<K,V>[] tab;
Node<K,V> p; //p是table[i]所在的头
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//如果说原来的表不存在或者为空就执行resize()方法，上面已经进入看了一下
//如果说原来的表的位置等于空的话就直接放进去 不存在冲突
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//这里才是重点 到这里说明发生冲突
Node<K,V> e;//e表示要要插入的节点
K k;
//这个判断是看原来的老的hash值跟我传进来的hash值是否相同并且key也相同 或者说key不为空并且相同
//也就是判断一下是不是相同的key 是的话就将p赋值给e
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);
//如果说大于等于8-1也就是7的话就树化 因为要插入元素了嘛，所以插入以后就等于8了
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//这里key相同的话就中断
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//找到了要插入的节点后 如果e不为null 说明key是一样的 只需要替换一下值就好了
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;
}
对于1.7的hashmap的死循环问题以及本篇文章的1.8的死循环数据覆盖问题，以后再总结
