HashMap 获取元素的大致过程

hashMap 中

map.put("A",1);map.put("B",2);map.put("C",3);

然后执行

map.get("B");

请描述一下 HashMap 获取元素的大致过程。

HashMap 实际过程

第一步：计算 hash

hash=hash(key)

第二步：计算桶下标

假设容量为16

index=(n-1)&hash

例如：

15&hash

得到桶的位置。

第三步：找到桶

table[index]

此时有三种情况：

情况1

桶为空

returnnull;

直接结束。

情况2

桶第一个节点就是目标

先比较：

hash是否相同&&equals是否相同

满足直接返回。

HashMap 不会一上来就遍历链表。

先看头节点是不是。

情况3

发生哈希冲突

开始向后查找。

JDK8：

• 链表遍历
• 红黑树查找

追问

为什么既要比较 hash，又要比较 equals？

例如：

"Aa".hashCode()"BB".hashCode()

它们的 hashCode 相同。

如果只比较 hash：

Aa==BB

显然错误。

所以：

hash相同+equals相同

才能认为是同一个 key。