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)时,链表结构会转换为红黑树结构,添加的思路和链表是类似的,不同存在对数据结构的操作,然后在添加了新节点之后要按照红黑树的规则进行树的重新平衡,这个过程和红黑树的实现算法相关,故不在本处进行介绍。

  • 移除键值对

根据键获取对应值

总结