讲一讲 get 方法全过程
我们上面讲了 HashMap 中的 put 方法全过程，下面我们来看一下 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; // 找到真实的元素位置 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 总是会check 一下第一个元素 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 如果不是第一个元素，并且下一个元素不是空的 if ((e = first.next) != null) { // 判断是否属于 TreeNode，如果是 TreeNode 实例，直接从 TreeNode.getTreeNode 取 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 如果还不是 TreeNode 实例，就直接循环数组元素，直到找到指定元素位置 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
来简单介绍下吧，首先会检查 table 中的元素是否为空，然后根据 hash 算出指定 key 的位置。然后检查链表的第一个元素是否为空，如果不为空，是否匹配，如果匹配，直接返回这条记录；如果匹配，再判断下一个元素的值是否为 null，为空直接返回，如果不为空，再判断是否是 TreeNode 实例，如果是 TreeNode 实例，则直接使用 TreeNode.getTreeNode 取出元素，否则执行循环，直到下一个元素为 null 位置。
getNode 方法有一个比较重要的过程就是 「(n - 1) & hash」，这段代码是确定需要查找的桶的位置的，那么，为什么要 (n - 1) & hash 呢？
n 就是 HashMap 中桶的数量，这句话的意思也就是说 (n - 1) & hash 就是 (桶的容量 - 1) & hash
// 为什么 HashMap 的检索位置是 (table.size - 1) & hash
public static void main(String[] args) {Map<String,Object> map = new HashMap<>();
// debug 得知 1 的 hash 值算出来是 49
map.put("1","cxuan");
// debug 得知 1 的 hash 值算出来是 50
map.put("2","cxuan");
// debug 得知 1 的 hash 值算出来是 51
map.put("3","cxuan");
}
那么每次算完之后的 (n - 1) & hash ，依次为
也就是 「tab[(n - 1) & hash]」 算出的具体位置。
HashMap 的遍历方式
HashMap 的遍历，也是一个使用频次特别高的操作
HashMap 遍历的基类是 HashIterator，它是一个 Hash 迭代器，它是一个 HashMap 内部的抽象类，它的构造比较简单，只有三种方法，「hasNext 、 remove 和 nextNode」 方法，其中 nextNode 方法是由三种迭代器实现的
这三种迭代器就就是
KeyIterator，对 key 进行遍历
ValueIterator，对 value 进行遍历
EntryIterator， 对 Entry 链进行遍历
虽然说看着迭代器比较多，但其实他们的遍历顺序都是一样的，构造也非常简单，都是使用 HashIterator 中的 nextNode 方法进行遍历
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
HashIterator 中的遍历方式
abstract class HashIterator {
Node<K,V> next; // 下一个 entry 节点
Node<K,V> current; // 当前 entry 节点
int expectedModCount; // fail-fast 的判断标识
int index; // 当前槽
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {...}
}
next 和 current 分别表示下一个 Node 节点和当前的 Node 节点，HashIterator 在初始化时会遍历所有的节点。下面我们用图来表示一下他们的遍历顺序
你会发现 nextNode() 方法的遍历方式和 HashIterator 的遍历方式一样，只不过判断条件不一样，构造 HashIterator 的时候判断条件是有没有链表，桶是否为 null，而遍历 nextNode 的判断条件变为下一个 node 节点是不是 null ，并且桶是不是为 null。
HashMap 中的移除方法
HashMap 中的移除方法也比较简单了，源码如下
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
remove 方法有很多，最终都会调用到 removeNode 方法，只不过传递的参数值不同，我们拿 remove(object) 来演示一下。
首先会通过 hash 来找到对应的 bucket，然后通过遍历链表，找到键值相等的节点，然后把对应的节点进行删除。
关于 HashMap 的面试题
HashMap 的数据结构
JDK1.7 中，HashMap 采用位桶 + 链表的实现，即使用链表来处理冲突，同一 hash 值的链表都存储在一个数组中。但是当位于一个桶中的元素较多，即 hash 值相等的元素较多时，通过 key 值依次查找的效率较低。
所以，与 JDK 1.7 相比，JDK 1.8 在底层结构方面做了一些改变，当每个桶中元素大于 8 的时候，会转变为红黑树，目的就是优化查询效率。
HashMap 的 put 过程
大致过程如下，首先会使用 hash 方法计算对象的哈希码，根据哈希码来确定在 bucket 中存放的位置，如果 bucket 中没有 Node 节点则直接进行 put，如果对应 bucket 已经有 Node 节点，会对链表长度进行分析，判断长度是否大于 8，如果链表长度小于 8 ，在 JDK1.7 前会使用头插法，在 JDK1.8 之后更改为尾插法。如果链表长度大于 8 会进行树化操作，把链表转换为红黑树，在红黑树上进行存储。
HashMap 为啥线程不安全
HashMap 不是一个线程安全的容器，不安全性体现在多线程并发对 HashMap 进行 put 操作上。如果有两个线程 A 和 B ，首先 A 希望插入一个键值对到 HashMap 中，在决定好桶的位置进行 put 时，此时 A 的时间片正好用完了，轮到 B 运行，B 运行后执行和 A 一样的操作，只不过 B 成功把键值对插入进去了。如果 A 和 B 插入的位置（桶）是一样的，那么线程 A 继续执行后就会覆盖 B 的记录，造成了数据不一致问题。
还有一点在于 HashMap 在扩容时，因 resize 方法会形成环，造成死循环，导致 CPU 飙高。
HashMap 是如何处理哈希碰撞的
HashMap 底层是使用位桶 + 链表实现的，位桶决定元素的插入位置，位桶是由 hash 方法决定的，当多个元素的 hash 计算得到相同的哈希值后，HashMap 会把多个 Node 元素都放在对应的位桶中，形成链表，这种处理哈希碰撞的方式被称为链地址法。
其他处理 hash 碰撞的方式还有 「开放地址法、rehash 方法、建立一个公共溢出区」这几种方法。
HashMap 是如何 get 元素的
首先会检查 table 中的元素是否为空，然后根据 hash 算出指定 key 的位置。然后检查链表的第一个元素是否为空，如果不为空，是否匹配，如果匹配，直接返回这条记录；如果匹配，再判断下一个元素的值是否为 null，为空直接返回，如果不为空，再判断是否是 TreeNode 实例，如果是 TreeNode 实例，则直接使用 TreeNode.getTreeNode 取出元素，否则执行循环，直到下一个元素为 null 位置。
HashMap 和 HashTable 有什么区别
见上
HashMap 和 HashSet 的区别
见上
HashMap 是如何扩容的
HashMap 中有两个非常重要的变量，一个是 loadFactor ，一个是 threshold ，loadFactor 表示的就是负载因子，threshold 表示的是下一次要扩容的阈值，当 threshold = loadFactor * 数组长度时，数组长度扩大位原来的两倍，来重新调整 map 的大小，并将原来的对象放入新的 bucket 数组中。
HashMap 的长度为什么是 2 的幂次方
这道题我想了几天，之前和群里小伙伴们探讨每日一题的时候，问他们为什么 length%hash == (n - 1) & hash，它们说相等的前提是 length 的长度 2 的幂次方，然后我回了一句难道 length 还能不是 2 的幂次方吗？其实是我没有搞懂因果关系，因为 HashMap 的长度是 2 的幂次方，所以使用余数来判断在桶中的下标。如果 length 的长度不是 2 的幂次方，小伙伴们可以举个例子来试试
❝例如长度为 9 时候，3 & (9-1) = 0，2 & (9-1) = 0 ，都在 0 上，碰撞了；
❞
这样会增大 HashMap 碰撞的几率。
HashMap 线程安全的实现有哪些
因为 HashMap 不是一个线程安全的容器，所以并发场景下推荐使用 ConcurrentHashMap ，或者使用线程安全的 HashMap，使用 Collections 包下的线程安全的容器，比如说
Collections.synchronizedMap(new HashMap());
还可以使用 HashTable ，它也是线程安全的容器，基于 key-value 存储，经常用
HashMap 和 HashTable 做比较就是因为 HashTable 的数据结构和 HashMap 相同。
上面效率最高的就是 ConcurrentHashMap。
后记
文章并没有叙述太多关于红黑树的构造、包含添加、删除、树化等过程，一方面是自己能力还达不到，一方面是关于红黑树的描述太过于占据篇幅，红黑树又是很大的一部分内容，所以会考虑放在后面的红黑树进行讲解。
</div>
