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.
相关文章
- 01-14【004期】你知道为什么HashMap是线程不安全的吗?
- 01-14关于hashMap的长度为什么是2的n次方的问题
- 01-14HashMap为什么是2倍扩容
- 01-14HashMap 是线程安全的吗,为什么不是线程安全的(最好画图说明多线程环境下不安全)
- 01-14jdk1.8中HashMap底层链表转红黑树的阈值为什么是8?链表查询慢为啥不直接用红黑树?
- 01-14HashMap的负载因子为什么默认是0.75?这篇文章告诉你答案
- 01-14为什么hashmap以2的倍数作为桶的长度,同时以2作为扩容倍数
- 01-14为什么 HashMap 是线程不安全的?(1)
- 01-14为什么 HashMap 是线程不安全的?(2)