0%

HashMap

Posted on

Q1：HashMap 的数据结构？

A1：哈希表结构（链表散列：数组+链表）实现，结合数组和链表的优点。当链表长度超过 8 时，链表转换为红黑树。

Q2：HashMap默认大小是多少？如果传入指定大小是20，那么实际大小是多少？

Q3：HashMap对key进行hash操作的时候有什么特殊处理吗？

Q4：put操作当发生hash碰撞，数据插入链表时，是插入链表头部还是尾部？

Q5：HashMap会出现死循环吗？

Q6：链表长度超过 8 时一定会转换成红黑树吗？

先贴一段简单的代码

1
2
3
4
Map<Integer, Integer> map = new HashMap<>(20);
for (int i = 0; i < 20; i++) {
    map.put(i, i);
}

A2：默认大小是16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
n初始值是19

n		10011
n>1		01001
		11011


n		11011
n>2		00110
		11111


n		11111
n>4		00001
		11111

-------------
n初始值是20

n		10100
n>1		01010
		11110


n		11110
n>2		00111
		11111


n		11111
n>4		00001
		11111

tableSizeFor方法如果入参是2的整数幂则返回本身，如果不是则返回大于入参的最小整数幂，如果入参是20，实际返回值则为32
为什么这么设计，是因为从Key映射到HashMap数组的对应位置，会用到一个Hash函数

1
index =  HashCode（Key） &  （Length - 1）

length取2的整数幂会让数据分布的更均匀

A3:

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这个操作是把 key 的 hashCode 值与 hashCode 值右移 16 位做异或（不同为 1，相同为 0），这样就是把哈希值的高位和低位一起混合计算，这样就能使生成的 hash 值更离散，和A2中的作用是一样的

A4：HashMap在jdk1.7中采用头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题。而在jdk1.8中采用尾插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了

总结一下HashMap1.7和1.8的变化：

  • 1.7采用数组+单链表，1.8在单链表超过一定长度后改成红黑树存储
  • 1.7扩容时需要重新计算哈希值和索引位置，1.8并不重新计算哈希值，巧妙地采用和扩容后容量进行&操作来计算新的索引位置。
  • 1.7插入元素到单链表中采用头插入法，1.8采用的是尾插入法。