java面试题02

1.HashMap的put过程

1. table是否是一个空数组，是则inflateTable(threshold)
2. 判断key是否是null，是则putForNullKey(value)
3. hash(key)计算哈希码（高位低位移位异或，尽可能增大所有位的影响）
4. indexFor(hash, table.length)(hash & (length)-1)哈希码按位与length-1，找到桶位
5. 判断找到的桶位是否为null

不是null，则e=e.next，遍历桶位，拿新key的hash和内容与旧key的hash值和内容比较，如有相等的，则新key的value覆盖旧的value，返回旧的value。遍历完没有相等的则继续addEntry。是null，addEntry头插法插入entry

1. 是null，则addEntry头插法插入entry

是null，则addEntry头插法插入entry

​ 先判断size是否大于等于阈值，是则resize扩容，new一个newTable，transfer转移

​ 没超过阈值，则creatEntry创建键值对，size++

​ Entry e = table[桶位]把桶位原先第一个元素赋给e

​ table[桶位] = new Entry<>(hash ,key, value, e)新创建的entry放到桶位，并且新创建的entry的next只想原先的第一个e，头插法完成

2.HashMap的容量为什么必须是2的次方数

找桶位 hash & (length - 1)

2的次方数减1，二进制是纯1，找桶位时，hash按位与可以散列到所有桶位，充分利用桶位。

假如容量是10，二进制1010，减1后1001，那么按位与永远散列不到0010即2号桶位

3.HashMap1.7计算哈希码为什么要同时用到高低位

1.7中哈希值右移20位后与自身异或

让高位参与哈希值计算，增大高位的影响，减少哈希碰撞的几率

4.在HashMap中同一个桶位中的元素，哈希码都是一样的码？为什么？

不是，哈希码不一样，但是与（length-1）按位与之后找到的桶位可能是一样的。

哈希码不一样，高位低位异或之后低位一样，则会到同一个桶位。

5.在HashMap扩容时，同一个桶位中的元素会被分配到新数组中的什么位置，为什么？

原位和原位+数组原长度的位置

例，原长度16，扩容后32，按位与15，按位与31，1111和11111低四位一样，所以重新按位与之后只会差16