
课程咨询: 400-996-5531 / 投诉建议: 400-111-8989
认真做教育 专心促就业
数据结构是我们在学习java编程开发的时候需要重点掌握的编程知识,而今天我们就通过案例分析来了解一下,HashMap数据结构基础知识。
1、HashMap集合简介
HashMap基于哈希表的Map接口实现,是以key-value存储形式存在,即主要用来存放键值对。HashMap的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。
JDK1.8之前的HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了节解决哈希碰撞(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)而存在的(“拉链法”解决冲突)。
JDK1.8之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(或者红黑树的边界值,默认为8)并且当前数组的长度大于64时,此时此索引位置上的所有数据改为使用红黑树存储。
2、哈希碰撞相关的问题
哈希表底层采用何种算法计算hash值?还有哪些算法可以计算出hash值?
底层是采用key的hashCode方法的值结合数组长度进行无符号右移(>>>)、按位异或(^)、按位与(&)计算出索引的
还可以采用:平方取中法,取余数,伪随机数法。这三种效率都比较低。而无符号右移16位异或运算效率是高的。
当两个对象的hashCode相等时会怎么样?
会产生哈希碰撞,若key值内容相同则替换旧的value.否则连接到链表后面,链表长度超过阈值8就转换为红黑树存储。
何时发生哈希碰撞和什么是哈希碰撞,如何解决哈希碰撞?
只要两个元素的key计算的哈希值相同就会发生哈希碰撞。jdk8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树解决哈希碰撞。
如果两个键的hashcode相同,如何存储键值对?
hashcode相同,通过equals比较内容是否相同。相同:则新的value覆盖之前的value不相同:则将新的键值对添加到哈希表中
3、HashMap的扩容机制
HashMap在进行扩容时使用resize()方法,计算table数组的新容量和Node在新数组中的新位置,将旧数组中的值复制到新数组中,从而实现自动扩容。因为每次扩容都是翻倍,与原来计算的(n-1)&hash的结果相比,只是多了一个bit位,所以节点要么就在原来的位置,要么就被分配到"原位置+旧容量"这个位置。
因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来hash值新增的那个bit是1还是0就可以了,是0的话索引没变,是1的话索引变成“原索引+oldCap(原位置+旧容量)”。
【免责声明】:本内容转载于网络,转载目的在于传递信息。文章内容为作者个人意见,本平台对文中陈述、观点保持中立,不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。更多内容请在707945861群中学习了解。