讲一讲 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。
后记
文章并没有叙述太多关于红黑树的构造、包含添加、删除、树化等过程,一方面是自己能力还达不到,一方面是关于红黑树的描述太过于占据篇幅,红黑树又是很大的一部分内容,所以会考虑放在后面的红黑树进行讲解。