解释一下HashMap 的 get 方法逻辑
参考回答
HashMap
的 get(Object key)
方法用于根据键(key
)获取对应的值(value
)。其核心逻辑是:
- 根据键的
hashCode()
计算哈希值,确定该键所在的桶(bucket
)。 - 遍历该桶中的链表(或红黑树)来查找目标键。
- 如果找到对应的键,返回其对应的值;否则返回
null
。
详细讲解与拓展
1. HashMap
的底层数据结构
HashMap
的底层是一个数组,每个数组元素是一个链表或红黑树(在冲突元素多时)。- 通过键的哈希值确定数据存储在哪个数组索引位置(即“桶”)。
2. get
方法的核心逻辑
get(Object key)
的执行过程如下:
(1) 计算哈希值
- 首先,
HashMap
使用键的hashCode()
方法计算哈希值,并通过位运算进一步压缩哈希值,以确定该键对应的桶(数组索引位置)。 -
源码中,计算哈希值的方法:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
key.hashCode()
:计算键的哈希值。h ^ (h >>> 16)
:高位和低位混合,减少哈希冲突。
(2) 定位桶
- 根据计算得到的哈希值,找到该键所在的桶(
bucket
)。 -
数组索引通过以下公式计算:index = (n – 1) & hash其中,n是数组的长度,hash
是上一步计算的哈希值。
- 位与运算 (
&
) 是一种高效的取模方式,用来确保索引值在数组范围内。
- 位与运算 (
(3) 遍历桶中的节点
- 如果桶中没有元素(即链表为空),直接返回
null
。 - 如果桶中有元素,则通过以下步骤查找目标键:
- 遍历桶中的链表或红黑树。
- 比较每个节点的哈希值是否等于目标键的哈希值。
- 如果哈希值相等,再通过
equals()
方法进一步比较键是否相等。 - 如果找到了目标键,返回对应的值;否则继续查找。
(4) 找不到键时
- 如果遍历完链表或红黑树仍未找到目标键,返回
null
。
3. get
方法源码分析
以下是 Java 8 中 HashMap
的 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) {
// 检查第一个节点是否是目标节点
if (first.hash == hash && // 比较哈希值
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 遍历链表或树查找目标节点
if ((e = first.next) != null) {
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; // 没找到返回 null
}
4. 关键点详解
(1) 哈希值计算
hash(key)
方法会对键的哈希值进行高低位混合(h ^ (h >>> 16)
),减少冲突。- 计算索引时使用
(n - 1) & hash
,通过位运算代替取模操作,效率更高。
(2) 桶内查找
- 链表查找:
- 如果冲突较少,桶中的节点以链表形式存储,按顺序遍历链表查找目标节点。
- 红黑树查找:
- 如果桶中的元素数量超过阈值(默认 8),链表会转换为红黑树,红黑树的查找时间复杂度为 O(log n)。
(3) 键的相等性比较
- 首先比较键的哈希值(
hash
)。 - 如果哈希值相同,再通过
equals()
方法比较键的内容。
5. 示例代码
示例:模拟 get
方法的逻辑
import java.util.HashMap;
public class HashMapGetExample {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
// 添加元素
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);
// 使用 get 方法
System.out.println("Value for key 'A': " + map.get("A")); // 输出:1
System.out.println("Value for key 'D': " + map.get("D")); // 输出:null
}
}
6. get
方法的时间复杂度
- 最优情况:
- 如果键的分布均匀,且桶内没有冲突(每个桶只存一个元素),
get
操作的时间复杂度为 O(1)。
- 如果键的分布均匀,且桶内没有冲突(每个桶只存一个元素),
- 最差情况:
- 如果发生大量哈希冲突,所有元素都存储在同一个桶内,链表查找的时间复杂度为 O(n)。
- 在 Java 8 中,引入红黑树后,最差情况下的时间复杂度降为 O(log n)。
7. 总结
- 执行步骤:
- 计算哈希值。
- 定位桶的位置。
- 遍历桶内的链表或红黑树。
- 比较哈希值和键的内容,找到匹配的键值对。
- 时间复杂度:
- 在理想情况下为 O(1),在最差情况下(冲突严重时)为 O(log n)。
- 性能优化:
- Java 8 通过红黑树优化了冲突场景下的性能,避免了链表退化为线性查找。
- 注意事项:
- 键的
hashCode()
和equals()
方法的正确性至关重要,直接影响get
方法的准确性和效率。
- 键的