JDK源码学习 —— 集合框架Map中的核心实现类:HashMap

2020-10-23   30 次阅读


HashMap 无疑是 Java 中使用最多的数据结构之一,同时也是面试中的热点问题。虽然常用,但是其中包含的知识挺复杂的,之前零碎的学习过,本次就通过比对 1.71.8 的源码,来系统详细的学习 HashMap

JDK 1.7 中使用的是 **数组+链表**作为底层数据结构。

JDK 1.8 中使用 数组+链表+红黑树作为底层数据结构。当链表长度大于等于8时,链表转化为红黑树,当红黑树的大小 小于等于6时,红黑树转化为链表

1、类注释

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

HashMap 基本上与 HashTable 的特性相同:

  • 允许 null valuenull key
  • 实现了 Map 接口的所有操作

不同点是 HashMap 是非线程安全的,并且 允许 nulls

HashMap 不保证元素的顺序,并且不保证顺序随着时间的推移恒定 ---> 也就是每次遍历可能获取元素的顺序都不同。

【quest:这里之前说 HashTable 已经允许 null 了,这里又说 HashMap 与 HashTable 的不同点是允许 nulls, 这里的 nulls 和之前的 null 不同吗?】

①:This implementation provides constant-time performance for the basic operations (get and put), assuming(假设) the hash function disperses(分散) the elements properly(适当地) among the buckets. ②:Iteration over collection views requires time proportional(成比例地) to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). ③:Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

这段注释感觉挺有东西的:

  • 首先说 HashMapgetput 操作是一个常数操作,常数操作是非常快的,但是前提哈希函数将元素正确地分散在桶(bucket)中
  • 在集合视图上迭代元素需要的时间与 HashMap 的容量(buckets 的数量) 以及大小 (键值映射数) 成正比。
  • 所以有两点很重要 :
    • 1、 不要将初始容量设置的太大
    • 2、 不要将 load facotor 负载因子设置的太小

因为上面两点都会影响容量与桶的比例,这点非常重要。

①:An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.②: The load factor is a measure(度量) of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds(超过) the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

这段的信息量也很大:

  • HashMap 具有两个影响性能的参数:初始容量(initial capacity) & 负载因子 (load factor)
    • 容量:hash tablebucket 桶的数量
    • 初始容量: 创建哈希表时的容量
  • 负载因子:作为 hashtable 自动扩容之前的最大负载量。
  • 当哈希表中的元素数量大于 负载因子 load factor * 当前容量 capacity 的积 时,哈希表会产生 rehash 操作,(也就是重建内部数据结构。) ,因此哈希表的存储桶数约为两倍。【quest:这里的约为两倍指的是发生 rehash 时的 bucket 数量吗? 需要两倍的 bucket 来支持内部数据的重建,还是平时的 bucket 就是两倍?】

①:As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs.②: Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

通常来说,默认的负载因子 0.75 在时间和空间方面提供了很好的平衡:

  • 如果将负载因子调大,会减少存储空间的开销,但是会增加查找操作的时间成本。(查找开销会影响 HashMap 中的大多数操作,比如 getput。)

在设置 初始容量时,应该考虑到 Map 中保存的实体数量以及负载因子的大小,来最大程度地减少 rehash 操作的次数。

如果 初始容量 大于 Map 中实际存储的原始数量除以负载因子,则不会发生任何 rehash 操作。

①:If many mappings are to be stored in a HashMap instance, creating it with a sufficiently(足够地) large capacity will allow the mappings to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table. ②:Note that using many keys with the same hashCode() is a sure way to slow down performance of any hash table. To ameliorate(改善) impact, when keys are Comparable, this class may use comparison order among keys to help break ties.

:如果 HashMap 中要存储很多映射实例,则创建时给一个足够大的初始容量比让 HashMap 发生多次扩容与 rehash 操作要更加高效。

:请注意,如果多个 keyhashCode 值相同,则一定会降低 hash table 的性能,为了改善这种状态,当键为 Comparable 的类时,可以使用键之间的比较顺序来打破多个键对应的 hashCode 相同的问题。【quest:这里给出了 hash 碰撞的解决方法,但是说实话我没看懂,因为没有建立起与实际代码的联系】

Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely(仅仅) changing the value associated with a key that an instance already contains is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:
Map m = Collections.synchronizedMap(new HashMap(...));

HashMap非线程安全Map 实现。如果在多线程环境下使用该类,并且有至少一个线程会修改 HashMap 的内容,则必须使用 额外的同步手段(修改 HashMap 的结构包括了 添加或删除一个或多个 mapping 映射,如果 仅仅是更改 key 关联的 value 值 并不算是修改 HashMap 的结构

常见的同步手段是将 HashMap 封装在类内部,然后使用同步的方式使用,如果没有已经封装了 HashMap 的类,则使用 Collections.synchronizedMap(new HashMap(...)); 工厂方法来构建一个线程安全的 Map 集合。

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
This class is a member of the Java Collections Framework.

这段是关于 Map 的迭代器 iteratorfail-fast 机制的描述,与之前的 Collection 类似:

  • 如果在创建迭代器之后的任何时间对 Map 的结构进行修改,除了使用 迭代器自己的 remove 方法之外,都会抛出 并发修改异常 ConcurrentModificationException
  • fail -fast 行为无法得到严格的保证,它只是检测错误,不应该依赖这个机制来保证数据的正确性。

类注释关键点总结:

  • 继承了 Map 接口的所有操作,并且允许 null 值。( permits null values and the null key.)
  • HashMap 大致等同HashTable,除了 HashMap 允许 null 值,以及 HashMap 是非线程安全的
  • HashMap 无法保证遍历的顺序每次都是一样的。
  • HashMapgetput 操作的时间复杂度是 常数
  • 迭代性能HashMap实例的容量(存储桶的数量)以及其大小(key-value 映射的数量)正比,所以不要将初始容量设置的过高(或者将 负载因子设置的过低 )这会影响迭代性能,这一点非常重要。
  • 影响 HashMap 性能的两个因素:初始容量(initial capacit) 和 **负载因子(load factor) **。capacity 代表着 hashtable 中有多少个桶,initial capacit 代表着当 HashMap 创建时 桶的数量。 load factor 则衡量着HashTable 的容量在自动增长之前允许装满多少个桶 **how full the fash table is allowed to get before its capacity is automatically increased) **
  • HashMap 中存储的条目数量(entries)超过了 (负载因子 * 当前最大容量)时,Hashtable 会进行 re-hashed 动作,也就是**重新散列存储的对象,重建内部数据结构,所以 HashMap 大约是 桶 的数量的两倍**。
  • load factor 的默认值 0.75 是均衡了 时间和空间损耗 算出来的值。将影响因子调整为比0.75更大的值,会减少空间上的损耗(扩容减少,数组大小增长速度变慢),但是会增加查询需要的时间(hash冲突增加,链表变长),这个时间反应在大多数 HashMap 的操作上,比如 getput
  • 如果初始容量大于最大存储条目 / 负载系数 (the maximum number of entries divied by the load factor)】,那么永远不会发生 rehash 动作。
  • 如果提前可以预知要存储很大数量的对象,则建议提前设置 HashMap 的初始容量,否则不断的扩容rehash是很消耗性能的操作。
  • 由于 HashMap非线程安全 的类,所以在使用时需要在客户端进行同步,确保不会有多个线程同时修改HashMap 容器。
  • HashMap 采用了 fail-fast 机制,当创建迭代器之后任何没有通过迭代器对容器进行修改的操作都会抛出 ConcurrentModificationException

存储结构:

:HashMap 中使用桶来存放数据,这个桶在类中对应的是 Node<K,V>[] table 是一个 Node 数组。

链表 : 数组中保存的元素 Node<K,V>Node 是一个典型的 单链表结构 ,源码分析在下面。

图中左边竖着的是 HashMap 的数组结构,数组的元素可能是**单个 Node,也可能是多个Node 组成的 链表 ,也可能是红黑树结构**。

下面这张图是 HashMap 的内部结构,它可以看作是**数组(Node[] table)链表结合组成的复合结构数组被分为一个个桶(bucket),通过 哈希值 决定了键值对 在这个数组的寻址**。哈希值相同的键值对,以链表的形式存储

构造函数:

// 指定初始容量和负载因子的 HashMap
public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
}

// 构造指定容量的 HashMap
public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 按照 Map 接口规定,必须有的构造函数之一 创建一个默认大小、默认负载因子的 HashMap
public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 按照 Map 接口规定,必须有的构造函数之一
public HashMap(Map<? extends K, ? extends V> m) {
  this.loadFactor = DEFAULT_LOAD_FACTOR;
  putMapEntries(m, false); // ①
}


// ① 实现 Map 接种中的 putAll 方法
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
  int s = m.size();
  if (s > 0) {
    if (table == null) { // pre-size
      float ft = ((float)s / loadFactor) + 1.0F;
      int t = ((ft < (float)MAXIMUM_CAPACITY) ?
               (int)ft : MAXIMUM_CAPACITY);
      if (t > threshold)
        threshold = tableSizeFor(t);
    }
    else if (s > threshold)
      resize();
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
      K key = e.getKey();
      V value = e.getValue();
      putVal(hash(key), key, value, false, evict);
    }
  }
}


类常量字段:

// 默认初始容量, 2的4次方,16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大容量,如果两个构造函数都使用参数隐式指定了更高的值,则使用该容量。 最大容量是 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子 0.75 ,可以较好地兼顾 Map 的时间与空间消耗
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 使用树而不是链表的阈值,该值必须大于2,至少应为8
static final int TREEIFY_THRESHOLD = 8;

// 将树转回链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;

// 最小树化容量阈值
static final int MIN_TREEIFY_CAPACITY = 64;





类字段 Fields:

// HashMap 中的桶,用来保存 Node 对象的数组,大小始终是2的幂
transient Node<K,V>[] table;

// entrySet 的缓存字段
transient Set<Map.Entry<K,V>> entrySet;

// HashMap 的实际保存的元素数量
transient int size;

// 计数器,与并发修改异常相关
transient int modCount;

// 当桶的数量使用到多少时进行扩容, capacity * loadFactor
int threshold;

内部类

  • Node
  • TreeNode
// 用来保存 HashMap 中映射条目的实际数据结构,单链表节点
static class Node<K,V> implements Map.Entry<K,V> {
  // key 被 hashCode 函数计算后的 哈希值
  final int hash;
  final K key;
  V value;
  Node<K,V> next;

  Node(int hash, K key, V value, Node<K,V> next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
  }

  public final K getKey()        { return key; }
  public final V getValue()      { return value; }
  public final String toString() { return key + "=" + value; }

  public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
  }

  public final V setValue(V newValue) {
    V oldValue = value;
    value = newValue;
    return oldValue;
  }

  public final boolean equals(Object o) {
    if (o == this)
      return true;
    if (o instanceof Map.Entry) {
      Map.Entry<?,?> e = (Map.Entry<?,?>)o;
      if (Objects.equals(key, e.getKey()) &&
          Objects.equals(value, e.getValue()))
        return true;
    }
    return false;
  }
}

TreeNode 源码过长,是树化后的节点类。下面是精简后的代码:

// 位于HashMap中
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}

// 位于LinkedHashMap中,典型的双向链表节点
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}


核心方法

1、添加元素

流程图:

// ①:使用hash函数计算 key 的值
// ②:调用 putVal 函数将 kv 映射存入 HashMap 中
public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}


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

// onlyIfAbsent ---> 如果为 ture,则不改变已有的 value
// evict ---> 如果为 false ,则代表 table 处于 creation mode
// 这里的传入值 onlyIfAbsent 是 false,所以会修改 key 对应的 value, evict 是 true,所以代表 table 不处于 creation mode
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  // n:数组长度 , i: 数组索引, p 是 i 下标位置处的 Node值
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // 这里判断当前的桶是否为空,且长度为0,如果是的话进行初始化
  if ((tab = table) == null || (n = tab.length) == 0)
    // 调用 resize 初始化
    n = (tab = resize()).length;
  // n -1 & hash ---> 意义是为了计算这个元素在哪个桶中
  // 如果 tab[n - 1 & hash] 处的桶还没有元素,则创建一个新的 Node 放入table 对应索引处,添加流程结束
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  // 否则代表如果当前索引位置已经存在 Node 这种情况就是哈希碰撞
  else {
    Node<K,V> e; K k;
    // 如果桶中的第一个元素 p 的 key 与插入的 key 相同,则将 p 元素保存到方法变量 Node e 中,方便后续使用
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    // 如果 p 属于一个树节点,则进入红黑树的 putTreeVal 插入元素流程
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    // 否则说明这个桶是一个链表,遍历这个链表
    else {
      // binCount 用于存储链表中元素的个数
      for (int binCount = 0; ; ++binCount) {
        // 遍历到链表的尾部,如果没有任何元素与当前插入的元素 key 相同,则在添加一个新节点
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          // 如果链表元素数量 大于等于 树化阈值 -1 ,则触发链表树化,这里 - 1 是因为 第一个元素没有加到 binCount 中
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        // 如果待插入的元素的 key 在链表中找到了对应的元素,则循环结束
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        // 覆盖对应 key 处的 value 值
        p = e;
      }
    }
    // 如果找到了 key 对应的元素
    if (e != null) { // existing mapping for key
      // 记录一下 key 原来对应的 value
      V oldValue = e.value;
      // 根据 onlyIfAbsent 以及 oldValue 是否为 null 判断是否需要替换 value 
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      // 节点被访问后的后置处理, LinkedHashMap 中被用到
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  // 元素数量加1,判断是否需要触发扩容操作
  if (++size > threshold)
    resize();
  // 节点插入之后的后置处理 LinkedHashMap 中被用到
  afterNodeInsertion(evict);
  // 没有找到对应的元素,返回 null 
  return null;
}

// ------------- 扩容/初始化 方法 ------------- //


// 初始化或扩容方法,如果当前 table 为空,则根据字段阈值中保持的初始容量对目标进行分配,否则,因为容量是2的幂,索引每个 bin 中的元素必须保持相同的索引,活在在新的 table 中以2的幂偏移
final Node<K,V>[] resize() {
 	// 定义一个局部变量,保存之前的桶
  Node<K,V>[] oldTab = table;
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  int oldThr = threshold;
  int newCap, newThr = 0;
  if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold
  }
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
  else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  @SuppressWarnings({"rawtypes","unchecked"})
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          do {
            next = e.next;
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

最是人间留不住,曾是惊鸿照影来。