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与==是相同的