求知若渴，虚心如愚。

JDK源码分析之HashMap

发表于 更新于 分类于

源码C:\ProgramFiles\Java\jdk1.8.0_181\jre\lib\rt.jar!\java\util\HashMap.java

简介

本类实现了java.util.Map接口并允许空值和空键，HashMap的实例具有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中存储桶的数量，初始容量只是创建哈希表时的容量。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表将被自动扩容（内部数据结构将被重建）。

通常，默认负载因子（.75）在时间和空间成本之间提供了一个很好的权衡。较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put）。如果将大量的键值对存储在HashMap实例中，则应该创建相匹配的容量，以避免多次触发自动扩容影响程序性能。

本类是线程不安全的。如果多个线程同时访问，并且至少有一个线程在结构上修改，则必须在外部进行同步。如果需要在多线程环境使用本类，可以用Map m = Collections.synchronizedMap(new HashMap(...));进行包装。

类图结构

  • Node：实现了Map接口中的Entry子接口，表示的是一个键值对。
    • TreeNode：继承Node类，变成了红黑树结构的Node。
  • HashIterator：内部迭代器实现类
    • EntryIterator：继承HashIterator并实现了Iterator接口，方便Map.Entry对象可以被迭代。
    • KeyIterator：继承HashIterator并实现了Iterator接口，方便键可以被迭代。
    • ValueIterator：继承HashIterator并实现了Iterator接口，方便值可以被迭代。
  • EntrySet：实现Collection类，用来存储Map.Entry对象。
  • KeySet：实现Collection类，用来存储键集合。
  • Values：实现Collection类，用来存储值集合。
  • HashMapSpliterator：内部Spliterator接口实现类
    • EntrySpliterator：
    • KeySpliterator：
    • ValueSpliterator：

实现思路

初始化

  • 如果不指定初始桶容量则默认为16，最大不超过1,073,741,824，根据初始桶容量调整大小的阈值threshold，其结果除1外始终是2的倍数（1/2/4/8/16/32/64/…），当初始容量超过16时其结果将是它的2倍，如果超过了16的2倍则结果为32，以此类推。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= 1,073,741,824) ? 1,073,741,824 : n + 1;
    }
  • 如果不指定扩容负载因子则默认为0.75，即达到75%容量时就进行扩容。
  • 初始化时仅设置参数上面两个参数，并不进行桶初始化，这点和hashtable有很大不同。

添加键值对

  • 计算键（key）的hash值
  • 如果当前map的hash表为空则进行真正初始化，所以它采用了延迟初始化的策略，当你设置值的时候才检查是否进行初始化。
    • 如果当前map为空，即首次初始化（复用扩容逻辑）：
      • 在初始化对象时计算的threshold值如果大于0，则新容量等于threshold，扩容阈值等于新容量*扩容负载因子，其结果如果大于1,073,741,824，那么扩容阈值为‭2,147,483,647‬。
      • 如果threshold值等于0，则新容量为16，扩容阈值为12（16*0.75）。
      • 根据上步计算的新容量初始化Node数组，然后将新数组赋值给hash表（原来的hash表有提前记录下来）。
  • 判断当前设置的键是否已经存在，根据key的hash值来找到对应的数组下标。
    • 如果这个下标对应的节点是NULL，则说明当前新加的key肯定不存在，所以直接添加新节点tab[i] = newNode(hash, key, value, null);即可。
    • 但如果上面计算出来数据下标有值，则说明可能和当前新加的key相同，那么就需要2次判断。
      • 新加的key的hash值与key本身都与找到的下标节点相同，那说明本次要添加的键值对已经存在了。
      • 如果上面判断为false，则检查对应下标节点是否为TreeNode，如果是就调用到TreeNode.putTreeVal()中去。
      • 考虑到相同Hash冲突之后，节点会添加到原节点前面，所以此时要判断当前节点的所有子节点，也就是判断它是否存在于链表中的某个节点上。
        • 如果当前节点没有子节点，那也就是没有匹配上，此时就可以直接添加新节点了。检查节点数量是否大于等于TREEIFY_THRESHOLD（8），如果满足这个条件则将链表结构转换为红黑树结构。
        • 如果当前节点有子节点，则遍历所有子节点，来比较是否与当前新加的键值对相同。
      • 通过上面一系列的检查之后发现新加的键值对已经存在了，则用新值覆盖旧值，并立即返回旧值。
  • 统计修改次数，判断是否需要扩容（即size是否大于扩容阈值threshold），并立即返回NULL。

在红黑树上添加键值对

通过上面的分析可以知道，当Node数组中某个下标所对应的节点链表长度大于等于8（TREEIFY_THRESHOLD）时，链表结构会转换为红黑树结构，添加的思路和链表是类似的，不同存在对数据结构的操作，然后在添加了新节点之后要按照红黑树的规则进行树的重新平衡，这个过程和红黑树的实现算法相关，故不在本处进行介绍。

  • 移除键值对

根据键获取对应值

总结