底层是一个数组,当这个数组满了之后,他就会自动进行扩容,变成一个更大的数组,让你在里面可以去放更多的元素
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取模,取模性能不高,位运算的性能比较高