HashMap 文档通读及源码分析

原创
2020/02/23 17:00
阅读数 49

文档通读及问题

没有贴英文原文,大家可以照着源码中的注释看,这里翻译的是源码上的注释,并且贴出了我自己读的时候心里的问题,后面会带着问题进行源码分析.

Hash Map 简介

Hash Table 基于 Map 接口实现. 它的实现提供了所有可选的 map 操作,并且允许 key 和 value 为 null. (HashMap 和 HashTable 大体相同,只不过 HashMap 不是线程安全的(unsynchronized),并且允许空值健) 此类不保证 map 的顺序;而且尤其要注意的是,它也不能保证顺序不会变化

Q: 顺序是如何变化的?


Hash Map 性能

在 hash 方法将元素正常散列在哈希桶里的情况下,此实现对于 get 和 put 这类基本操作的时间复杂度是常量级的.
集合视图上的迭代要求【时间】与【HashMap实例的“容量”(bucket的数量)和大小(键值映射的数量)之和】成正比. 此外,如果对性能有一定要求的话,千万不要将初始容量设置的太高(或是将加载因子设置得太低).

Q: 为何是get 和 put 是常量级的,如何保证? 初始容量和加载因子是如何影响性能的?


对于 HashMap 来说,有两个参数会影响性能:初始容量(initial capacity) 和 负载因子(load factor).
capacity 是 hash table的桶数量,而初始容量就是 hash table 被创建时的容量大小. 负载因子 是用来衡量 hash table 被自动扩容前能被填充到什么程度的一个指标,也是就:填了多少数据就需要自动扩容了. 当 hash table的 entries 超过这个负载因子和当前容量时,hash table 会被重新 hash (意思是:内部的数据组成会被重新组建),以让 hash table 能扩容两倍左右.

Q: entries, capacity, load factor的关系?

一般来说,默认的负载因子(0.75)是一个在时间和空间消耗上都比较平衡的一个值. 更高的值会降低空间消耗但是会增加查询成本(对于 HashMap 类中的大部分方法,包括 get 和 put). 当设置初始容量时,要考虑map 中的 entries 数量和负载因子,以尽量减少重新 hash? 计算操作. 如果初始容量 > entries 最大值 / 负载因子,就不会进行重新 hash 计算.

Q: 又一次提到加载因子 load factor?
Q: 什么是 rehash 操作,什么情况下会触发?

如果需要存储的数据量较大,创建时设置一个足够大的 capacity,数据存储时会比需要扩容时重新 hash 计算更高效. 要注意使用多个 hashCode 相同的 key 是绝对会降低hash table的效率的. 如果 key 实现了 Comparable 接口的话,这个类可能会使用key 之间的comparison 顺序来提升效率.

Q: hashCode 相同时如何处理的? 实现了 comparable 会如何操作,未实现又会怎样?


Hash Map 线程不安全

注意这个实现是非同步的(not synchronized). 如果有多个线程并发地获取一个 hash map, 并且至少其中一个线程在结构上改变了这个 map,它必须在外部同步. (结构修改操作就是任何新增或者删除一个或多个数据,如果只是修改和 实例已包含的 key 相关的值不能叫做 结构上的修改.) 一般是通过同步一些自然封装map的对象来实现.

Q:最后一句不懂什么意思,This is typically accomplished by synchronizing on some object that naturally encapsulates the map.

如果不存在这样的对象,map 必须通过 Collections.synchronizedMap 方法包装(wrapped). 最好在创建时就这样操作,以免不慎非同步获取 map.

示例:

Map m = Collections.synchronizedMap(new HashMap(...));

Fail-fast 机制解释

对于所有的集合类来说,迭代器对于这个类的 集合视图方法都是 fail-fast 的:如果在迭代器创建后 map 被结构化修改,除了迭代器自身的 remove 操作外,迭代器都会抛出 ConcurrentModificationException 异常。 除此之外,并发修改时,迭代器也不会在未来不确定的时候冒险地做任何不确定的操作,而是会迅速原封不动地失败. (PS译者注:这里原文描述是 quickly and cleanly,我猜是说不会有任何操作发生,这个 map 原封不动的返回的意思)

注意 fail-fast 机制并不可靠,一般来说,非同步的并发操作发生时,你是无法得到任何硬性保证的.
Fail-fast 迭代器会尽量去抛出 ConcurrentModificationException.
所以,写程序时依赖于这个异常来保证正确性是不可取的:fail-fast 机制只应该用来检查 bug.

这个类是 Java Collections Framework 中的成员

Java 集合类接口继承关系和实现

源码通读

接下来开始看代码

public class HashMap<K,V> extends AbstractMap<K,V>  
    implements Map<K,V>, Cloneable, Serializable

结合上图看,HashMap 继承了 AbstractMap,并实现了 Map 接口,同时还实现了 CloneableSerializable 接口,这两个接口不在本文讨论范围内,是关于 Java 持久化和引用相关的知识。

常量

serialVersionUID
private static final long serialVersionUID = 362498820763181265L;

方法里面定义了一个 serialVersionUID 的静态变量,这个变量是为 Serializable 接口准备,进行序列化时使用的。

默认初始容量
/**
 * The default initial capacity - MUST be a power of two. 
 */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

默认初始容量,这里定义的是 16,必须是2次幂.

最大容量
/**
 * The maximum capacity, used if a higher value is implicitly specified 
 * by either of the constructors with arguments. 
 * MUST be a power of two <= 1<<30. 
 */
 static final int MAXIMUM_CAPACITY = 1 << 30;

最大容量,如果在构造函数中隐式设置了比默认容量更大的值,会用来约束容量的初始值.
规则:容量值必须是 2 次幂,并且不能大于 2 的 30 次方.

默认负载因子
/**
 * The load factor used when none specified in constructor. 
 */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

负载因子,如果未在构造器中指定负载因子会使用这个默认值.

树化阈值
/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage. 
 */
 static final int TREEIFY_THRESHOLD = 8;

将桶中存储的链表转换成 tree 的阈值. 当值到 8 个并且向桶中添加 1个元素时就会转成树. 在从树退化回原来的链表时应该至少有 8 个值,并且 remove 两个才会转换回数组.

从树转换成链表的阙值.
/**
 * The bin count threshold for untreeifying a (split) bin during a 
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at 
 * most 6 to mesh with shrinkage detection under removal. 
 */
 static final int UNTREEIFY_THRESHOLD = 6;
桶被树化时的最小容量
/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds. 
 */
 static final int MIN_TREEIFY_CAPACITY = 64;

桶被树化的最小容量. 必须至少是 4 * 树化的阙值来避免resize 和树化操作 阙值的之间的冲突.

接着有一段很长的 Implementation notes. 这部分翻译和讲解附在最后

Node<K, V>

Node 是 HashMap 的一个内部静态类

static class Node<K,V> implements Map.Entry<K,V> {  
    final int hash;  // 存储对 key 进行 hash 运算后的值,避免重复计算
    final K key;  
    V value;  
    Node<K,V> next;  // 存储指向下一个 Node 的引用,单链表
  
  ......  省略部分代码
  
    public final V setValue(V newValue) {  // setValue 会返回设置前的值
         V oldValue = value;  
         value = newValue;  
         return oldValue;  
    }  
  
    public final boolean equals(Object o) {  
        if (o == this)  // 如果相等,== 比较的是物理地址,也就是同一个对象,肯定是返回 true. 
            return true;  
        if (o instanceof Map.Entry) {  // 如果 是 Entry 的实例,则比较 key 和 value 是否都相等.
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;  
            if (Objects.equals(key, e.getKey()) &&  
                Objects.equals(value, e.getValue()))  
                return true;  
        }  
        return false;  
     }  
}

Static utilities

Hash 方法

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

文档翻译:计算 key 的 hashCode值,并将哈希值的高位移到低位. 因为散列表大小都是 2 次幂,比当前大小大的 hash 值集合就一定会冲突(比较明显的例子就是 在一个比较的散列表中,一组 Float 类型的数据就会持续发生 hash 冲突)所以通过转换可以将高位下移从而减少这种冲突. 这是对速度,实用性和位移效率的权衡后的结果. 因为很多常见的 hash值都已经合理分布(所以这种情况下这里的移位操作没啥卵用),并且因为我们使用了树来处理数据量较大时的冲突,所以我们只要用成本最低的方式处理某些位来降低性能上的损失,考虑最高位的这种影响,否则因为 table 的容量可能永远不会用于索引计算.

大意就是

  • 将原有的 hashCode 右移 16 位
  • 因为散列表大小都是 2 次幂,如果不进行右移会非常容易 hash 冲突
  • 相比持续冲突而需要使用树来保存大量冲突的数据的话,右移的代价是值得的
  • 还可以解决因为散列表数据较少时高位 hash 不会用于索引计算的问题.

比较方法 comparableClassFor & compareComparables

    /**
     * Returns x's Class if it is of the form "class C implements
     * Comparable<C>", else null.
     */
    static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
                for (int i = 0; i < ts.length; ++i) {
                    if (((t = ts[i]) instanceof ParameterizedType) &&
                        ((p = (ParameterizedType)t).getRawType() ==
                         Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }

    /**
     * Returns k.compareTo(x) if x matches kc (k's screened comparable
     * class), else 0.
     */
    @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }
  • comparableClassFor 如果 x 实现了 Comparable 接口,就返回 x 的类,否则就返回 null.
  • compareComparables k 和 x 的比较结果,如果 x 和 k 的类型能匹配,就返回 k.compareTo(x)的结果,否则返回0.

设置散列表大小 tableSizeFor

 /**
   * Returns a power of two size for the given target capacity.
   */
  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 >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

在设置 capacity 时会调用此方法来保证 capacity 一定是 2 的次幂,并且不能超过最大容量.

Fields

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
 transient Node<K,V>[] table;

table, 第一次使用时被初始化,必要时会调整大小. 一旦被创建,长度始终是 2 次幂. (在某些操作中,如果当前并不需要的话,长度也可为 0)

   /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

保存缓存的 entrySet,注意在 AbstractMap 中是使用 keySet()values() 方法来获取.

   /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

map 中包含的键值映射数量.

   /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient int modCount;

modCount: HashMap 被结构化改变的次数.

  • 结构化改变是指改变了 HashMap 中映射数量,或者改变了它的内部结构,比如说重新 hash 计算.
  • 这个值是集合视角的迭代器用来实现 fail-fast机制的. (详情参见 ConcurrentModificationException)
   /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

阈值 ,到达这个值大小就需要调整大小.

   /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

loadFactor: 加载因子

Public Operations

先是四个构造方法,比较简单,做一些初始化的设置

public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

这里有根据 map 来构造 HashMap 的,会调用一个 put 方法来组建数据

putMapEntries, putVal

putMapEntries 参数

  • m: 原始 map
  • evict: 如果是初始化时的构造为 false,否则为 true.
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);
            }
        }
    }
  1. 如果 map 为空,不做任何操作
  2. 如果当前 HashMap 的 table(Node<K,V>[]) 为 null,判断是否需要调整扩容的阙值 threhold.
    • ( map大小 / 负载因子)+ 1.0 容量上限 的较大值 t > 阙值,则根据 t 调整阙值.
  3. 如果 map大小 > 当前阙值,扩容 resize().
  4. 循环,将键值对放入当前的 HashMap. 调用 putVal 方法.

putVal

可以结合注释和脑图一起看

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0) // 如果 table 为空
            n = (tab = resize()).length; // 初始化 table,并将 n 设置为 table 大小
        if ((p = tab[i = (n - 1) & hash]) == null) // 根据 hash 值寻址,n-1 & hash 在 n 为 2 次幂时
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) { // 循环遍历 p
                    if ((e = p.next) == null) { 
                        p.next = newNode(hash, key, value, null); // 将尾结点设为当前数据生成的 Node
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
                            // 如果 P 的子节点数 binCount > 树化阙值 - 1
                            // -1 是因为 p 头结点未算在内
                            // 转成树
                            treeifyBin(tab, hash); 
                        break; 
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break; // 如果 key 相等跳出循环, e = key 相等的这个结点
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value; // 更新 value 值
                afterNodeAccess(e);
                return oldValue; // 返回旧值
            }
        }
        ++modCount; // modCount 自增,走到着这里说明是新增了 node ,for fail-fast
        if (++size > threshold) // 判断是否需要调整大小
            resize(); // 扩容,下面会重点分析这个方法
        afterNodeInsertion(evict);
        return null;
    }

HashMap#putVal

这里比较重要的方法就是 resize: 扩容 putTreeVal: 将元素当到红黑树上 treeifyBin:将桶中的元素转换成红黑树

resize

初始化或是扩容 2 倍时调用 ,其实 resize 就做了两件事

  1. 处理桶的容量大小
  2. 处理桶中的链表/红黑树

要处理容量,还要处理下次 resize 的阈值,所以主要处理两个值 threshold 和 capacity,其中 threshold 是通过成员变量显示,而 capacity 是通过 桶的那个数组容量来体现的 所以是先计算出capacity 和 threshold(1),拷贝一份桶中的数据,再将原来的桶初始化为一个新的容量为 capacity 的数组,将原来的数据根据现有的容量重新散列这个新数组中(2)

下面具体看一下

处理容量大小

因为 threshold = capacity * loadFactor,所以只要改变了 capacity,就一定要去同步处理 threshold

概括一下就是

  1. 如果没有初始化过,初始化
  2. 如果超出最大值,threshold 设为最大值,并直接返回原有桶,不进行任何处理
  3. 如果在可 resize 的范围内,就 double 容量和 threshold

处理桶中的数据

遍历桶中的数据 如果当前桶只有一个元素e,根据新的容量计算出 e 的下标并指向 e 如果当前桶中的元素是树,则需要将树中的元素分成两份放置,根据原来的容量来计算位置是应该放在高位还是低位,这样就可以让桶中的元素分布更平均,如果不重新放置的话就失去了扩容的意义。

resize 的代码有点长,而且很大部分都是红黑树的操作就不贴了

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部