小知识

xiaoxiao2021-02-28  11

java基础

hashmap 

一、1.6 和 1.8 的区别 为什么这么做?  从 1.数据结构区别  2.进而引起时间复杂度的区别

当元素所插入的index为空时, 时间复杂度为O1,不为空:a.小于8,则为On, b.大于8 则为logn 采用红黑树 2分查找法

二、put/get的流程  

 put

 1.判断index是否有值,无值则直接new node 插入。 有值则看当前节点 key hash 值是不是都相等。相等则直接覆盖。不相等,则继续遍历,如果出现key hash相等,则将value覆盖。当遍历到链表尾巴时,如果还不存在hash值,key值相等的Node时,则直接向链表中加新的元素。

get 

同理:首先根据key的hash^hash>>>16 找到index 如果该位置有值 而且next == null 则直接取出来。如果不为null 则要看表头节点是不是 treeNode类型,是的话直接用树的二分查找法。不是的话用链表的遍历查找。

resize方法:是通过old桶极限值位向左加1bit实现的。也就是翻1倍。现将老的Node表保存在临时变量,然后桶临界值大小扩大两倍。然后再遍历老的hashMap node表。 一个个重新根据key hash值存到新 node表中。

clear 

直接遍历table,然后将元素置为null

foreach  

会不断看 modCount 数目。 如果发生变化,抛出异常。

负载因子

 作用:合理控制table 也就是node 数组大小。提高操作效率。 因为table太大,则遍历 查找 效率低。 如果太小 则发生hash碰撞多, 同样操作效率下降。尽量是桶较多,hash碰撞较少、

亮点:

a.hashMap 其实在 new 的时候并没有初始化, 是在put操作时进行初始化。 而且大小是2的倍数。 作用:最大限度节约资源。

线程不安全的体现:rehash时,多个线程同时去重排列。会导致相互等待,发生死锁。

hashmap  怎么去处理hash碰撞    

 1.从put操作的流程去答。  然后引申一下hashMap的key的类型,是不可变的,而且最好是要合理的重写 hashcode equal 方法,使得 发生hash碰撞的概率更小。

b.hashmap怎么去找到index  通过 tab[i=(n-1)&hash]       hash = key.hashcode()^hash>>>16

c.衡量HashMap是否进行Resize的条件如下: 

HashMap.Size >= Capacity * LoadFactor (默认情况下是 == 原来长度 * 0.75)

d.HashCode,它是一个本地方法,实质就是地址取样运算;

==是用于比较指针是否在同一个地址;

equals与==是相同的

转载请注明原文地址: https://www.6miu.com/read-2650075.html

最新回复(0)