HashMap面试题(jdk1.8)

HashMap面试题(jdk1.8)

文章目录

• • • 1、HashMap的特性?
    • 2、HashMap底层原理?
    • 3、HashMap什么时候触发扩容，resize扩容方法如何实现?
    • 4、HashMap的get方法实现？
    • 5、HashMap中的hash函数如何实现的，为什么这么实现，其他的hash函数实现方式？
    • 6、HashMap容量为什么是16，为什么是2的幂，如果是12会如何？
    • 7、HashMap中两个对象的hashCode相等时put会如何，如何获取get两个键相同hashcode的值？
    • 8、HashMap和HashTable的区别?
    • 9、jdk1.7中HashMap有啥缺点(红黑树作用)?

1、HashMap的特性?

（1）HashMap底层是Node数组+链表+红黑树，键值对均允许null且线程不安全;
（2）HashMap默认容量为16、默认阈值12、默认负载因子0.75f、树化阈值>8和64、解树阈值是树节点长度<6;
     解树的阈值仅在扩容方法resize()中使用到，删除方法是先删除树节点，使用特殊根节点的左右树节点判定是否转化链表
  if (root == null || root.right == null ||
      (rl = root.left) == null || rl.left == null) {
      tab[index] = first.untreeify(map);  // too small
      return;
  }
（3）HashMap存储无序且key值重复覆盖，覆盖前提是hash值、key键值相同(使用equals判定);
（4）HashMap扩容为翻倍扩容，基于当前容量进行左移1位扩大容量并迁移数据。
     容量不是2的幂则在第一次put的时候会进行转化为2的幂如：13,9则会变为16,具体可参考tableSizeFor转化方法。

2、HashMap底层原理?

HashMap底层存储为Node数组+链表+红黑树，主要是put方法对键值对进行存储，步骤如下：
    （1）首先是根据key进行Hash即根据key的hashcode进行右移16位，然后再与其进行异或(高低位);
    （2）然后判断是否初始化过，table为空则调用resize方法，此时会进行初始化逻辑，并不会走扩容逻辑;
    （3）再根据扰动算法(即hash)得到的int值对当前容量进行按位与(&)运算，(n-1)&hash值确定桶位置;
    （4）根据桶位置进行空桶插入、链表插入(尾插法)、树节点插入和替换插入，此过程会判定是否进行扩容和树化(链表转树化)。
    HashMap的get方法，与put类似，根据key的扰动算法，然后再进行按位与运算，最终利用key的hash和equals方法去匹配node,
     此过程会存在空桶比较、链表比较、红黑树比较，最终返回value,找不到即返回null。

3、HashMap什么时候触发扩容，resize扩容方法如何实现?

触发扩容resize方法的条件：
（1）第一次put时，如果table未初始化时会触发，此时只会执行初始化逻辑，并不会走扩容逻辑;
（2）当put键值对时，当前数量>扩容阈值时会触发扩容 *** 作;
（3）当链表大于等于8且数组长度小于64时，此时不对链表进行树化，而是对数组进行扩容，均满足时才会转化为红黑树。
resize实现方式：
（1）先判断数组table是否已被初始化，如果为空，则进行数组初始化和阈值计算等;
（2）如果table不为空，则进行下一步扩容，基于当前容量进行翻倍扩容，利用高低位进行归类（可能会存在红黑树解化），然后统一迁移。

4、HashMap的get方法实现？

（1）根据key进行hash即扰动算法，右移16位，然后进行异或，如果key为null,则返回0作为hash值;
（2）根据hash值对(n-1)进行按位与运算确定桶位置;
（3）再根据key的hash值,key使用equals方法进行判定找到node或者TreeNode值，找不到就返回null。

5、HashMap中的hash函数如何实现的，为什么这么实现，其他的hash函数实现方式？

hash函数实现方式：
    （1）先判断key的hashcode是否为null,如果为null,则返回0作为key的hash;
    （2）key不是null的情况就根据key的hashcode进行右移16位，然后进行异或运算(即高低位)。
hash扰动算法的原理：因数组容量正常来说是几十到上百，故对应二进制只有32位中的后面几位，近使用这几位可能会导致大量的hash冲突,
     避免链表过长或红黑树，尽可能的填充数组的桶，利用高低位进行异或，可以减少hash冲突，使得更加分布和散列。
其他hash实现方式：平方取中法，除留余数法，伪随机数法，也可以自定义某种策略进行hash散列。

6、HashMap容量为什么是16，为什么是2的幂，如果是12会如何？

（1）16的原因是构造方法未指定初始容量时，使用其自身默认的初始容量16即1<<4;
（2）2的幂的原因，是因为减少hash碰撞和尽可能的利用数组空间;
（3）如果设置初始容量为12的话，会利用tableSizeFor对12先进行-1，再进行右移1,2,4,8,16，最后+1,得到基于12转化后的16。

7、HashMap中两个对象的hashCode相等时put会如何，如何获取get两个键相同hashcode的值？

（1）两个键的hashcode在相等时put：首先得到hash匹配相等，再进行key的equals判定，如果相等则判定是同一个key，进行覆盖;
（2）两个键的hashcode在相等时get：首先得到hash匹配相等，再进行key的equals判定，如果相同则进行返回，不相等继续遍历寻找，
 直到遍历完链表和红黑树，如果仍然未找到则返回null。

8、HashMap和HashTable的区别?

相同点：存储的都是key-value键值对;
不同点：
    （1）HashMap允许key-value均为null,HashTable不允许任何一个为null,否则报空指针;
    （2）HashMap不是线程安全，不同步，HashTable是线程安全的，底层涉及到数据的方法均加了synchronized关键字;
    （3）HashMap继承于AbstractMap类，HashTable继承于Dictionary类;
    （4）HashMap迭代器为Iterator(fail-fast),HashTable迭代器为Enumerator(不是fail-fast),
        多线程遍历 *** 作(put、remove)HashMap会报并发修改异常ConcurrentModificationException。
    （5）HashMap默认容量值16，扩容是翻倍扩容，HashTable默认容量大小是11(构造方法中写死),扩容是翻倍+1;
    （6）HashMap的hash算法为对key的hashcode进行右移16位，然后异或;hashTable的hash算法直接使用key的hashcode作为hash值。

9、jdk1.7中HashMap有啥缺点(红黑树作用)?

 缺点：jdk1.7中hashMap结构为entry数组+链表，当hash冲突比较大时，会造成链表过长，导致put和get遍历比较耗费性能即O(n);
 红黑树作用：jdk1.8对HashMap进行改进，针对链表过长采取红黑树转化，将O(n)变为O(logN),提高了查询效率，底层存储结构为Node数组+链表+红黑树。