Skip to content

Latest commit

 

History

History
59 lines (20 loc) · 1.54 KB

File metadata and controls

59 lines (20 loc) · 1.54 KB

底层是一个数组,当这个数组满了之后,他就会自动进行扩容,变成一个更大的数组,让你在里面可以去放更多的元素

2倍扩容

[16位的数组,<> -> <> -> <>]

[32位的数组,<> -> <>, <>]

数组长度=16

n - 1 0000 0000 0000 0000 0000 0000 0000 1111

hash1 1111 1111 1111 1111 0000 1111 0000 0101

&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5(index = 5的位置)

n - 1 0000 0000 0000 0000 0000 0000 0000 1111

hash2 1111 1111 1111 1111 0000 1111 0001 0101

&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5(index = 5的位置)

在数组长度为16的时候,他们两个hash值的位置是一样的,用链表来处理,出现一个hash冲突的问题

如果数组的长度扩容之后 = 32,重新对每个hash值进行寻址,也就是用每个hash值跟新数组的length - 1进行与操作

n-1 0000 0000 0000 0000 0000 0000 0001 1111

hash1 1111 1111 1111 1111 0000 1111 0000 0101

&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5(index = 5的位置)

n-1 0000 0000 0000 0000 0000 0000 0001 1111

hash2 1111 1111 1111 1111 0000 1111 0001 0101

&结果 0000 0000 0000 0000 0000 0000 0001 0101 = 21(index = 21的位置)

判断二进制结果中是否多出一个bit的1,如果没多,那么就是原来的index,如果多了出来,那么就是index + oldCap,通过这个方式,就避免了rehash的时候,用每个hash对新数组.length取模,取模性能不高,位运算的性能比较高