乐趣区

关于java:后端面经JavaHashMap详解

1. HashMap 的家族定位

接口 java.util.Map 有四个罕用的实现类,如图是它们之间的类继承关系。

上面我将一一介绍其性能特点。

  • HashMap

    • 最罕用的 Map 实现类,通过应用 Hash 表构造,进步查找速度;
    • 应用键值对作为存储节点,只容许一个 key 值为null,容许多个 value 值为null
    • 线程不平安,对于线程平安有要求的程序,能够思考应用:sychronizedMap 或者 ConcurrentHashMap;
  • HashTable

    • 同样应用 Hash 表构造,进步查找效率;
    • 线程平安,然而平安层级低于 ConcurrentHashMap,不罕用。
  • LinkedHashMap

    • 继承自 HashMap,应用 Hash 表构造,进步查找效率;
    • 链表插入 维持插入程序
  • TreeMap

    • sortedMap 接口的实现类,可应用特定的 排序 规定对键值对进行排序;

对四种常见的实现类的性能比拟如下图所示:

2. HashMap 的数据结构

2.1 Hash 表的基本概念

Hash 表是 数据结构和算法 课程中学习到的一种重要的数据结构。次要设计思维是:

  • 应用一个长度为 n 的数组存储相干数据。
  • 应用 hash 函数 实现内容和数组下标的对应,也就是 hash 函数 的函数值为 0~n 之间。

    • hash 函数 雷同的输出参数肯定会产生雷同函数值,不同内容尽量做到函数值扩散。
  • 在 hash 函数值对应的下标写入该内容。
  • 下次查找某元素的时候,先依据 hash 函数 生成下标,而后再随机拜访数组,这样查找效率大大提高了。

相似于一个叫 贾斯汀·费尔兰德·亨利皮特潘 (简单内容)的人,在 酒店前台 (hash 函数)入住酒店的房间编号是1004(hash 函数值 / 数组下标)。须要找他的人,只须要去酒店前台查问他住在1004 房间,间接去 1004 房间找人就能够了,不须要一个一个房间去找。

2.2 Hash 抵触

在下面的流程阐明中,咱们能够发现 Hash 表的实现要害就在于 Hash 函数,一个好的 hash 函数应该保障不同的输出内容尽量扩散其函数值。
当存入的数据过多,hash 函数性能较差的时候,可能会呈现hash 抵触

  • AB 是两个不同的存储内容,然而通过 hash 函数计算,失去的 hash 函数值雷同,因而两个内容存储在数组的同一地位。
  • 例如:贾斯汀·费尔兰德·亨利皮特潘 特朗普·懂王·建国同志 两个人在酒店前台调配到的房间号都是1004,然而房间只有一张床,这时两个人就会发生冲突。

解决抵触次要有两种思路:

  • 凋谢定址法:发生冲突的时候,后到来的元素放弃已被占用的地位,寻找新的插入地位。(再找)
  • 链地址法:发生冲突的时候,后到来的元素在原有地位的根底上,应用链表的形式存储。(排队)

    • HashMap 应用的就是 链地址法

2.3 HashMap 数据结构

  1. 节点 Node
    Node 是 HashMap 的一个根本存储单元,从源码中可见 Node 实现了 Map.Entry 接口,寄存的是键值对。在 JDK1.8 中的源码中,Node 的定义如下所示:

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    // 用来定位数组索引地位
        final K key;
        V value;
        Node<K,V> next;   // 链表的下一个 node
    
        Node(int hash, K key, V value, Node<K,V> next) {...}
        public final K getKey(){ ...}
        public final V getValue() { ...}
        public final String toString() { ...}
        public final int hashCode() { ...}
        public final V setValue(V newValue) {...}
        public final boolean equals(Object o) {...}
    }
  2. JDK1.7 的 HashMap 数据结构
    数组 + 链表

    • 如图所示
    • 应用链地址形式解决 hash 抵触。
  3. JDK1.8 的 HashMap 数据结构
    数组 + 链表 + 红黑树

    • 如图所示

      ![在这里插入图片形容](https://img-blog.csdnimg.cn/e80970c484d9427c8c47885eabbe0229.png#pic_center)
      
    • 对红黑树的学习可参考此博客。
    • 链表和红黑树的转换依据链表长度阈值判断,阈值为 8,即链表长度大于 8 时,由链表转换为红黑树,小于 6 时,由红黑树转换为链表。
    • 红黑树的引入目标:在链表长度较长的状况下,优化查找效率。

3. HashMap 的重要变量

3.1 常量

  • DEFAULT_INITIAL_CAPACITY

    • 默认的数组初始容量,值为2^4=16
    • 如果没有指定初始数组的容量的话,就会应用这个默认值。
  • MAXIMUM_CAPACITY

    • 最大的数组容量,值为2^30
    • 在扩容的时候,如果扩容后的容量大于这个值,就会应用这个值作为新的容量。
    • 之后如果数据再减少,不再进行扩容,而是间接链表存储或者转为红黑树。
  • DEFAULT_LOAD_FACTOR

    • 默认负载因子,值为0.75
    • 在 HashMap 中,扩容的临界值计算公式为:
      临界值(threshold)= 负载因子(loadFactor)* 容量(capacity)
    • 负载因子能够设置为任意值,然而须要留神的是:

      • 负载因子变大,hash 抵触的概率就会变大,查找效率就会升高。【就义工夫】
      • 负载因子过小,会导致数组空间利用率低,节约内存空间。【就义空间】
  • TREEIFY_THRESHOLD

    • 链表转化为红黑树的阈值,值为8
    • 当一个数组节点所带着的链表长度大于 8 时,链表会转化为红黑树。
  • UNTREEIFY_THRESHOLD

    • 红黑树转化为链表的阈值,值为6
    • 当一个数组节点的红黑树节点小于 6 时,红黑树会转化为链表。
  • MIN_TREEIFY_CAPACITY

    • 转换为红黑树的最小容量,值为64
    • 这个变量的意思是,在 HashMap 一直减少新元素的过程中,如果此时数组中的元素个数小于 64,那么就抉择扩容。当数组元素个数大于 64 的时候才会思考树化。

      3.2 变量

  • size

    • HashMap 中存储的键值对个数。
  • modCount

    • 对 HashMap 进行批改的次数记录,每次增删则加一。
  • threshold

    • 扩容的临界值,计算公式为:threshold = loadFactor * capacity。其中 capacity 为数组总长度,通常为了进步阈值,会应用扩容减少 capacity,而对于负载因子 loadFactor,个别不会批改。
  • loadFactor

    • 负载因子,用户可自行设置其值,否则等于默认值0.75

3.3 辨析 size、capacity、threshold

size: 理论存储的键值对个数
capacity: 数组的总长度
threshold: 扩容的临界值
treeify_threshold/untreeify_threahold: 链表和红黑树互相转化的阈值

4. HashMap 重要办法和源码解析

4.1 构造方法

  1. HashMap()
    无参结构,应用默认的初始容量 2^4 和负载因子0.75,结构一个空的 HashMap。

    // 结构一个空的 HashMap,初始容量为 16,负载因子为默认值 0.75
    public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;  // all other fields defaulted}
  2. HashMap(int initialCapacity)
    指定初始容量,应用默认的负载因子0.75

    public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);// 一次性实现容量和负载因子的赋值
    }
    
  3. HashMap(int initialCapacity, float loadFactor)
    指定初始容量和负载因子,结构一个空的 HashMap。

    public HashMap(int initialCapacity, float loadFactor) {
     // 如果初始容量为正数,抛出非负异常
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal initial capacity:" +  initialCapacity);
     // 初始容量大于最大值时 1 <<30,则取最大值
     if (initialCapacity > MAXIMUM_CAPACITY)
         initialCapacity = MAXIMUM_CAPACITY;
     // 负载因子不能小于 0,并且必须是数字,否则抛异样
     if (loadFactor <= 0 || Float.isNaN(loadFactor))
         throw new IllegalArgumentException("Illegal load factor:" + loadFactor);
     // 数值判断非法之后,赋值
     this.loadFactor = loadFactor;
     this.threshold = tableSizeFor(initialCapacity);//tableSizeFor() 办法返回一个值,比 initialCapacity 大的最小 2 的幂。}
  4. HashMap(Map<? extends K, ? extends V> m)
    结构一个 非空 的 HashMap,将 m 中的键值对存入 HashMap 中,默认的负载因子 0.75,应用默认的初始容量2^4

    public HashMap(Map<? extends K, ? extends V> m) {
     this.loadFactor = DEFAULT_LOAD_FACTOR;
     // 将 Map 中的 key-value 赋值到新的 Map 中去
     putMapEntries(m, false);
    }
    

    4.2 resize 办法

    当 HashMap 中数组的使用量超过阈值的时候,就须要进行扩容。JDK1.8 的源码如下所示:

    final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;// 以后 table
     int oldCap = (oldTab == null) ? 0 : oldTab.length;// 以后 table 的大小
     int oldThr = threshold;// 以后 table 的 threshold
     int newCap, newThr = 0;// 新的 table 的大小和阀值临时初始化为 0
    
     // 上面就是开始计算新的 table 的大小和阀值
     // 第一种状况:以后 table 的大小大于 0,则意味着以后的 table 必定是有数据的
     if (oldCap > 0) {//
         if (oldCap >= MAXIMUM_CAPACITY) {// 原始容量大于最大容量,不再扩容,间接返回原始 table
             threshold = Integer.MAX_VALUE;
             return oldTab;
         }
         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)// 翻倍之后不超过最大容量,原始容量小于最大容量,且大于默认容量,那么容量翻倍,阈值也对应翻倍
             newThr = oldThr << 1;
     }
     // 第二种状况:以后的 table 中无数据,然而阀值不为零,阐明初始化的时候指定过容量或者阀值,然而没有被 put 过数据,else if (oldThr > 0) 
         newCap = oldThr;// 此时的阀值就是数组的大小,所以间接把以后的阀值当做新 table 的数组大小即可。threshold = tableSizeFor(t);
     // 第三种状况,这种状况就代表以后的 table 是调用的空参结构来初始化的,所有的数据都是默认值。else {// 初始阈值为 0,示意应用默认值,新的 table 也只有应用默认值即可
         newCap = DEFAULT_INITIAL_CAPACITY;
         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
     }
     // 如果新的阀值是 0,那么就简略计算一遍就行了
     if (newThr == 0) {float ft = (float)newCap * loadFactor;
         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                   (int)ft : Integer.MAX_VALUE);
     }
     threshold = newThr;
    
     // 依据上文中计算的新表容量和阈值,初始化新的 table
     // 这个 newTab 就是新的 table,数组大小就是下面这一堆逻辑所计算出来的
     @SuppressWarnings({"rawtypes","unchecked"})
     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
     table = newTab;
     if (oldTab != null) {
         // 遍历以后 table,解决每个下标处的 bucket,将其解决到新的 table 中去
         for (int j = 0; j < oldCap; ++j) {
             Node<K,V> e;
             if ((e = oldTab[j]) != null) {
                 // 开释以后 table 数组的对象援用(for 循环后,以后 table 数组不再援用任何对象)oldTab[j] = null;
                 // a、只有一个 Node,则间接 rehash 赋值即可
                 if (e.next == null)
                     newTab[e.hash & (newCap - 1)] = e;
                 // b、以后的 bucket 是红黑树,间接进行红黑树的 rehash 即可
                 else if (e instanceof TreeNode)
                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                 // c、以后的 bucket 是链表
                 else { // preserve order
                     Node<K,V> loHead = null, loTail = null;
                     Node<K,V> hiHead = null, hiTail = null;
                     Node<K,V> next;
                     // 遍历链表中的每个 Node,别离判断是否须要进行 rehash 操作
                     // (e.hash & oldCap) == 0 算法是精华,充分运用了上文提到的 table 大小为 2 的幂次方这一劣势,下文会细讲
                     do {
                         next = e.next;
                         // 依据 e.hash & oldCap 算法来判断节点地位是否须要变更
                         // 索引不变
                         if ((e.hash & oldCap) == 0) {if (loTail == null)
                                 loHead = e;
                             else
                                 loTail.next = e;
                             loTail = e;
                         }
                         // 原索引 + oldCap
                         else {if (hiTail == null)
                                 hiHead = e;
                             else
                                 hiTail.next = e;
                             hiTail = e;
                         }
                     } while ((e = next) != null);
                     // 原 bucket 地位的尾指针不为空(即还有 node)
                     if (loTail != null) {
                         // 链表开端必须置为 null
                         loTail.next = null;
                         newTab[j] = loHead;
                     }
                     if (hiTail != null) {
                         // 链表开端必须置为 null
                         hiTail.next = null;
                         newTab[j + oldCap] = hiHead;
                     }
                 }
             }
         }
     }
     return newTab;
    }
  5. 为什么要 * 2 扩容?或者说,为什么 HashMap 的数组大小为 2 的幂
    在实践学习中,Hash 表的大小最好是素数,因为素数可能无效升高 hash 碰撞。然而 HashMap 并没有采纳这种做法。
    在下面的源码中,咱们能够看到,HashMap 在扩容的时候,数组的大小都是原来的两倍,这是因为在计算索引的时候,咱们应用的是 size-1 的 n 个全 1 二进制串和 hash 值进行与运算,这样能够保障计算出来的索引值肯定在 0~size-1 之间,不会越界。如图所示:

当 HashMap 值为 2 的幂的时候,size-1为全 1 二进制字符串,且扩容之后,本来有抵触的两个元素会找到各自的新索引地位。如图所示:

在代码中,这个步骤被进一步简化。如代码片段所示:

if ((e.hash & oldCap) == 0) {if (loTail == null)
      loHead = e;
  else
      loTail.next = e;
  loTail = e;
}
// 原索引 + oldCap
else {if (hiTail == null)
      hiHead = e;
  else
      hiTail.next = e;
  hiTail = e;
}

因为 hash 值是一个整数,所以 hash & oldCap 的后果要么是 0,要么是 oldCap。所以,hashMap 的扩容,实际上是将原来的数组分成两局部,一部分的索引不变,一部分的索引变为原索引 +oldCap。这样就保障了原来的两个元素,扩容之后,肯定不会在同一个索引地位上。具体解释如图所示:

4.3 hash 办法

也就是之前在实践局部所说的 hash 函数局部,将关键字 key 的值转换为惟一 hash 值,JDK1.8 源码如下:

static final int hash(Object key) {
    int h;
    // 高 16 位与低 16 位进行异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hashCode()函数通常和 equals() 函数进行比拟,hashCode()函数是依据对象的内存地址生成一个特定的数,因而,hashCode 值雷同的对象不肯定雷同,hashCode 值不同的对象肯定不雷同。
个别判断两个对象是否相等,先应用 hashCode() 函数判断内存地址,如果 hashCode() 函数值雷同,再应用 equals() 函数判断内存中的内容,如果 hashCode() 函数值不同,就不须要再应用 equals() 函数判断了。

这里 h 先设置成 key 值的 hashCode,而后右移 16 位,再和原来的 h 进行异或运算,这样做的目标是为了缩小 hash 碰撞,进步查找效率。

之后如何从 hash 值映射到数组下标,在 JDK1.7 的源码如下所示:

static int indexFor(int h, int length) {return h & (length-1);
}

这里也解释了为什么 HashMap 的数组大小为 2 的幂,因为这样能够保障 length-1 为全 1 的二进制串,与操作之后计算出来的索引值肯定在 0~size-1 之间,不会越界,具体操作如图所示:

4.4 put 办法

put 办法次要是在 HashMap 中存储键值对,JDK1.8 源码如下所示:

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);// 重点在于 putVal 办法
}

// 参数 onlyIfAbsent, 针对曾经存在的 value,值为 true 示意不批改;否则示意会替换本来的 value 值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
    // ① 如果以后 table 为空则进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 计算失去索引 i,算法在上文有提到,而后查看索引处是否有数据
    // ② 如果没有数据,则新建一个新的 Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 索引处有数据
    else {
        Node<K,V> e; K k;
        // ③ 索引处的第一个 Node 的  key 和参数 key 是统一的,所以间接批改 value 值即可(批改的动作放在上面)if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // ④ 索引处的 bucket 是红黑树,依照红黑树的逻辑进行插入或批改
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // ⑤ 索引处的 bucket 是链表
        else {
            // 遍历链表下面的所有 Node
            for (int binCount = 0; ; ++binCount) {
                // 索引处的 Node 为尾链
                if ((e = p.next) == null) {
                    // 间接新建一个 Node 插在尾链处
                    p.next = newNode(hash, key, value, null);
                    // 判断是否须要转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 链表转换为红黑树,此办法在上文中也有介绍
                        treeifyBin(tab, hash);
                    break;
                }
                // 以后 Node 的 key 值和参数 key 是统一的,即间接批改 value 值即可(批改的动作放在上面)if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 找到了雷同 key 的 Node,所以进行批改 vlaue 值即可
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 批改 value 值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 批改操作,间接 return 完结掉代码逻辑
            return oldValue;
        }
    }
    // 记录构造发生变化的次数
    ++modCount;
    // ⑥ 判断是否须要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    // 新增的 Node,返回 null
    return null;
}

源代码所形象进去的具体的 put 流程可如下图所示:

在 JDK1.7 中,链表插入应用头插法,而在 JDK1.8 中,链表插入应用尾插法,

  • JDK1.7 应用头插法的起因:思考到热点数据,前面插入的元素更有可能被最近应用,因而应用头插法。
  • 头插法会使链表上 Node 的程序调转,而尾插法令不会,另外,头插法也会造成环形链死循环等问题,
  • 参考文献

  • 知乎专栏 -HashMap 原理详解,看不懂算我输(附面试题)
  • 掘金社区 - 详解 HashMap 数据结构
  • 美团技术团队 -Java 8 系列之重新认识 HashMap
退出移动版