面试考察的绝对重点。以下是问题导航
- hashMap数据结构
- hash函数设计
- 扩容 为什么扩容为2
- Put/get方法
- 链表转红黑树
- 1.7 & 1.8差别
- 死循环条件
基础知识
^ 异或：相同的为0 不同的为1
& 与运算：A与B都为1结果为1 其他为0
| 或运算：A或B其中一个为1则为1 其他都为0
hashMap数据结构
略。
hash函数设计
int h = (key == null) ? 0 :(h = key.hashcode)^(h>>>16)
int index = h & (length-1);
- h>>>16 被称为扰动函数 使用无符号右移16位后再与原hashcode异或 原因是 .hashcode 方法计算的结果为32位,但是length位数比较低，直接计算index高位不参与容易冲突，右移16再异或可以混合低位和高位增加随机性。从打降低hash冲突的风险。
- 为什么是 &(length-1): Java中对2的n次方取余等于减一的与运算，效率更高。
扩容步骤
resize()方法中若数组未初始化则初始化数组，若是已经初始化的数组，则数组扩容为之前的2倍。扩容过程如下
- 遍历数组若旧数组中不存在hash冲突的节点，直接移动到新的数组当中去。int index = (e.hashcode&(newLength -1))
- 若存在冲突的节点，树节点进行拆分，链表节点会保持原有顺序，依然是尾插法。
- 判断元素是否在原有位置
e.hashcode&(oldcap)==0这是因为oldCap的高位和newCap-1的高位是一致的。 - 发现元素不是在原有位置，更新hitail和hiHead的指引关系。
- 将index未改变的复制到新的数组当中去。
- 将index发生改变的元素复制到新数组当中去。新的下标为oldindex+oldCap
为什么扩容为2
因为在扩容中判断元素是否在原位置使用的是与操作。都为1才能为1。假设数组从8扩容到16,决定为扩容后是否在原位置的为hashCode的高位值。1/0会被分流到不同的位置当中去，从而在扩容中可以让数组分布更加均匀。
old.length -1 = 7 0 0 1 1 1
e.hashCode = k x p x x x
==============================
0 0 y y y
扩容前index值由低三位决定,与操作让高位以上都为0
e.hashcode&(oldCap-1)
new.length -1 = 15 0 1 1 1 1
e.hashCode = k x p x x x
==============================
0 z y y y
扩容后唯一发生变化的是高位z。若z为0那么位置不变。
若z的位置为1 那么新的index等于oldCap+oldIndex
新的index的值为zyyy z000等于oldCap 0yyy等于oldIndex
e.hashcode&(newCap-1)
old.length = 8 0 1 0 0 0
e.hashCode = k x p x x x
==============================
0 z 0 0 0
此时e.hashcode & oldCap == 0 那么则z为0 说明位置不变。
put/get方法
get方法
- hash & (length -1)确定元素位置，如果没碰撞直接放到bucket里；
- 如果碰撞了，以链表的形式存在buckets后；
- 如果碰撞导致链表过长(就把链表转换成红黑树(JDK1.8中的改动 大于等于8)；
- 如果节点已经存在就替换old value(保证key的唯一性)
- 如果bucket满了(超过load factor*current capacity)，就要resize。
put方法
- hash & (length -1)确定元素位置
- 判断第一个元素是否是我们要找的位置
- 判断节点是否为树，若是在树节点查找
- 判断节点是否为链表，若是在链表查找
- 找到对应的元素返回，无则返回空值
死循环
在JDK1.7当中由于头插法在并发情况下会出现成环的情况。假设数组index[1]=1->5->9
- 当前A线程正在准备扩容 e=1 e.next=5让出时间片 B线程完成扩容
- 扩容后的newtabIndex[1]=9->5->1 由于头插法 顺序被置换
- 此时A线程继续执行 newtabIndex[1]会挂载到e=1上
- 然后执行 newtabIndex[1] = e.next 给出一个 e=1 指向e.next =5的引用导致成环
- 在当前位置getKey时候就会引起死循环问题。