HashMap的底层结构实现以及存取元素的过程
关于HashMap和HashSet区别的最后一行内容的修正：(修正的内容只是自己对Java8-HashMap源码的理解，如有错误之处，还请各位大佬，不吝指教
HashMap和HashSet在存储一个新元素时，计算hashcode的方式都是通过调用HashMap中的put()方法去进行的，然后在找到对应的插入位置，在这之前二者没有什么区别，但是在对插入位置上存在相同元素的处理上就出现了不同：HashMap在存储一个新元素时调用的是put()方法，如果这个元素已经存在了，那么HashMap的put()方法会将新元素把就元素覆盖掉，然后返回旧元素；HashSet在存储一个新元素时调用的是add()方法，通过add()方法再去调用put()方法，在HashSet存储新元素时发现已经存在相同元素，则会返回false，因为HashSet中是不允许有重复元素出现的。
==============================================================================
最近暑期实习的面试，发现身边有很多同学面试的时候都被问到了HashMap的底层相关的知识，感觉比较重要，特意整理了一下，发在牛客上存个档，也分享给大家。内容是通过查阅网上的资料、Java8-HashMap的源码、以及chatGPT的回答结合自己的理解总结梳理而成，如有错误之处，还请各位大佬，不吝指教
主要参考链接：https://pdai.tech/md/java/collection/java-map-HashMap&HashSet.html
说到HashMap就会联想到HashSet，那么这二者有什么区别呢？其实二者在Java中有着相同的实现，HashSet仅仅是对HashMap做了一层包装，HashSet底层就是基于HashMap实现的。以下简要介绍下二者的区别：
|
|
实现了 | 实现了 |
存储键值对 | 仅存储对象 |
调用 | 调用 |
当新元素已经存在时，put()方法使用新元素把旧元素覆盖，然后返回旧元素 |
当新元素已经存在时，add()方法返回false，相同元素不可以重复插入到HashSet中 |
另外，HashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素；除该类未实现同步外，其余跟Hashtable大致相同；跟TreeMap不同，该容器不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个HashMap的顺序可能会不同。这里再简要说一下HashMap与TreeMap的区别：
TreeMap和HashMap都继承自AbstractMap，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap接口。
实现NavigableMap接口让TreeMap有了对集合内元素的搜索的能力。
实现SortedMap接口让TreeMap有了对集合中的元素根据键排序的能力。默认是按key的升序排序，不过我们也可以指定(自定义)排序的比较器。
以下是对HashMap的详细介绍
Java7 - HashMap
HashMap的底层数据结构的实现：数组+链表的形式，也就是链表散列。
先大致说一下往HashMap中放元素的过程：
HashMap通过key的hashcode经过扰动函数处理过后得到的hash值，然后再通过 (n - 1) & hash 判断当前元素存放的位置(n指的是数组长度)，如果当前位置存在元素的话，就判断该元素与要存入的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
扰动函数
：所谓扰动函数指的就是HashMap的hash方法，使用hash方法(扰动函数)是为了防止一些实现效果比较差的hashcode()方法，换句话说，使用扰动函数之后，可以减少碰撞。(我的理解：可能会有一些key，你通过hashcode()方法计算出的hash值，冲突的可能性比较大，进而要进行频繁的重哈希操作，这个时候就可以使用扰动函数(也就是HashMap的hash方法)，通过扰动函数计算出的hash值，冲突的可能性较小，就不用就行频繁的重哈希操作了，这样就会在一定程度上提高效率。)
拉链法
关于 Java7--HashMap 中的put()、get()、remove()方法
get()
get(Object key) 方法根据指定的 key 值返回对应的 value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.getValue()。因此getEntry()是算法的核心。算法思想是首先通过hash()函数得到对应bucket的下标，然后依次遍历冲突链表，通过key.equals(k)方法来判断是否是要找的那个entry。
上图中hash(k)&(table.length-1)等价于hash(k)%table.length，原因是HashMap要求table.length必须是2的指数
因此table.length-1的二进制表示的低位全是1，跟hash(k)相与会将哈希值的高位全抹掉，剩下的就是余数了。
解释上面的话：在HashMap中，为了提高性能，数组的长度table.length必须是2的指数，即 table.length = 2^n，其中n为正整数。这是因为在计算一个键值对应的桶的索引时，HashMap会用键的哈希值对数组长度取模，即 index = hash(k) % table.length，这样可以保证索引值在0和 table.length-1之间。但是，取模操作比位运算操作要慢，为了提高性能，HashMap采用了位运算操作来代替取模操作。因为刚刚说了，table.length一定是2的指数，也就是说table.length-1的二进制表示的低位全是1，因此对哈希值(hash)进行与(&)操作，可以将哈希值的高位抹掉，只保留哈希值的低位，得到一个在0和table.length-1之间的整数值。这个整数值就是键对应的桶的索引，即 index = hash(k) % table.length。这样可以避免取模操作，提高运算性能。
对于“table.length一定是2的指数，也就是说table.length-1的二进制表示的低位全是1”这句话的解释：
如果一个数组的长度为table.length(table.length的值一定是2的指数)，那么table.length-1的二进制表示中，低位(也就是二进制表示中的最右边的几位)都是1，而高位(也就是二进制表示中的最左边的几位)一定是0。例如，如果一个数组的长度为8，那么8的二进制表示是1000，而7的二进制表示是0111；如果数组长度为16，那么16的二进制表示是10000，而15的二进制表示是01111，可以看到7和15的二进制表示中低位全是1。所以使用table.length-1对k的hash值进行与(&)运算，可以将哈希值的高位全都变成0，只保留低位，从而保证得到的哈希值在0到n-1之间(不会数组越界)。
final Entry<K,V> getEntry(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[hash&(table.length-1)];// 得到冲突链表
e != null; e = e.next) {// 依次遍历冲突链表中的每个entry
Object k;
// 依据equals()方法判断是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
put()
put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于getEntry()方法；如果没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry，插入方式为头插法。
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 = hash & (table.length-1);// hash%table.length
}
// 在冲突链表头部插入新的entry
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
remove()
remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry(修改链表的相应引用)。查找过程跟getEntry()过程类似。
final Entry<K,V> removeEntryForKey(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);// hash & (table.length-1)
Entry<K,V> prev = table[i];// 得到冲突链表
Entry<K,V> e = prev;
while (e != null) {// 遍历冲突链表
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
modCount++; size--;
if (prev == e) table[i] = next;// 删除的是冲突链表的第一个entry
else prev.next = next;
return e;
}
prev = e; e = next;
}
return e;
}
Java8 - HashMap
Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。相比于之前的版本，JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。(将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树)
TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。
Java7 中使用 Entry 来代表每个 HashMap 中的数据节点，Java8 中使用 Node，基本没有区别，都是 key，value，hash 和 next 这四个属性，不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。通常，我们根据数组元素中，第一个节点数据类型是 Node 还是 TreeNode 来判断该位置下是链表还是红黑树。
关于Java8 的put()、数组扩容、get()方法
put()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 第四个参数 onlyIfAbsent 如果是 true，那么只有在不存在该 key 时才会进行 put 操作
// 第五个参数 evict 我们这里不关心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次 put 值的时候，会触发下面的 resize()，类似 java7 的第一次 put 也要初始化数组长度
// 第一次 resize 和后续的扩容有些不一样，因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 找到具体的数组下标，如果此位置没有值，那么直接初始化一下 Node 并放置在这个位置就可以了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {// 数组该位置有数据
Node<K,V> e; K k;
// 首先，判断该位置的第一个数据和我们要插入的数据，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) {
// 插入到链表的最后面(Java7 是插入到链表的最前面)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD 为 8，所以，如果新插入的值是链表中的第 8 个
// 会触发下面的 treeifyBin，也就是将链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在该链表中找到了"相等"的 key(== 或 equals)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 此时 break，那么 e 为链表中[与要插入的新值的 key "相等"]的 node
break;
p = e;
}
}
// e!=null 说明存在旧值的key与要插入的key"相等"
// 对于我们分析的put操作，下面这个 if 其实就是进行 "值覆盖"，然后返回旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
和 Java7 稍微有点不一样的地方就是，Java7 是先扩容后插入新值的，Java8 先插值再扩容。
数组扩容
resize() 方法用于初始化数组或数组扩容，每次扩容后，容量为原来的 2 倍，并进行数据迁移。
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;
}
// 将数组大小扩大一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 将阈值扩大一倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 对应使用 new HashMap(int initialCapacity) 初始化后，第一次 put 的时候
newCap = oldThr;
else {// 对应使用 new HashMap() 初始化后，第一次 put 的时候
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 用新的数组大小初始化新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 如果是初始化数组，到这里就结束了，返回 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 {
// 这块是处理链表的情况
// 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序
// loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表
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;
// 第二条链表的新的位置是 j + oldCap，这个很好理解
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
get()
相对于 put 来说，get 的过程就比较简单了，所以在这块再深入探讨一下，当元素存储在红黑树中时，是如何进行数据的取操作的(主要是我同学面试的时候被问到了：当数据以红黑树的方式存入HashMap中时，应该如何取这个数据🧐)
首先看一下get的过程：
- 计算
key的hash值，根据 hash 值找到对应数组下标:hash & (table.length-1) - 判断数组该位置处的元素是否刚好就是我们要找的，如果不是，继续往下走
- 判断该元素类型是否是
TreeNode，如果是，用红黑树的方法取数据，如果不是，那就是链表了，那就遍历链表，直到找到相等(==或equals)的 key
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) {
// 判断第一个节点是不是就是需要的
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 判断是否是红黑树 -> 是红黑树的话 -> 调用getTreeNode()方法 -> 这个方法又会调用find()方法去寻找对应的TreeNode
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;
}
getTreeNode()方法
当判断出元素类型为TreeNode后，就调用getTreeNode(hash, key)方法。
// HashMap.java源码中 第1888-1883行
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
通过给定的的hash值和键key，从当前节点开始向下查找包含指定键的树节点。方法的实现中，首先通过判断当前节点是否有父节点来确定应该从哪个节点开始查找。如果当前节点有父节点，则从根节点开始查找，否则从当前节点开始查找。具体的查找工作由find方法完成，它会递归地向下查找包含指定键的树节点，并返回查找到的节点。最终，getTreeNode()方法返回查找到的树节点。
find()方法
// HashMap.java源码中 第1858-1891行
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
find()方法使用do-while循环来实现递归查找，每次迭代中，通过当前节点的哈希值和键对象，决定向左子树、右子树或者当前节点中查找。
1、初始化本地变量
TreeNode<K,V> p = this;
初始化变量 p 为当前节点，即接下来在以该节点为根节点的子树中查找。
2、循环查找
do {
// ...
} while (p != null);
使用循环迭代地查找包含指定键的树节点。循环条件是只要当前节点不为 null 就继续查找。
3、根据哈希值hash比较确定向左子树或右子树查找
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
首先比较当前节点的哈希值 ph 和指定键的哈希值 h 的大小关系，如果 ph 大于 h，则说明要查找的键在当前节点的左子树中，将变量 p 更新为左子节点 pl；如果 ph 小于 h，则说明要查找的键在当前节点的右子树中，将变量 p 更新为右子节点 pr。
4、根据键对象key比较确定向左子树或右子树查找
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
如果当前节点的哈希值 ph 和指定键的哈希值 h 相等，则需要根据键对象来确定是否找到了指定的节点。如果当前节点的键对象 pk 和指定键 k 相等，则说明已经找到了指定的节点，直接返回当前节点 p。如果当前节点的键对象 pk 和指定键 k 不相等，则需要根据键对象的比较结果来确定向左子树还是向右子树查找。如果当前节点的左子节点 pl 为 null，则向右子树查找；如果当前节点的右子节点 pr 为 null，则向左子树查找。
5、根据键对象的比较结果确定向左子树还是向右子树查找
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
如果当前节点的键对象 pk 和指定键 k 不相等，而且当前节点的左右子节点都不为 null，则需要根据键对象的比较结果来确定向左子树还是向右子树查找。在这种情况下，如果键的类型实现了 Comparable 接口，可以使用 compareTo 方法来比较键的值；否则，需要使用提供的比较器 Comparator 来比较键的值。在 HashMap 中，为了提高性能，如果节点的键类型实现了 Comparable 接口，就使用键对象的 compareTo 方法来比较键的值；否则，使用 Comparator。这就是代码中的 kc 变量的作用，它保存了键对象的比较器。因此，首先判断变量 kc 是否为 null，如果不为 null，说明已经有个比较器可以用来比较键的值了。如果为 null，则调用 comparableClassFor(k) 方法来获取键的类型。如果键的类型实现了 Comparable 接口，comparableClassFor(k) 方法将返回键的类型；否则返回 null。 然后使用 compareComparables 方法来比较键的值，如果比较结果不为 0，则说明找到了要查找的节点。compareComparables 方法的作用是比较两个键的值，如果它们的类型相同，就使用 compareTo 方法来比较；否则，使用 Comparator 来比较。最后根据比较结果更新节点的位置，如果比较结果小于 0，说明要查找的键在左子树中，就更新 p 为左子树根节点；如果比较结果大于 0，说明要查找的键在右子树中，就更新 p 为右子树根节点。如果比较结果为 0，说明找到了要查找的节点，直接返回该节点即可。
总的来说，这段代码的作用是在哈希表中查找键为 k 的节点。如果节点的哈希值与 k 的哈希值不相等，就继续往下查找；如果节点的哈希值与 k 的哈希值相等，就比较节点的键值与 k 的键值，根据比较结果更新节点的位置。
6、递归查找
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
如果上述条件都不满足，则需要递归地从右子树中查找包含指定键的树节点。调用右子节点的 find 方法，传入参数 h、k 和 kc，查找并返回结果。如果右子树中找到了指定节点，则直接返回结果 q；否则需要向左子树继续查找，将变量 p 更新为左子节点 pl。
7、未找到
return null;
如果循环结束后还未找到指定的节点，则说明没有找到，返回 null。
第一次在牛客上发这种长篇的文章，不知道该如何附加上目录
第一次发真的是没经验，有些参考javaGuide上的知识点，就直接拿着上面带水印的发上来了，想着不去除水印，这不才是正确的借鉴方式么，也算是维护了人家的IP了吧，没想到今天想着复习笔记呢，图片竟被和谐掉了，真的不理解
