关于后端:浅入浅出-17和18的-HashMap

前言

HashMap 是咱们最最最罕用的货色了,它就是咱们在大学中学习数据结构的时候,学到的哈希表这种数据结构。面试中,HashMap 的问题也是常客,当初卷到必须答出来了,是必须会的常识。

我在学习 HashMap 的过程中,也遇到了不少问题,从概念到应用,整个过程都大大小小有些纳闷,然而我这些纳闷是因为我在某个常识环节上出了问题,导致不能了解,当我看了网上各种对于 HashMap 的无关博客以及 HashMap 的源码后,大抵是了解了,然而我又不确定我是否是真的了解了,决定把 HashMap 的根本必须会的常识全副梳理下来,势必得搞定它!

从最开始只是会应用它的 API 进行数据的存取,到决定要搞定纳闷、搞懂它的底层原理!

本篇文章,将从 0 浅入,从什么是哈希表讲起,而后再说 Java 是怎么实现哈希表的。整个梳理过程,将通过源码这个第一手的材料进行梳理剖析,排汇常识、解决疑难,一步一步进行梳理,如果你是对 HashMap 懵懵懂懂的同学,那么欢送跟着我的节奏一起来梳理!

浏览完本篇文章,你将播种

  • 意识哈希表、哈希抵触、抵触解决办法…
  • 明确 Java 中哈希表是怎么实现的…
  • table 数组的意思、哈希桶的意思、Entry 的意思、Node 的意思…
  • 1.7 的 HashMap 源码剖析流程…
  • 明确为什么曾经有了 hashCode() 办法了,为什么还须要 hash() 办法
  • 整个 put、get、扩容的过程…
  • 1.8 的 HashMap 与 1.7 的不同的中央…
  • 1.8 的扩容和 1.7 的扩容不一样的中央…

总之,我置信屏幕前的你读完必定是有播种的,当然,最大的播种目前是我本人哈哈哈。

全文1万2000多字,欢送缓缓食用!因为自己程度无限,文中必定还有许多不足之处,欢送大家指出!

学习 HashMap 之前,咱们须要晓得什么?

咱们晓得 HashMap 就是 Java 中对哈希表这种数据结构的实现,假使你不晓得什么是哈希表,那么天然学习 HashMap 就会有大大的艰难,假使你晓得哈希表,但仅仅是懵懵懂懂,有个简略理解,那天然艰难会升高许多。

所以,在学习 HashMap 之前,咱们天然须要先晓得什么是哈希表,当然还须要晓得链表,不过本篇文章仅对哈希表作出阐明。上面将开始讲讲哈希表这种形象的数据结构,之所以说形象,是因为上面只说哈希表应该具备的性能,然而不会给出具体实现,比如说咱们能够简略地应用数组来实现哈希表,是吧,然而 Java 中的哈希表的实现就不是单单一个数组就实现了的。

好了,废话少说,开搞!

什么是哈希表?

哈希表(Hash Table,也有另一个称说:散列表)。

哈希表是一种能够通过键(Key)间接拜访存储在某个地位上的值(Value)的数据结构。

Hash 被翻译成「哈希」、「散列」。Key 被翻译成「键」、「关键字」

哈希表能够用来干嘛?

很简略,和咱们以前学习的数据结构一样,能够用来存储数据。

这不是废话嘛?的确是废话。

好吧,那么都能够存储数据,为什么还会呈现哈希表?间接用以前的程序表、链表、栈、队列,这些数据结构来存储不行吗?这个问题问得好,的确,反正都是存储,为什么还要哈希表?

要答复这个问题,就得说说为什么要有数据结构了,之所以须要数据结构,有一个目标就是:更无效地进行数据的存储,不同的数据结构有不同的个性,程序表能够通过下标疾速的查找出数据、链表能够不须要占用一整片间断的存储空间进行存储等等。哈希表也是一样。

哈希表如何存储数据?

哈希表存储数据,给定一个 Key,存储一个 Value。这里就须要用到一个哈希函数(散列函数)。

以数学中的「函数」来了解,就是有一个函数是这样的 $f(x) = y$,一个 $x$ 通过函数 $f$ 映射成值 $y$ 。

那么哈希函数也能够这样了解:$hash(key) = address$

即键通过哈希函数映射成了一个地址,这个地址能够是数组下标、内存地址等。

所以呢,存储就是,通过哈希函数,把 Key 映射到某个地址,而后将 Value 存储到这个地址上。

那么存储后如何获取,如何查找到这个 Value 呢?还是一样,通过哈希函数取得 Key 映射的地址,而后从这个地址取出 Value 。现实的状况下,在哈希表中查找数据,查找的工夫复杂度是 $O(1)$ 。

所谓的「哈希」,就是 Key 通过哈希函数失去一个函数值(哈希值、哈希地址)的过程。

什么是哈希抵触?

在数学上,函数的映射能够是一对一,也能够是多对一的,也就是说一个 $x$ 能够映射一个 $y$ ,也能够多个 $x$ 映射到同一个 $y$ 上。

哈希函数也一样,它有可能呈现多对一的状况,即多个不同的 Key,通过哈希函数失去同一个地址(哈希值)。

这就呈现问题了,这种状况,就称为「哈希抵触」。

哈希抵触残缺定义:哈希函数可能把两个或两个以上的不同关键字映射到同一个地址,这种状况称为抵触。发生冲突的不同关键字称为同义词。

你想一下,如果两个不同的 Key,比方说 Key1 和 Key2,通过哈希函数失去同一个地址,那么你不解决这个抵触,间接进行存储,那么就是这样的:

  • Key1 先存储,Key2 后存储,天然只保留了 Key2
  • Key2 先存储,Key1 后存储,天然只保留了 Key1

这种状况是咱们不想看到的,所以咱们必须解决抵触。

如何解决抵触?

在解决抵触之前,咱们应该尽量减少抵触的产生,这就须要设计得OK的哈希函数。当然抵触是必然的,是逃不掉的,当数据量够多的时候,必然会发生冲突,所以就须要设计好解决抵触的办法。

哈希函数的设计留神点:

  • 函数的定义域必须蕴含所有的 Key,函数的值域必须蕴含所有的 Value。其中值域是跟哈希表的大小无关的。
  • 函数计算出来的地址(哈希值)应该可能均匀分布在哈希表的内存地址空间上,从而缩小抵触的产生。
  • 函数可能简略就简略实现,这样计算会很快。

解决抵触的办法:

解决抵触的思维就是为抵触的 Key 找下一个没有被占用的地址。

  • 凋谢定址法
  • 拉链法

这里就只说这个拉链法。

拉链法

把所有发生冲突的 Key 存储在一个线性链表中,这个链表由 Key 哈希过后失去的地址(哈希地址)惟一标识,这就是拉链法,实用于常常插入和删除的状况。

哈希表查找效率

均匀查找长度(ASL-Average Search Length),可掂量哈希表的查找效率。

ASL依赖于哈希表的「装填因子(负载因子)」

$$
装填因子的定义:α = \frac{哈希表中的元素个数}{哈希表的长度}​
$$

装填因子越大,那么抵触的可能就越大,反之亦然。

1.7 版 HashMap

当初晓得什么是哈希表了,那么接下来就看看 Java 中对哈希表的实现——HashMap

再次初识 1.7 的 HashMap

咱们先看看文档是怎么说的,同时我进行了大体的翻译。(这些阐明能够从源码的结尾找到)

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.

哈希表是通过实现 Map 接口实现的,因为 Map 接口提供了所有的映射操作,并且容许空值和空键(HashMap这个类能够简略的看作是 HashTable 类,与之不同是,HashMap 是非同步且容许存储空数据的)。HashMap 这个类不保障映射的程序,特地是不保障这个程序会随着工夫的扭转而放弃不变。

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.

当哈希函数失当地将元素映射到哈希桶(the buckets)中,那么就具备常量工夫里的基本操作(get 和 put)性能。遍历 HashMap 这个汇合的时候,遍历的工夫与 HashMap 实例的容量(哈希桶的数量)加上它的大小(Key和Value的映射数量,即键值对的数量)成正比,因而,不要设置初始的容量太高,或者负载因子太低,这是十分重要的。

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 的实例,有两个参数会影响它的性能:初始容量负载因子

初始容量就是哈希表中的哈希桶的数量,所谓哈希桶,就是一个个的数组元素所占的坑位,咱们能够称整个数组为 table 数组,而后外面的一个个元素地位(table[i])就是哈希桶。你给定一个初始容量,那么这个容量就会在 table 数组创立的时候,作为这个 table 数组的容量,即其长度、大小。

负载因子是掂量在以后 HashMap 主动扩容前,有多少个哈希桶是能够被获取到的。当哈希表中的 Entry 对象(键值对)的数量超过了负载因子和以后容量的乘积时(load factor × capacity),那么哈希表就会进行从新哈希(rehashed,重构整个哈希表),table 数组就变为原来的两倍大,即扩容两倍

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 的初始容量时,应该。思考好预期的 Entry 数量以及负载因子,以此缩小 rehash 的次数。如果哈希表的初始容量(table 数组的长度)大于 Entry 数量除以负载因子,则不会产生 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 实例,这样效率是最大的,比起你搞一个小容量的 HashMap,而后让它本人 rehash、table 数组翻倍。留神,应用许多有着雷同 hashCode() 的 Key 的话,那必定是会升高哈希表的性能的,因为抵触多了,为了升高这种影响,当这些 Key 是可比拟的状况下,那么哈希表旧能够应用比拟的形式去解决。

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 是不同步的,也就是非线程平安的,在多线程并发的状况下对 HashMap 进行操作(增加、删除、映射),就会产生线程平安问题,导致数据不统一,如果想在多线程的状况下应用 HashMap,那么能够应用 Collections.synchronizedMap 办法将一般的 HashMap 包装成同步的 HashMap。不过不举荐这样应用,咱们举荐应用 ConcurrentHashMap

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.

迭代器疾速失败(fail-fast):如果 Map 在迭代器进行迭代的时候,Map 中的数据被批改了,那么迭代器就会抛出一个异样:ConcurrentModificationException。因为怕有不确定的行为危险,次要来说就是怕数据不统一,怕线程不平安。


看完了文档的阐明,当初能够晓得,HashMap 大略有这样的货色

  • 哈希表的键值对(Entry)是存储在一个名为 table 的数组中的。Entry 的话,是把 Key、Value、hash 值,封装为 Entry 对象。
  • table 数组外面的一个个元素地位(table[i])就是哈希桶。
  • 哈希桶存储的就是 Entry,也就是说一个个的哈希桶,存储着一个个的 Entry 对象。
  • 哈希表的初始容量指的就是 table 数组的长度。
  • 哈希表的容量指的是 table 数组的长度;哈希表的大小指的是 Key 和 Value 映射的数量,即键值对的数量。这个很重要,须要搞清楚哈希表的「容量」和「容量」,别搞混了。
  • Entry 对象的数量 > load factor × capacity 时,就会主动扩容,table 数组扩容为原来的两倍。
  • 哈希表是线程不平安的。

看到这里,可能还是有些形象,没事,接下来咱们看下源码。

HashMap 中的成员变量

首先先看看 HashMap 定义的成员变量:

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{
    /**
     * The default initial capacity - MUST be a power of two.
     * 默认的初始化容量大小为16,这个大小必须为2次幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    
    /**
     * 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.
     * 最大的容量,如果任意带参构造函数传入的值大于这个最大容量,就应用这个最大容量
     * 1 左移 30位,即 2的30次方
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    /**
     * The load factor used when none specified in constructor.
     * 默认负载因子 0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     * table 数组,必要时就能够重置大小,长度必须总是2次幂,留神这里的数组类型的 Entry
     * Entry 是一个外部类,上面就能够看到了
     */
    transient Entry[] table;
    ... 
    /**
     * Entry 类,次要作为一个存储 Key 和 Value 的节点,同时保留以后的通过哈希函数计算出来的 hash
     * next 指针,次要用于发生冲突时,应用拉链法解决抵触,指向链表下一个 Entry 节点的
     */
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;     // 键
        V value;         // 值
        Entry<K,V> next; // 指向下一个节点 ,从而造成解决抵触的链表
        final int hash;  // 哈希值
        ...
    }
    
    /**
     * The number of key-value mappings contained in this map.
     * size 代表的就是以后存储在 map 中的 Key-Value 映射的数量,即 Entry 的数量
     */
    transient int size;
    
    /**
     * The next size value at which to resize (capacity * load factor).
     * @serial
     * table 重置大小的阈值,这个阈值就是之前说的 load factor * capacity
     */
    int threshold;
    
    /**
     * The load factor for the hash table.
     *
     * @serial
     * 负载因子
     */
    final float loadFactor;
    
     /**
     * 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).
     * 这个变量次要与 fail-fast 疾速失败 无关,前面再说,先留个印象。
     */
    transient int modCount;
    ...
}

所以说,在 JDK 1.7 及以前,HashMap 的底层数据结构是「数组+链表」,这里的数组指的就是 Entry 类型的 table 数组,同时应用 Entry 作为链表的节点。

上图谈话!

4 个构造方法

接下来看看构造方法,HashMap 中有 4 个构造方法,按源码中的呈现程序如下:

  • public HashMap(int initialCapacity, float loadFactor)
  • public HashMap(int initialCapacity)
  • public HashMap()
  • public HashMap(Map<? extends K, ? extends V> m)

第一个构造方法,两个参数,一个初始容量,另一个负载因子,很显著,就是结构一个有着确切初始容量和确切负载因子的 HashMap 实例,源码是这样的。

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     * 
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        // 上面3个if,是保障代码的健壮性,不是次要内容
        // 初始容量小于0,那么抛出非法参数异样
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 初始容量大于最大容量(2^30),间接将2^30作为初始容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 如果负载因子小于等于0,或者负载因子有问题,抛出异样
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // 次要内容在这里
        // Find a power of 2 >= initialCapacity
        // 找到一个二次幂的数,如果以后输出的初始容量刚好的二次幂,就不必找了
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        
        this.loadFactor = loadFactor;                // 初始化,赋值
        threshold = (int)(capacity * loadFactor);    // 主动扩容的阈值
        table = new Entry[capacity];                // 创立大小为capacity的Entry数组
        init();    // 一个空办法,有什么用?这个先不论,之后再说,目前晓得下面的就足够了。
    }

实际上,搞定下面第一个构造方法,前面的构造方法就轻而易举了。第二个构造方法,只是输出了一个初始化容量,间接调用第一个构造方法,而负载因子就是默认的 0.75。

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

第三个无参的构造方法,间接应用默认 0.75 的负载因子以及默认的初始化容量为 16 的 Entry 类型的 table 数组。而后默认的阈值就是 0.75 × 16 = 12,即当 Entry 个数超过 12,存储第 13 个 Entry 的时候,就会进行 resize、rehash。

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

第四个构造方法,接管一个确切的 Map,用 HashMap 包装这个确切的 Map

    /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
    }

以上,就是 HashMap 的 4 个构造方法,看来还是能够搞定的嘛!

扰动/哈希函数

接着看源码,发现就是 hash() 了。咱们晓得,在 Object 中,曾经有一个 hashCode() 办法了,这个 hashCode() 能够说是一个哈希函数,那为什么在 HashMap 中,又还须要另一个 hash() 办法呢?

在源码正文里曾经阐明了,就是抵挡低质量的哈希函数,让 hashCode() 计算出来的哈希码再次扰动(再次哈希),这是十分重要的,因为 HashMap 应用二次幂长度的 table 数组,不进行再次哈希的话,就会遇到 hashCode 在较低位没有差别的抵触,所以须要应用这个 hash() 办法。总而言之,就是再次扰动,升高抵触产生的概率。

有小伙伴可能有纳闷,「低质量的哈希函数」?hashCode() 不是 Java 固定实现好的吗?为什么怕有低质量的 hashCode() ?

这个问题问得好,实际上,咱们能够发现 hashCode() 是一个本地办法(Native Method)

public native int hashCode();

这就意味着,hashCode() 并不是由 Java 语言实现的,而是由 C 或 C++ 这些非 Java 语言是实现的。同一个 native 办法,如果用不同的 JVM 去调用,那么运行效率可能是不一样的,因为不同的 JVM 对于某个 native 办法都有本人的实现,所以才须要扰动函数进行再次哈希

hash() 办法(扰动函数)传入的参数是 Key 的 hashCode() 计算出来的哈希码(值),将这个哈希码通过 hash() 办法失去最终的 hash 值。

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

留个印象-indexFor

indexFor() 办法,哈希值数组长度减一进行与运算

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

获取哈希表的大小、判断哈希表是否为空

    /**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map
     */
    public int size() {
        return size;
    }

    /**
     * Returns <tt>true</tt> if this map contains no key-value mappings.
     *
     * @return <tt>true</tt> if this map contains no key-value mappings
     */
    public boolean isEmpty() {
        return size == 0;
    }

put 的过程

HashMap 的 put() 办法:

  • public V put(K key, V value)

这个办法就是将某个确切的 Key 与 某个确切的 Value 分割起来,存储到哈希表中,这样它们之间就建设起映射的关系了。

如果以后哈希表中有了这个 Key,那么就用新的 Value 笼罩掉旧的 Value。

Key 和 Value 能够是 null,只能有一个 Key 为 null,能够有多个 Value 为 null。

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        // 将 Key 的 hashCode 再次哈希失去最终的 hash 值
        int hash = hash(key.hashCode());
        // 将 hash 值与数组长度减一进行与运算,计算最终的哈希地址(即数组下标)
        int i = indexFor(hash, table.length);
        // for 循环是遍历这个哈希桶上的链表,如果有链表的话,即 e.next != null 阐明有链表了
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 如果该地位的 hash 值和以后要存储的 Key 的 hash 值一样,阐明可能是同一 Key 或不同的 Key
            // 同一 Key 的话就能够笼罩,不同 Key 的话就须要解决这个抵触
            // 先是比拟内存地址是否相等,如果内存地址不相等,再去应用 equals 办法判断两个 Key 是不是同一个。
            // 如果内存地址相等,阐明是同一个 Key 了,不用应用 equals 了
            // equals 判断是相等的话,那么必定是同一个 Key 了,因为 hashCode 相等不能阐明两个对象相等
            // 但两个对象相等的话,那么 equals 肯定相等。
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 进入这里,阐明是同一个 Key,那么就能够用新 Value 笼罩掉旧 Value 了
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);    // 这个先不论
                return oldValue;
            }
        }
        // 走到这里,阐明 Map 中没有这个 Key,那么就能够增加这个 Key-Value 的映射了
        modCount++;    // 阐明数据产生了扭转,fail-fast 会用到
        addEntry(hash, key, value, i);    // 增加这个Entry
        return null;
    }

    /**
     * Offloaded version of put for null keys
     */
    private V putForNullKey(V value) {
        // 判断有没有这个 null Key,有就新的 Value 笼罩旧的 Value
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        // 没有,那么就增加上这个 Key 为 null 的映射
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

    static class Entry<K,V> implements Map.Entry<K,V> {
        ...
         /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }       
        
    }

所以,整个过程是这样的:

将 Key 的 hashCode 再次哈希失去最终的 hash 值,而后通过这个 hash 值与数组长度减一进行与运算,计算最终的哈希地址,接着就遍历这个哈希桶(如果这个桶上有链表的话,如果这个哈希桶没有存储元素,那么间接存储到以后哈希桶),判断该地位的 hash 值和以后要存储的 Key 的 hash 值是否一样:

  • 一样阐明是同一个 Key,则能够笼罩
  • 不一样阐明不同 Key,产生哈希抵触,须要解决哈希抵触,那么先是比拟这两个 Key 的内存地址是否相等:

    • 如果内存地址不相等,再去应用 equals 办法判断两个 Key 是不是同一个。

      • equals 判断两个 Key 为 true,间接新 Value 笼罩旧 Value。
      • equals 判断两个 Key 为 false,如果以后哈希桶有下一个节点,那么下一个节点进行循环判断。如果在以后链表节点始终判断出 false,则将这个 Key 封装成 Entry,头插法插入该链表。
    • 如果内存地址相等,阐明是同一个 Key 了,不用应用 equals 了,此时间接新 Value 笼罩旧 Value。

那么到这里,我置信你曾经看懂了 put 的过程了!

get 的过程

HashMap 的 get() 办法:

  • public V get(Object key)

如果 HashMap 中有这个 Key,那么就返回这个 Key 映射的 Value。

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        // 将 Key 的 hashCode 再次哈希失去最终的 hash 值
        int hash = hash(key.hashCode());
        // indexFor(hash, table.length) 获取 Key 所在 table 数组中的下标
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            // for 循环是遍历这个哈希桶上的链表,如果有链表的话
            Object k;
            // 判断该地位上的 Key 是否为咱们须要的 Key
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

置信你搞懂了 put 的过程,那么 get 的过程也不难理解,过程是这样的:

将 Key 的 hashCode 再次哈希失去最终的 hash 值,而后通过这个 hash 值与数组长度减一进行与运算,计算最终的哈希地址(被封装成 indexFor 办法了),接着还是一样,遍历哈希桶,判断该地位上的 Key 是否为咱们须要的 Key。

主动扩容-resize+transfer

下面咱们也说了,有一个阈值,即 load factor × capacity 这个阈值,如果以后哈希表的大小超过了这个阈值,那么哈希表是须要扩容的,在 HashMap 中,它是不要手动干涉,是会主动进行扩容的。那么它是怎么主动扩容的?

回顾:

  • 哈希表的容量:是指 table 数组的长度。
  • 哈希表的大小:是指存储在哈希表中的元素(Entry 类型的元素)的个数。
  • capacity(容量):默认16
  • load factor(负载因子):默认0.75
  • threshold(阈值):默认 0.75 × 16 = 12,即哈希表大小超过12就会主动扩容

咱们回去看下 put 操作,能够看到倒数第二行代码有个 addEntry() 办法

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);    // 就是这里,增加 Entry 对象
        return null;
    }

addEntry() 的源码,是这样的:

  • 存储 Key、Value、hash 值到指定的哈希桶中。
  • 判断以后哈希表大小加一后,有没有超出阈值。超过阈值则进行哈希表容量的 resize() 操作。

所以这个扩容就是通过 addEntry() 办法里的 size++ >= threshold 进行判断是否须要扩容,进而调用扩容办法 resize() 实现所谓的主动扩容。

    /**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

咱们能够看到 resize() 的时候,参数是两倍的数组长度,也就是说将哈希表的容量扩充成原来的两倍。

resize(2 * table.length);

那上面咱们看看扩容是怎么子的,看看 resize() 源码:

源码正文也说了,将会对 HashMap 实例存储的 Entry 进行 rehash(再次哈希)到一个扩容后的新数组。如果以后容量是最大容量(MAXIMUM_CAPACITY,1 <<< 30,即$2^{30}$)了,那么就不会进行扩容,同时设置阈值为 Integer.MAX_VALUE

    /**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     *
     * If current capacity is MAXIMUM_CAPACITY, this method does not
     * resize the map, but sets threshold to Integer.MAX_VALUE.
     * This has the effect of preventing future calls.
     *
     * @param newCapacity the new capacity, MUST be a power of two;
     *        must be greater than current capacity unless current
     *        capacity is MAXIMUM_CAPACITY (in which case value
     *        is irrelevant).
     */
    void resize(int newCapacity) {
        Entry[] oldTable = table;            // 原数组
        int oldCapacity = oldTable.length;    // 原数组长度 = 原容量
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        // 创立一个比原数组长度大两倍的新数组
        Entry[] newTable = new Entry[newCapacity];
        // 转移原数组中的元素(Entry 对象)到新数组中
        transfer(newTable);
        // 原数组援用指向新数组
        table = newTable;
        // 从新计算阈值
        threshold = (int)(newCapacity * loadFactor);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        Entry[] src = table;    // 原数组
        int newCapacity = newTable.length;
        // 遍历原数组
        for (int j = 0; j < src.length; j++) {
            // e 能够看成一个指针,指向第j个哈希桶上的Entry节点
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    // 看以后地位上的 Entry 有没有 next,有则阐明是链表
                    // next 是 null,阐明没有链表,那么就不会执行上面的 while
                    Entry<K,V> next = e.next;
                    // 计算以后 Entry 在新数组中的地位
                    int i = indexFor(e.hash, newCapacity);
                    // e 的下一个节点指向新的哈希桶,能够把哈希桶当作表头,这样不便头插法插入元素
                    e.next = newTable[i];
                    // 新的哈希桶存储这个节点
                    newTable[i] = e;
                    // 挪动指针 e 指向下一节点
                    e = next;
                } while (e != null);
            }
        }
    }

所以,总的来说,扩容的过程是这样的

咱们 put 一个元素到哈希表,这个过程会调用 addEntry() 办法,在理论插入一个元素后,判断以后 size 是否大于阈值,大于的话就会扩容,扩容的话,会传入一个两倍原数组大小的参数,而后创立一个新的数组,这个数组的长度是原数组的两倍,再通过一个 transfer() 办法,将原数组中的 Entry 从新哈希(rehash)到新数组中,最初将原数组援用指向新数组,同时计算下新的阈值。

1.7 总结

1.7 的 HashMap,底层是 Entry 类型的数组 + Entry 类型的链表

这个数组称为 table 数组(也有的人称为桶数组),数组上的每个地位,能够称为哈希桶,每一个哈希桶都是存储 Entry 类型的元素的,同时能够晓得每个哈希桶地位上都能够对应着一个解决抵触的链表的地位

如果当要存储的 Key-Value 的 Key 与以后地位上的 Key 发生冲突,那么就须要进行头插法,将该 Key 插入以后哈希桶对应的链表。

如果以后存储的元素的个数超过了阈值(threshold = load factor × capacity),那么就会进行扩容,创立一个两倍原数组大小的新数组,而后将原数组中的元素从新哈希到新数组中,最初原数组援用指向新数组,进而实现扩容。

1.8 版 HashMap

在 JDK 1.8 开始,就变成了「数组+链表/红黑树」

看看源码与1.7有什么区别

看看区别

  • DEFAULT_INITIAL_CAPACITY 写法变高级了,从 16 间接改成 1 << 4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  • 呈现一个TREEIFY_THRESHOLD,树化阈值,即链表转成红黑树的阈值,默认为 8。
static final int TREEIFY_THRESHOLD = 8;
  • 呈现一个UNTREEIFY_THRESHOLD,解除树化的阈值,即红黑树中的 Entry 数量小于 6,那么就从红黑树进化成链表。
static final int UNTREEIFY_THRESHOLD = 6;
  • 呈现一个MIN_TREEIFY_CAPACITY,最小树化容量,即 table 数组的长度最小须要 64,才有机会树化。
static final int MIN_TREEIFY_CAPACITY = 64;

Node

接着,咱们看到这里定义了一个 Node 节点,通过比照 1.7 版的,能够发现这个把 1.7 中的 Entry 换了个名,定义成 Node 节点。也就是说,在 1.8 中的 table 数组,其类型不再是 Entry 类型,而是 Node 类型,即 Node 类型的 table 数组。

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        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;
        }
    }

Node 数组

transient Node<K,V>[] table;

扰动函数

hash(),扰动函数产生了变动,1.8 源码是这样的:

让 Key 的 hashCode 与上 hashCode 无符号右移 16 位,最终与运算的后果就是最终的 hash 值。

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

而 1.7 的是这样的:

    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

构造方法

构造方法也有变动,然而次要的过程还是一样的,次要的区别就是,此时的 table 数组还没有被创立进去。

    /**
     * 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;
    }

    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);
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

能够说在 1.8 这里,HashMap 属于懒加载的了,那么 table 数组何时加载(创立)呢?没错,就是在 put 的时候才创立的。上面咱们来看看。

put 的变动

put 多了一层封装,须要在 putVal() 办法中了解

  • final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
  • hash:Key 通过扰动函数失去最终 hash 值。
  • keyvalue:键 和 值。
  • onlyIfAbsent:如果为 true,那么不会扭转已存在的值。
  • evict:如果为 false,阐明 table 数组正在创立中。

put 的思路还是一样的:依据 Key 计算出哈希地址,判断这个地址上有没有抵触,没有则直接插入这个 Node,有则须要解决抵触。变动大的就是代码的实现(红黑树、尾插法)。

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // tab-> table 数组
        // p-> node 指针,指向哈希桶中第一个节点,能够说是链表表头节点
        // n-> 代表 table 数组的长度
        // i-> 代表 table 数组的下标
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 第一次 put 就会进入这个判断,进行数组的创立
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果 put 的这个 Key,找到的地位不会抵触,那么间接创立一个 Node 节点存储这个键值对
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            // 发生冲突进入这里
            Node<K,V> e; K k;
            // 判断是否是同一个Key,是就把指针 e 指向这个节点 p,而后间接走上面的 e 是否为空的判断了
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)    // Key 不同,走这里,如果这个节点 p 是一个树节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {    // Key 不同,没有树化,须要遍历链表
                for (int binCount = 0; ; ++binCount) {
                    // e 指向的 p 的下一个节点,如果为空,阐明是链表尾部了
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        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;
                    // 挪动指针
                    p = e;
                }
            }
            // 这里就是,如果是同一个 Key ,就会走这里的笼罩
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)    // 判断是否须要扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

get 的变动

get 也是,多了一层封装,思路还是一样,获取哈希地址,判断该地位上的元素是否是咱们想要的。

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 判断以后哈希表是否存在、是否有元素、失去的哈希地址上是否有元素(算法的健壮性)
        // 判断为 false 的话,天然阐明没有任何元素,还 get 个 p?
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 哈希桶第一个元素是咱们想要的?是就间接返回了
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 不是,那么看哈希桶上的链表/红黑树
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

扩容机制

1.8 的扩容机制,变动就大了!在 1.7 的时候,次要是通过 resize()transfer() 相互配合实现扩容及元素转移的,在 1.8 的时候,间接把 transfer() 也搞到 resize() 中了,而且 transfer 的 rehash 的算法很美好。不过扩容机会还是一样,超过阈值就会扩容。

咱们看看源码是这样的:

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;    // 一开始 table 还没创立,所以第一次这里的 oldTab 为空
        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 数组(当然,第一次创立数组也是在这里创立)
        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) {    // 判断第j个哈希桶是否为空
                    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;
                            // 如果这个与操作后果为0,那么放入新数组的地位和原数组的地位是一样的
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)    // 间接放入
                                    loHead = e;
                                else                // 尾插法
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 与操作后果不为0,须要从新计算寄存的地位
                            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;
                        }
                    }
                }
            }
        }
        // 第一次不会走下面的 if,间接返回新创建默认容量和阈值的数组
        return newTab;
    }

这外面最难了解的就是 (e.hash & oldCap) == 0

  • 运算后果为 0 的话,那么放入新数组的地位和原数组的地位是一样的
  • 运算后果不为 0 的话,那么就须要从新计算地位(新地位:所在的原数组地位下标加上原数组容量(长度))

了解 (e.hash & oldCap) == 0

须要晓得的是:

  • e.hash: e 能够看成一个指针,是一个指向以后遍历到的 Node 节点的指针,hash 指的是该 Node 节点存储的 Key 的 hash 值,即 hash 值是通过 hash(key.hashCode()) 失去的最终存储的 hash 值。
  • oldCap:示意原数组的容量,即原数组长度,同时这个长度是 2 次方幂,比方 $2^4 = 16$

何时这个操作等于 0 ?

咱们能够从 oldCap 动手,假如 oldCap 是 16,那么其二进制为 10000

如果咱们想 e.hash & oldCap 等于 0,那么该 Key 的 hash 值的二进制最高位必须为 0,剩下的二进制位能够不论,这样进行与运算后的后果必定是等于 0 的。

举个例子,假如此时 hash 值对应的二进制为 01111,那么和 oldCap 进行与运算:

`e.hash & oldCap = 10000 & 01111 = 00000 = 0

不言而喻,当 hash 值二进制的最高位为 0 的时候,和 oldCap 进行与运算后,后果必然为0

然而这个和扩容后地位有什么关系呢?咱们晓得,扩容是扩为原来的两倍的,所以咱们能够看下,计算扩容后该Node 节点应该在哪个新地位。

计算扩容后的地位,咱们晓得是这样的,「hash 值 & 数组长度减一」的运算后果,就是咱们须要的数组下标。

扩容后的应该在的地位(oldCap 是 16,2 倍就是32,32 对应二进制 100000,减一操作后为 011111):

hash & 2 × oldCap - 1 = 01111 & 011111 = 01111

那没扩容之前的地位在那里?咱们计算下:

hash & oldCap - 1 = 01111 & 01111 = 01111

所以,咱们能够发现,此时扩容后和扩容前,该元素的地位没有发生变化。 因而,才有这个论断:运算后果为 0 的话,那么放入新数组的地位和原数组的地位是一样的

何时这个操作不等于 0 ?

同样,从 oldCap 动手,假如此时 oldCap 是16,对应二进制为 10000

如果咱们想 e.hash & oldCap 不等于 0,那么该 Key 的 hash 值的二进制最高位必须为 1,剩下的二进制位能够不论,这样进行与运算后的后果必定是不等于 0 的。

还是一样,举例子,假如 hash 值对应的二进制为 10001,那么和 oldCap 进行与运算:

e.hash & oldCap = 10001 & 10000 = 10000 = 16 ≠ 0

不言而喻,hash 值二进制的最高位为 1,那么该后果必然不为 0

同理,来看下扩容前后的地位关系。

扩容前的地位:

hash & oldCap - 1 = 10001 & 01111 = 00001 = 1

扩容后的地位:

hash & 2 × oldCap - 1 = 10001 & 011111 = 10001 = 17

它们之间有一种奇妙的关系,就是:「扩容后的地位」会等于「扩容前的地位」加上「扩容前的数组容量」,也就是说 10001(扩容后的地位) = 1(扩容前的地位) + 10000(扩容前的数组容量,16)

所以,才有这个论断:运算后果不为 0 的话,那么就须要从新计算地位(新地位:所在的原数组地位下标加上原数组容量(长度))

对于红黑树

待欠缺,等着填坑。

1.8 总结

在 1.8 的 HashMap中,底层是 Node 类型的数组 + Node 类型的链表 或者 + Node 类型的红黑树。

比起 1.7 来说,变动还是挺多的,源码的写法也变得更加高级,当然效率也变得更高了,引入了红黑树进步查找效率。因为引入了红黑树,所以解决抵触的时候,就有些区别了。

如果当要存储的 Key-Value 的 Key 与以后地位上的 Key 发生冲突,那么就须要进行尾插法(1.7 就是头插法),将该 Key 插入以后哈希桶对应的链表,当这个链表的长度大于 8 且数组长度大于等于 64 时,以后链表就会树化,转成红黑树,当红黑树中的元素小于 6 时,那么就会进化回来成为链表。如果仅仅链表长度大于 8,然而数组长度小于 64,那么就只会进行扩容,不会把链表树化(这部分的源码在 treeifyBin() 办法中)。

结语

以上,就是浅入浅出 1.7 和 1.8 的 HashMap!

最初的最初

由自己程度所限,不免有谬误以及不足之处, 屏幕前的靓仔靓女们 如有发现,恳请指出!

最初,谢谢你看到这里,谢谢你认真对待我的致力,心愿这篇博客对你有所帮忙!

你轻轻地点了个赞,那将在我的心里世界削减一颗亮堂而夺目的星!

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据