一、HasMap如何解决哈希冲突
1、什么是哈希冲突?
哈希冲突就是指当插入一个Entry<k,v>时,将key经过hash计算出的下标中已经存在另一个Entry<k,v>,这时就会产生哈希冲突。
2、如何解决?
解决哈希冲突的方式有四种:
1、开放地址法(包括线性探测、二次探测、伪随机探测等)
2、链地址法
3、再哈希发
4、建立一个公共的溢出区
那么HashMap采用的是哪种方法呢?
要知道HashMap采用哪种方法就要知道它的实现原理。
众所周知,HasMap的底层是通过数组+链表实现的。此处的“链表”就是HashMap为我们提供的解决哈希冲突的方法。也就是连地址法。
当HashMap中插入一个Entry数据时,抽象会根据插入数据的key计算出一个哈希值,该哈希值就是数组的下标,如果该下标里已经存有值,则意味着产生哈希冲突,这时hashmap会以单向链表的形式对存储Entry。
二、HashMap扩容时限插入还是先扩容?
当然是先扩容!!!
①HashMap的初始容量默认为16,负载因子默认为0.75。当插入的数据数量大于二者之积时就要考虑进行扩容。
②HashMap的扩容是需要将其扩至2倍,再哈希计算将所有数据移至新的HashMap中,如果先插入,那我岂不是要多计算一次哈希值,多一次插入吗?