|
HashMap底层是由数组+链表（jdk1.8之后是数组+链表+红黑树）实现的。HashMap查询速度之所以快，其精髓在于数组，数组是一种n内存连续的数据结构，利用哈希值，计算出key在数组中的下标，就能帮我们迅速定位到目标数据。所以计算下标方法直接决定了hashmap的性能。
如果key的哈希值是m，hashmap容量是n，为了使数据在数组上均匀分布，必然采用取模的方法，即其下标为m%n，但这样取模性能十分低下。计算机中运算效率最高的是位运算，所以最好采用位运算。有研究发现，如果n=2^x,
恰好有m%n == m & (2^x -1 )，①故想用位运算取代模运算，其容量必须是2的x次幂
②HashMap的长度一定是2的次幂，还有另外一个原因，那就是在扩容迁移的时候不需要再重新通过哈希
定位新的位置了。扩容后，元素新的位置，要么在原脚标位，要么在原脚标位+扩容长度这么一个位置.是否移位，由扩容后表示的最高位是否1为所决定，由于移动的方向只有一个，即向高位移动。因此，可以根据对最高位进行检测的结果来决定是否移位，从而可以优化性能，不用每一个元素都进行移位，因为为0说明刚好在移位完之后的位置，为1说明需要移动oldCap.
|