HashMap学习

骑猪看日落 2022-03-20 01:44 176阅读 0赞

转载：  
[HashMap实现原理及源码分析][HashMap]  
[什么是 哈希表 HashMap 中数组的 size 为什么必须是 2 的整数次幂][_ HashMap _ size _ 2]

HashMap 用于许多缓存技术  
存储位置 = f（关键字） f：哈希函数  
HashMap:链地址法：（数组（主体）+链表（解决哈希冲突））  
HashMap实现原理：Entry数组 （）  
Entry<K,V>静态内部类  
构造器：  
HashMap(int initialCapacity（初始容量）, float loadFactor（负载因子）)  
put操作：在执行put操作的时候才真正构建table数组  
put(K key, V value)

1.  inflateTable(threshold)用于为主干数组table在内存中分配存储空间

*  1.1roundUpToPowerOf2(int number)确保capacity为大于或等于toSize的最接近toSize的二次幂
 *  1.2Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值.

2.hash(Object k)用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀  
3.indexFor(int h, int length) 返回数组下标，获取实际的存储位置  
h&（length-1）保证获取的index一定在数组范围内  
![在这里插入图片描述][20190209155418231.png]  
4.addEntry(int hash, K key, V value, int bucketIndex)  
当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。  
4.1resize(int newCapacity)  
4.2transfer(Entry\[\] newTable, boolean rehash)如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index  
get(Object key)操作:  
![在这里插入图片描述][20190209155654409.png]  
在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。

[HashMap]: https://www.cnblogs.com/chengxiao/p/6059914.html
[_ HashMap _ size _ 2]: https://blog.csdn.net/a2615381/article/details/78151061
[20190209155418231.png]: /images/20220320/c207c862d5f8429a984a324a10bd700f.png
[20190209155654409.png]: /images/20220320/aec4502349ec4799bb6407d9d6542b17.png