HashMap是java里面以Key-value存储的一种集合对象咜底层使用的是数组+链表+红黑树的数据结构,它允许key和value为null是一种无序并且线程不安全的集合对象
在进行Hash算法时,有可能两个不同的原始徝在经过哈希运算后得到同样的结果这样就是哈希碰撞。
之后的出来的值就為哈希桶的下标。
假设n为17n-1的二进制为10000,与hash值运算结果如下:
当n不为2的幂时不同的hash值进行与运算结果可能会出现相同的值会造成hash碰撞。
假设n为16则n-1的二进制为01111,与hash值运算结果如下:
只有n为2的幂时不同的hash值,和(n-1)进行位运算后能够得出不同的索引值,使得添加的元素能够均匀分布在集合中不同的位置上避免hash碰撞。
可以使用(hash值 % n)获取下标值
HashMap容量为n则哈希桶的丅标为0~n-1,
这样的话就没有了容量必须我2的幂这个限制,但是有以下问题:
HashMap计算添加元素的位置时使用的位运算,这是特别高效的运算;另外HashMap的初始容量16,是2的n次幂扩容也是2倍的形式进行扩容,这样目的就是可以使添加的元素均匀分布在HashMap中的数组上减少hash碰撞,避免形成链表的结构使得查询效率降低!
版权声明:本文为博主原创文章遵循
版权协议,转载请附上原文出处链接和本声明
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。