Java之HashMap的底层原理

一、 面试知识点

1. 随着18年以来现在互联网对java面试题也是越问越深，其中hashmap更是java必问问题，那么我们今天就来总结一下hashmap 的底层原理和面试常考知识点。

2. HashMap 是一种存储高校但是不保证有序的容器，它的数据结构为"数组+链表/红黑树"的结构（当链表长度到8以后数据结构改为红黑树）

   
   image.png

• 底层实现了Map<k,v> 的接口并实现了浅拷贝和序列化，HashMap 默认初始值大小为16 ，初始值大小必须为2的幂次，如果用户输入的不是2的幂，那么系统自动更新为输入值附近的2的幂次，最大大小为2的30次幂。HashMap的阈值默认为 0.75，当存储节点超过该值，对map进行扩容。
  每次扩容为原来的1倍。

  
  image.png

• HashMap 提供了四种构造方法，分别是默认构造方法；可以指定初始容量构造方法；可以指定初始值和阈值的构造方法；以及基于一个Map的构造方法。一般常用的都是给定初始容量大小的构造方法

  
  image.png
• 在一次put(添加操作)的时候，HashMap 会先进行初始化，如果没有先进行初始化操作，初始化过程会取比用户指定容量大的最近2的幂次数作为数组的初始容量，如果设置了扩容的阈值也一并更新。初始化完成以后继续put 方法
  1. 先判断有没有初始化
  2. 在判断传入的key是否为空 就存储在table(0)位置
  3. key不为空就对key进行hash，hash的结果在 & 上数组的长度就得到了位置。
  4. 如果存储位置为空就创建新节点，不为空就说存在hash冲突了。
  5. 解决冲突HashMap会遍历整个链表，如果有相同的value值就更新，否则创建节点添加到链表头。
  6. 添加还要判断存储节点是否达到阈值，达到阈值要进行扩容。
  7. 扩容两倍，扩容的时候使用Arrays.copy() 进行扩容。
  8. 扩容过后新插入的节点也要重新进行hash 一遍才能插入。

// jdk8 源码
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 取值的操作和添加差不多。
  1. 先判断是否为空，为空就取table(0)去找
  2. 不为空也低先hash & 数组长度得到下标位置
  3. 在遍历找到相同的找到相应的值。
• 以上这些是一些常用的知识点，但是如果你只是知道以上这些还是不够的，一般面试官还会问你HashMap 线程安全码？ 当然大家都知道是不安全的，但是要是问你怎么解决呢？ 如果你要是回答加锁或者回答使用HashTable 基本上就挂了。HashMao是一个线程不安全的容器，在并发操作会出现丢失更新问题，严重会导致cpu宕机的，一般报错为java.util.ConcurrentModificationException.那我们该怎么解决呢？
  1. 使用java类库提供的collections工具包下的Collections.synchronizedMap(new HashMap()),返回一个线程安全的Map
  2. 使用并发包(java.util.concurrent)下的ConcurrentHashMap,ConcurrentHashMap采用分段式锁机制实现线程安全。
• 能不能手写一个HashMap 线程不安全的案例

private static void hashMapNotSafe() {
     // 线程不安全版本
       Map<String, String> hashMap = new HashMap<>();
       //并发版本的hashMap。
  // Map<String, String> hashMap = new ConcurrentHashMap<>() ;
       for (int i = 0; i < 30; i++) {
           new Thread(()-> {
               hashMap.put(Thread.currentThread().getName(), UUID.randomUUID().toString().substring(0, 8));
               System.out.println(hashMap);
           }, String.valueOf(i)).start();
       }
   }

• java8和java7的区别
  1. Hash1.7 和1.8 最大的不同在于1.8 采用了“数组+链表+红黑树”的数据结构，在链表长度超过8 时，把链表转化成红黑树来解决HashMap 因链表变长而查询变慢的问题；
  2. 1.7 的底层节点为Entry，1.8 为node ，但是本质一样，都是Map.Entry 的实现
  3. 还有就是在存取数据时添加了关于树结构的遍历更新与添加操作，并采用了尾插法来避免环形链表的产生

二、 考点分析

HashMap 作为最基础的容器，常用来考1.7和1.8的区别，除了这个要想在面试中脱颖而出还要对HashMap的前因后果要多了解。

1. 考点一：为什么初始容量为2的幂等次？为什么负载因子为0.75f？为什么做那么多扰动处理。

• 这些问题都要围绕一个点回答：减少hash 冲突。
• 容量必须为2的幂次是为了增加取值的可能性。
  • 2的n次幂转换为二进制为1后面n个0，在计算下标的是否为hash&(length-1),也就是&(n-1)个1.所有二进制为1的好处？
    • 0/1 & 1 都为它本身
    • 0/1 & 0 都为 0
  • 可以看出&1保证了取值的平均。如果某一位为0 ，比如最后一位，那么它&出来下标就一定是个偶数，减少了HashMap 数组一半的取值，大大增加了冲突的可能。
• 负载因子为0.75f是空间与时间的均衡。
  • 如果负载因子小，意味着阈值变小。比如容量为10 的HashMap，负载因子为0.5f，那么存储5个就会扩容到20，出现哈希冲突的可能性变小，但是空间利用率不高。适用于有足够内存并要求查询效率的场景。
  • 相反如果阈值为1 ，那么容量为10，就必须存储10个元素才进行扩容，出现冲突的概率变大，极端情况下可能会从O(1)退化到O(n)。适用于内存敏感但不要求要求查询效率的场景
• hash()的意义在于使hash结果不同hash 算法的好坏直接印象hash结构的效率。1.8 之所以把9 次扰动降到2 次，是出于计算效率的考虑。

2. 考点二：& 字符串和%字符串 虽然效果一样，但是操作效果更高。
3. 考点三：为什么int String 更适合做key?

• int 和 String 的好处在于hash 出来的值不会改变。如果是一个对象，那么他们可能会因为内部引用的改变而hashCode 值的改变，会导致存储重复的数据或找不到数据的情况。

三、 面试时候由于HashMap 引导出来的其他问题？

• 不仅仅是HashMap 的问题，在面试的时候，面试官会引导出很多其他问题，所以这个地方你在回答问题的时候要设计引导到你熟悉的内容上
• 说说concurrentHashMap 和 HashMap 的区别以及底层的实现？
• 说说HashMap 如何实现有序(LinkHashMap 和TreeMap)以及他们的差别