HashMap面试题

使用最快的速度，最精简的语言给大家带来最全面的面试题

前言

  HashMap常见面试题，其实现原理和JDK1.7与JDK1.8的区别，和HashMap的扩容机制和寻址算法等全方面面试题，带给大家，最精简的总结。

一、HashMap实现原理

1.底层使用hash表，数组+链表/红黑树

2.put元素，用key的hashcode计算当前元素数组的下标

3.存储时hash值相同，比较key,如果key的值相同则覆盖，如果不同（hash冲突），则储存在链表/红黑树中

4.获取数值的时候，找hash值对应的下标，判断key是否相同

二、HashMap在JDK1.7和JDK1.8中的区别

（1）1.8之前使用的是拉链法，如果遇到hash冲突，直接头插法插入链表

（2）1.8及以后，当链表长度大于8，数组长度大于64时，链表转为红黑树，减少搜索的时间，扩容的时候使用resize()方法，当红黑树的节点小于等于6个的时候红黑树退化为链表

三、HashMap的put方法是如何进行的？

1.判断数组table是否为空，否则resize进行初始化，

2.根据key计算hash值，为数组中存储的下标

3.table[i]为空则直接插入，如果table[i]的首元素和key一样则直接覆盖

4.1.判断是否是红黑树，是的话直接进行插入

4.2.遍历table[i]链表，进行插入，在遍历的过程中如果遇到相同的key则覆盖

5.插入后，size是否超过threshould（数组长度*loadFactor加载因子（默认值为0.75））,否则进行扩容

四、HashMap的扩容机制

1.添加元素进行初始化，调用resize方法，初始化数组长度为16，每次达到threshold阈值，进行扩容

2.每当进行扩容的时候，数组长度扩容为原来的二倍

3.扩容的时候需要新建数组，将老的数组的值拷贝到新的数组中

（1）在扩容的时候不存在hash冲突，则新位置为e.hash&(newCap-1)

（2）在扩容的时候存hash冲突，判断e.hash&oldCap是否为0？如果为零则使用原始数组的下标

如果不为零，则为原始下标+原始数组长度

五、HashMap的寻址算法

1.计算对象的hashCode值

2.调用hash方法进行二次运算，hashCode值右移16位异或运算，为了让哈希分布更加的均匀

3.使用（Capcity-1）&hash得到索引

六、HashMap数组的长度为甚要是2的次幂？

1.计算索引时效率更高，2的次幂可以使用位与代替模运算

2.扩容时重新计算索引的效率更高

3.hash&oldcap==0，是的话使用原位置，否则：旧位置+oldcap

总结

  已经断更两天了，因为摸鱼，前几天太晚了，看完背完面试题，已经很晚很晚了，所以博主进行了偷懒，(*^▽^*)，此后博主还会不断进行更新，在学习完面试题后会不断总结给大家。