1. HashMap

• Hash 算法及寻址优化：把 key 的 hashcode 转换为二进制(32位)，将 hashcode 右移 16 位后和原 hashcode 做异或(实际上就是把搞16位挪到低16位，和原低16位异或，目的是让高低16位都参与 hash 计算)，然后把结果和size-1做与运算(这其实和对 hash 做size取模效果是一样的，但与运算的性能高于取模运算)。 总结：hash优化，就是让高低16位参与运算，尽量避免hash冲突；寻址优化，就是用与代替取模。
• 解决hash冲突：用链表+红黑树，但链表长度大于8转为红黑树。
• HashMap 扩容：当发生扩容，可能需要对原有元素进行rehash，若扩容后的size二进制未多出一个bit，则hash不变，否则 hash = index + oldCapacity

版权所有

版权归属：Mayee

许可证：署名 4.0 国际 (CC-BY-4.0)