HashMap

https://juejin.im/post/5dee6f54f265da33ba5a79c8

HashMap实现了Map接口，并继承 AbstractMap 抽象类，其中 Map 接口定义了键值映射规则。AbstractMap 抽象类提供了 Map 接口的骨干实现，以最大限度地减少实现Map接口所需的工作。

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

初始容量 和 负载因子(一般默认0.75)，这两个参数是影响HashMap性能的重要参数。其中，容量表示哈希表中桶的数量 (table 数组的大小)，初始容量是创建哈希表时桶的数量；负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。

哈希的相关概念

　　Hash 就是把任意长度的输入(又叫做预映射， pre-image)，通过哈希算法，变换成固定长度的输出(通常是整型)，该输出就是哈希值。这种转换是一种 压缩映射 ，也就是说，散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出，从而不可能从散列值来唯一的确定输入值。简单的说，就是一种将任意长度的消息压缩到某一固定长度的息摘要函数。

 1  /**
 2      * Constructs an empty HashMap with the default initial capacity
 3      * (16) and the default load factor (0.75).
 4      */
 5     public HashMap() {
 6 
 7         //负载因子:用于衡量的是一个散列表的空间的使用程度
 8         this.loadFactor = DEFAULT_LOAD_FACTOR; 
 9 
10         //HashMap进行扩容的阈值，它的值等于 HashMap 的容量乘以负载因子
11         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
12 
13         // HashMap的底层实现仍是数组，只是数组的每一项都是一条链
14         table = new Entry[DEFAULT_INITIAL_CAPACITY];
15 
16         init();
17     }
18 
19 
20 
21 static class Entry<K,V> implements Map.Entry<K,V> {
22 
23     final K key;     // 键值对的键
24     V value;        // 键值对的值
25     Entry<K,V> next;    // 下一个节点
26     final int hash;     // hash(key.hashCode())方法的返回值
27 
28     /**
29      * Creates new entry.
30      */
31     Entry(int h, K k, V v, Entry<K,V> n) {     // Entry 的构造函数
32         value = v;
33         next = n;
34         key = k;
35         hash = h;
36     }
37 
38     ......
39 
40 }

View Code

其中，Entry为HashMap的内部类，实现了 Map.Entry 接口，其包含了键key、值value、下一个节点next，以及hash值四个属性。事实上，Entry 是构成哈希表的基石，是哈希表所存储的元素的具体形式。

HashMap 的存储实现

在 HashMap 中，键值对的存储是通过 put(key,vlaue) 方法来实现的，其源码如下：

 1 public V put(K key, V value) {
 2 
 3         //当key为null时，调用putForNullKey方法，并将该键值对保存到table的第一个位置 
 4         if (key == null)
 5             return putForNullKey(value); 
 6 
 7         //根据key的hashCode计算hash值
 8         int hash = hash(key.hashCode());             //  ------- (1)
 9 
10         //计算该键值对在数组中的存储位置（哪个桶）
11         int i = indexFor(hash, table.length);              // ------- (2)
12 
13         //在table的第i个桶上进行迭代，寻找 key 保存的位置
14         for (Entry<K,V> e = table[i]; e != null; e = e.next) {      // ------- (3)
15             Object k;
16             //判断该条链上是否存在hash值相同且key值相等的映射，若存在，则直接覆盖 value，并返回旧value
17             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
18                 V oldValue = e.value;
19                 e.value = value;
20                 e.recordAccess(this);
21                 return oldValue;    // 返回旧值
22             }
23         }
24 
25         modCount++; //修改次数增加1，快速失败机制
26 
27         //原HashMap中无该映射，将该添加至该链的链头
28         addEntry(hash, key, value, i);            
29         return null;
30     }

View Code

在上述的 put(key,vlaue) 方法的源码中，我们标出了 HashMap 中的哈希策略（即(1)、(2)两处），hash() 方法用于对Key的hashCode进行重新计算，而 indexFor() 方法用于生成这个Entry对象的插入位置。当计算出来的hash值与hashMap的(length-1)做了&运算后，会得到位于区间[0，length-1]的一个值。特别地，这个值分布的越均匀， HashMap 的空间利用率也就越高，存取效率也就越好。

使用hash()方法对一个对象的hashCode进行重新计算是为了防止质量低下的hashCode()函数实现。由于hashMap的支撑数组长度总是 2 的幂次，通过右移可以使低位的数据尽量的不同，从而使hash值的分布尽量均匀。更多关于该 hash(int h)方法的介绍请见《HashMap hash方法分析》

我们知道，HashMap的底层数组长度总是2的n次方。当length为2的n次方时，h&(length - 1)就相当于对length取模，而且速度比直接取模要快得多，这是HashMap在速度上的一个优化。

内部源码如下:

  1 /**
  2      * Offloaded version of put for null keys
  3      */
  4     private V putForNullKey(V value) {
  5         // 若key==null，则将其放入table的第一个桶，即 table[0]
  6         for (Entry<K,V> e = table[0]; e != null; e = e.next) {   
  7             if (e.key == null) {   // 若已经存在key为null的键，则替换其值，并返回旧值
  8                 V oldValue = e.value;
  9                 e.value = value;
 10                 e.recordAccess(this);
 11                 return oldValue;
 12             }
 13         }
 14         modCount++;        // 快速失败
 15         addEntry(0, null, value, 0);       // 否则，将其添加到 table[0] 的桶中
 16         return null;
 17     }
 18 ————————————————
 19 /**
 20      * Applies a supplemental hash function to a given hashCode, which
 21      * defends against poor quality hash functions.  This is critical
 22      * because HashMap uses power-of-two length hash tables, that
 23      * otherwise encounter collisions for hashCodes that do not differ
 24      * in lower bits. 
 25      * 
 26      * Note: Null keys always map to hash 0, thus index 0.
 27      */
 28     static int hash(int h) {
 29         // This function ensures that hashCodes that differ only by
 30         // constant multiples at each bit position have a bounded
 31         // number of collisions (approximately 8 at default load factor).
 32         h ^= (h >>> 20) ^ (h >>> 12);
 33         return h ^ (h >>> 7) ^ (h >>> 4);
 34     }
 35 ————————————————
 36 /**
 37      * Returns index for hash code h.
 38      */
 39     static int indexFor(int h, int length) {
 40         return h & (length-1);  // 作用等价于取模运算，但这种方式效率更高
 41     }
 42 ————————————————
 43 /**
 44      * Adds a new entry with the specified key, value and hash code to
 45      * the specified bucket.  It is the responsibility of this
 46      * method to resize the table if appropriate.
 47      *
 48      * Subclass overrides this to alter the behavior of put method.
 49      * 
 50      * 永远都是在链表的表头添加新元素
 51      */
 52     void addEntry(int hash, K key, V value, int bucketIndex) {
 53 
 54         //获取bucketIndex处的链表
 55         Entry<K,V> e = table[bucketIndex];
 56 
 57         //将新创建的 Entry 链入 bucketIndex处的链表的表头 
 58         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
 59 
 60         //若HashMap中元素的个数超过极限值 threshold，则容量扩大两倍
 61         if (size++ >= threshold)
 62             resize(2 * table.length);
 63     }
 64 ————————————————
 65 /**
 66      * Rehashes the contents of this map into a new array with a
 67      * larger capacity.  This method is called automatically when the
 68      * number of keys in this map reaches its threshold.
 69      *
 70      * If current capacity is MAXIMUM_CAPACITY, this method does not
 71      * resize the map, but sets threshold to Integer.MAX_VALUE.
 72      * This has the effect of preventing future calls.
 73      *
 74      * @param newCapacity the new capacity, MUST be a power of two;
 75      *        must be greater than current capacity unless current
 76      *        capacity is MAXIMUM_CAPACITY (in which case value
 77      *        is irrelevant).
       随着HashMap中元素的数量越来越多，发生碰撞的概率将越来越大，所产生的子链长度就会越来越长，这样势必会影响HashMap的存取速度。为了保证
       HashMap的效率，系统必须要在某个临界点进行扩容处理，该临界点就是HashMap中元素的数量在数值上等于threshold（table数组长度*加载因子）。
       但是，不得不说，扩容是一个非常耗时的过程，因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。所以，如果我们能够提前预知HashMap 
       中元素的个数，那么在构造HashMap时预设元素的个数能够有效的提高HashMap的性能。

 78      */
 79     void resize(int newCapacity) {
 80         Entry[] oldTable = table;
 81         int oldCapacity = oldTable.length;
 82 
 83         // 若 oldCapacity 已达到最大值，直接将 threshold 设为 Integer.MAX_VALUE
 84         if (oldCapacity == MAXIMUM_CAPACITY) {  
 85             threshold = Integer.MAX_VALUE;
 86             return;             // 直接返回
 87         }
 88 
 89         // 否则，创建一个更大的数组
 90         Entry[] newTable = new Entry[newCapacity];
 91 
 92         //将每条Entry重新哈希到新的数组中
 93         transfer(newTable);
 94 
 95         table = newTable;
 96         threshold = (int)(newCapacity * loadFactor);  // 重新设定 threshold
 97     }
 98 ————————————————
 99  /**
100      * Transfers all entries from current table to newTable.重哈希的主要是一个重新计算原HashMap中的元素在新table数组中的位置并进行复制处理的过程
101      */
102     void transfer(Entry[] newTable) {
103 
104         // 将原数组 table 赋给数组 src
105         Entry[] src = table;
106         int newCapacity = newTable.length;
107 
108         // 将数组 src 中的每条链重新添加到 newTable 中
109         for (int j = 0; j < src.length; j++) {
110             Entry<K,V> e = src[j];
111             if (e != null) {
112                 src[j] = null;   // src 回收
113 
114                 // 将每条链的每个元素依次添加到 newTable 中相应的桶中
115                 do {
116                     Entry<K,V> next = e.next;
117 
118                     // e.hash指的是 hash(key.hashCode())的返回值;
119                     // 计算在newTable中的位置，注意原来在同一条子链上的元素可能被分配到不同的子链
120                     int i = indexFor(e.hash, newCapacity);   
121                     e.next = newTable[i];
122                     newTable[i] = e;
123                     e = next;
124                 } while (e != null);
125             }
126         }
127     }
128 ————————————————

总而言之，上述的hash()方法和indexFor()方法的作用只有一个：保证元素均匀分布到table的每个桶中以便充分利用空间。

HashMap 永远都是在链表的表头添加新元素。此外，若HashMap中元素的个数超过极限值 threshold，其将进行扩容操作，一般情况下，容量将扩大至原来的两倍。

HashMap 的读取实现

 1 /**
 2      * Returns the value to which the specified key is mapped,
 3      * or {@code null} if this map contains no mapping for the key.
 4      *
 5      * <p>More formally, if this map contains a mapping from a key
 6      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 7      * key.equals(k))}, then this method returns {@code v}; otherwise
 8      * it returns {@code null}.  (There can be at most one such mapping.)
 9      *
10      * <p>A return value of {@code null} does not <i>necessarily</i>
11      * indicate that the map contains no mapping for the key; it's also
12      * possible that the map explicitly maps the key to {@code null}.
13      * The {@link #containsKey containsKey} operation may be used to
14      * distinguish these two cases.
15      *
16      * @see #put(Object, Object)
17      */
18     public V get(Object key) {
19         // 若为null，调用getForNullKey方法返回相对应的value
20         if (key == null)
21             // 从table的第一个桶中寻找 key 为 null 的映射；若不存在，直接返回null
22             return getForNullKey();  
23 
24         // 根据该 key 的 hashCode 值计算它的 hash 码 
25         int hash = hash(key.hashCode());
26         // 找出 table 数组中对应的桶
27         for (Entry<K,V> e = table[indexFor(hash, table.length)];
28              e != null;
29              e = e.next) {
30             Object k;
31             //若搜索的key与查找的key相同，则返回相对应的value
32             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
33                 return e.value;
34         }
35         return null;
36     }

View Code

/**
     * Offloaded version of get() to look up null keys.  Null keys map
     * to index 0.  This null case is split out into separate methods
     * for the sake of performance in the two most commonly used
     * operations (get and put), but incorporated with conditionals in
     * others.
     */
    private V getForNullKey() {
        // 键为NULL的键值对若存在，则必定在第一个桶中
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        // 键为NULL的键值对若不存在，则直接返回 null
        return null;
    }

HashMap 的底层数组长度为何总是2的n次方？

HashMap 中的数据结构是一个数组链表，我们希望的是元素存放的越均匀越好。最理想的效果是，Entry数组中每个位置都只有一个元素，这样，查询的时候效率最高，不需要遍历单链表，也不需要通过equals去比较Key，而且空间利用率最大。

那如何计算才会分布最均匀呢？HashMap采用了一个分两步走的哈希策略：

1.使用 hash() 方法用于对Key的hashCode进行重新计算，以防止质量低下的hashCode()函数实现。由于hashMap的支撑数组长度总是 2 的倍数，通过右移可以使低位的数据尽量的不同，从而使Key的hash值的分布尽量均匀；

// HashMap 的容量必须是2的幂次方，超过 initialCapacity 的最小 2^n 
int capacity = 1;
while (capacity < initialCapacity)
    capacity <<= 1;

2.使用 indexFor() 方法进行取余运算，以使Entry对象的插入位置尽量分布均匀

《java提高篇（二三）—–HashMap》

总结:

不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，空间利用率较高，查询速度也较快；

h&(length - 1) 就相当于对length取模，而且在速度、效率上比直接取模要快得多，即二者是等价不等效的，这是HashMap在速度和效率上的一个优化。

https://blog.csdn.net/justloveyou_/article/details/62893086

注:HashMap 和 ConcurrentHashMap 在 1.7 和 1.8 中不同的实现方式

https://blog.csdn.net/weixin_44460333/article/details/86770169