1.HashMap底层原理 数据结构
底层使用哈希表(数组+链表进行存储),在jdk1.8后 当链表长度大于等于8时 将链表转为红黑树 ,时间复杂度由O(n)变为O(logn)
2.HashMap的put过程
(1)对key计算hash值 求下标
(2)如果没有发生hash碰撞,直接放入桶中
(3)如果发生碰撞,放在链表的后面 并计算链表长度 大于8转为红黑树
(4)如果节点已经存在进行覆盖
(5)如果长度大于(长度*负载因子0.75) 进行扩容resize
3.HashMap中的hash函数是怎么实现的
(1)高16bit不变 低16bit和高16bit做了一个异或(^)
(2)(n-1)&hash 得到下标
4.扩容过程是什么样的,原来某位置的元素,移动到了新数组,位置怎么确定
(1)扩容为原来的2倍,对每个节点重新计算hash值
(2)可能的位置是原来的位置 或者是(原下标+原容量)的位置
5.hash冲突还有那些解决办法
开放定址法(线性探测) 链地址法 再哈希法
6.链表查找某个元素的时间复杂度是O(n),怎么优化
单向链表 无法优化 一种是hashMap实现的红黑树 另一种是可以通过双向链表来实现 这样就可以使用折半查找 但是因为要保存上一个元素的地址 更加耗费内存空间
