Java集合类框架学习 4.1 —— HashMap(JDK1.6)-白红宇

Java集合类框架学习 4.1 —— HashMap(JDK1.6)

阅读量：4297 次

发布时间：2019-05-27

本文共 18562 字，大约阅读时间需要 61 分钟。

这篇开始看HashMap，先从1.6的开始，它是基础。理解了1.6的之后，再看下1.7以及1.8的改进。

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

一、基本性质

1、基于哈希表的Map接口实现，使用链地址法处理hash冲突。如果hash函数绝对随机均匀，那么基本操作（get和put）的时间性能基本是恒定的。迭代操作所需的时间大致与HashMap的容量（hash桶的个数，table.length）和K-V对的数量（size）的和成正比，因此，如果迭代性能很重要，不要将初始容量设置得太高（或负载系数太低）。

2、HashMap有两个影响其性能的参数：初始容量initCapacity，和负载因子loadFactor。容量是哈希表中的hash桶的个数，initCapacity只是创建哈希表时的容量，loadFactor是衡量哈希表在扩容之前允许达到多少的量度。当哈希表中的条目数量超过loadFactor和当前容量capcity的乘积threshold时，哈希表会扩容为两倍的大小，并且进行重新散列（重建内部数据结构，各个K-V对重新存储到新的哈希表中）。

默认负载因子0.75在时间成本和空间成本之间提供了良好的平衡。较高的值loadFactor会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put）。在设置其初始容量时，应考虑映射中的预期条目数（size）及其负载因子（loadFactor），提前设置好。这样能尽量节省空间，并且减少扩容次数，提高HashMap整体存储效率。

3、允许null key和null value，null key总是放在第一个hash桶中。

4、非同步，可以使用Collections.synchronizedMap包装下进行同步，这样具体实现还是使用HashMap的实现；也可以使用Hashtable，它的方法是同步的，但是实现上可能和HashMap有区别；多数场景下，可以使用ConcurrentHashMap。

5、跟ArrayList一样，HashMap的迭代器是fail-fast迭代器。

6、实现Cloneable接口，可clone。

7、实现Serializable接口，可序列化/反序列化。

8、HashMap中，Key的hash值（hashCode）会优先于 == 和 equals，这一点后面有解释。

基本结构的简单示意图，可以看下。

二、常量和变量

1、常量

/** The default initial capacity - MUST be a power of two. */static final int DEFAULT_INITIAL_CAPACITY = 16; // 数组table的默认初始化大小，容量必须是2^n形式的数/** * 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; // hash桶最大数量（table数组的最大长度），size超过此数量之后无法再扩容了/**  The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子

2、变量

/** The table, resized as necessary. Length MUST Always be a power of two. */transient Entry[] table; // 底层的hash桶数组，长度必须是2^n，容量不足时可以扩容/** The number of key-value mappings contained in this map. */transient int size; // K-V对的数量。注意，为了兼容size方法才使用int，HashMap的实际size可能会大于Integer.MAX_VALUE，理论上long类型才是比较好的值，实际中大多数int型也够用/** The next size value at which to resize (capacity * load factor). */int threshold; // 扩容阈值，一般值为table.length * loadFactor，不能扩容时使用Integer.MAX_VALUE来表示后续永远不会扩容/** The load factor for the hash table. */final float loadFactor; // 加载因子，注意，此值可以大于1/** * 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 volatile int modCount; // 大多数实现类都有的modCountprivate transient Set
    
     
      > entrySet = null;// keySet values继承使用AbstractMap的父类的属性

三、基本类

也就是每个K-V对的包装类，也叫作节点，比较基础的类。

static class Entry
    
      implements Map.Entry
     
       {    final K key;    V value;    Entry
      
        next;    final int hash; // final的，扩容时hash值还是使用的旧值，只是重新计算索引再散列    Entry(int h, K k, V v, Entry
       
         n) {        value = v;        next = n;        key = k;        hash = h;    }    public final K getKey() {        return key;    }    public final V getValue() {        return value;    }    public final V setValue(V newValue) {        V oldValue = value;        value = newValue;        return oldValue;    }    public final boolean equals(Object o) {        if (!(o instanceof Map.Entry))            return false;        Map.Entry e = (Map.Entry)o;        Object k1 = getKey();        Object k2 = e.getKey();        if (k1 == k2 || (k1 != null && k1.equals(k2))) {            Object v1 = getValue();            Object v2 = e.getValue();            if (v1 == v2 || (v1 != null && v1.equals(v2)))                return true;        }        return false;    }    public final int hashCode() {        return (key==null   ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());    }    public final String toString() {        return getKey() + "=" + getValue();    }    // 提供给子类实现的方法，在LinkedHashMap中有实现    void recordAccess(HashMap
        
          m) {}    void recordRemoval(HashMap
         
           m) {}}

四、构造方法与初始化

// 1.6的构造方法是会真正初始化数组的，到了1.7就开始使用懒初始化，在第一次进行put/putAll等操作时才会真正初始化table数组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);    // Find a power of 2 >= initialCapacity    int capacity = 1;    while (capacity < initialCapacity) // 用循环找出满足的2^n        capacity <<= 1;    this.loadFactor = loadFactor;    threshold = (int)(capacity * loadFactor);    table = new Entry[capacity]; // 真正初始化table数组    init(); // 这个方法里面什么都没做}public HashMap(int initialCapacity) {    this(initialCapacity, DEFAULT_LOAD_FACTOR);}// 默认构造方法，相当于new HashMap(16, 0.75f)public HashMap() {    this.loadFactor = DEFAULT_LOAD_FACTOR;    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);    table = new Entry[DEFAULT_INITIAL_CAPACITY]; // 真正初始化数组    init();}// loadFactor使用默认值0.75f，因为m是接口类型，可能没有loadFactor这个属性public HashMap(Map
     m) {    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);    putAllForCreate(m); // 因为m是一个空的map}void init() {}// 特化的一个put，使用createEntry而不是addEntry，不会触发扩容（容量已经设置好了），也不会修改modCountprivate void putForCreate(K key, V value) {    int hash = (key == null) ? 0 : hash(key.hashCode());    int i = indexFor(hash, table.length);    /**     * Look for preexisting entry for key.  This will never happen forclone or deserialize.     * It will only happen for construction if the input Map is a sorted map whose ordering is inconsistent w/ equals.     */    // 因为不同的Map实现中判别“相等”的方式可能不一样，因此HashMap这里需要用自己的方式再比较下    for (Entry
    
      e = table[i]; e != null; e = e.next) {        Object k;        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {            e.value = value;            return;        }    }    createEntry(hash, key, value, i);}private void putAllForCreate(Map
      m) {    for (Iterator
     > i = m.entrySet().iterator(); i.hasNext();) {        Map.Entry
      e = i.next();        putForCreate(e.getKey(), e.getValue());    }}// 在初始化时使用的一个特化的添加节点的方法void createEntry(int hash, K key, V value, int bucketIndex) {    Entry
     
       e = table[bucketIndex];    table[bucketIndex] = new Entry
      
       (hash, key, value, e);    size++;}

五、一些内部方法

jdk1.6的主要有两个，一个hash函数，一个hash桶定位。

/**  Returns index for hash code h. */// hash桶定位方法，利用length = 2^n的特性，使用位运算加快速度static int indexFor(int h, int length) {    return h & (length-1);}

这个方法就是用来把hash值散列到table数组某个位置的方法。

HashMap是利用哈希表来加速查找的集合类。它当中使用的hash值是一个32bit的整数，而HashMap的hash桶的初始数目为16，是无法跟全部整数一一对应的，因此需要根据hash值进行散列，使得不同Entry能均匀存储到所有hash桶中。最常见的散列方式就是用hash值对hash桶的数目进行取模。十进制中常用的取模方法是%，是用除法实现的。对于2^n这种数，可以利用位运算取模，具体的做法就是 & (2^n-1)。因为除以2^n相当于右移n位，%2^n相当于保留最低的n位，而(2^n-1)这种数的最低的n位1，%2^n就相当于 &(2^n-1)。(2^n-1)这种二进制中有效的1都是从最低位开始连续的1，跟网络中的子网掩码很像（子网掩码是从高位开始），有个比较高大上的说法叫做"低位hash掩码"。

Hashtable是利用取模运算散列定位到hash桶的，虽然通用，但是效率比这HashMap低。

这个方法也是HashMap的容量一定要是2的整数次幂的一个原因。length = capacity，length为2^n的话，h&(length-1)就相当于对length取模。同时(2^n - 1)这种数的所有bit为1的位都是连续的，这样进行 & 运算能够利用hash值中最低的n位中的所有位，也就是[0, 2^n - 1]所有值都能取到。& 运算的结果是这个hash桶在table数组的索引，因此也就能够利用table的所有空间。如果不是2^n，那么hash掩码中最低n位就不全为1，会有0出现，这样进行 & 运算后这个0对应的位永远是0，就不能利用这一位的值，造成hash值散列到table中时不够均匀，table中会有无法被利用的空间。比如length为15，是个奇数，(length-1)为偶数14，最后一位为0，进行&运算后一定是偶数，造成所有table中所有奇数下标的位置无法被利用，浪费15 >> 1 = 7个空间，基本浪费了一半。

/** * 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. */// HashMap自己的hash函数，是一个扰动函数，主要是为了避免hashCode方法设计的不够好导致hash冲突过多// indexFor方法只能利用h的最低的n位的信息，因此使用移位来让低位能够附带一些高位的信息，充分利用hashCode的所有位的信息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);}

为什么HashMap不直接使用hashCode，非要自己写个hash函数呢？

因为hashCode是个32bit数，存放到table数组中时，根据上面的table数组索引方法，可以知道只有最低n位（HashMap的容量为2^n）被利用到了，高位部分的信息都丢失了。假设直接使用hashCode，在节点很多，并且hashCode设计得比较好的情况下，低n位也会是随机且均匀分布的。但是在元素不太多、hashCode设计得很烂的情况下，低n位就不够随机均匀了，这让hash冲突变多，降低了各种方法的时间效率。

HashMap中的hash算法基本就是把hashCode的高位与低位进行异或运算，让低位能够夹带一些高位的信息，尽量利用hashCode本身所有位的信息，来让indexFor方法的结果尽量随机均匀。多次进行这种运算，hashCode本身的影响就减少了，这也降低了hashCode设计得太差导致的不良影响。

这种函数一般叫作扰动函数，就是为了让数值本身的二进制信息变乱，某些位能够夹带一部分别的位的信息，得到一个bit位分布尽量随机均匀的新值，减少后续的hash散列冲突。

如果是直接用%操作，并且除数尽量使用大的素数，就基本上能够利用hashCode的所有位了，让根据hash值散列到table数组时尽量均匀，这时候就不太依赖hash扰动函数了。Hashtable基本是就是这样做的（直接使用hashCode，中间多一个变符号操作），不过这样效率低，其他的一些使用length = 2^n特性的地方也会比HashMap慢不少。

六、扩容

jdk1.6的HashMap的扩容很简单，实现得很直接。两个步骤，先创建一个两倍长度的数组，然后把节点一个个重新散列定位一次。要说的都写注释了，其余的没什么单独好说的。

// table数组扩容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];    transfer(newTable); // 把旧数组上所有节点，重新移动到新数组上正确的地方    table = newTable;    threshold = (int)(newCapacity * loadFactor); // 重设阈值，注意这里有点问题。loadFactor可以大于1，newCapacity*loadFactor是个浮点数，                                                 // 它可能大于Integer.MAX_VALUE，此时强转后变为Integer.MAX_VALUE，造成后续再也无法扩容。1.7开始修复了这一点}// 基本思路是把旧数组的所有节点全都重新“添加”到新数组对应的hash桶中// 1.6的实现很简单、直接、直观，后续版本有改良的实现void transfer(Entry[] newTable) {    Entry[] src = table;    int newCapacity = newTable.length;    for (int j = 0; j < src.length; j++) {        Entry
    
      e = src[j];        if (e != null) {            src[j] = null;            // 这里是把原来的Entry链从头到尾再“put”到新数组里面            // jdk1.6的put是把新节点添加到Entry链的最前面，因此transfer执行后，还在同一条Entry链（只有两条可选，可以看下jdk1.8的注释，后面我也会说）上的节点的相对顺序会颠倒            // 举个例子（数字为hash值，非真实值），扩容transfer前，table[0] = 16 -> 32 -> 48 -> 64 -> 80 -> 96，            //     扩容新数组中变成两条了，一条是table[0] = 80 -> 48 -> 16，另一条是table[16] = 96 -> 64 -> 32            // 16, 48, 80（32, 64, 96）还在同一条上，但是它们的相对顺序颠倒了，HashMap的整体的迭代顺序当然也变了，当然本身它ye不保证迭代顺序            do {                Entry
     
       next = e.next;                int i = indexFor(e.hash, newCapacity); // 没有重新计hash值，只是重新计算索引                e.next = newTable[i];                newTable[i] = e;                e = next;            } while (e != null);        }    }}

七、常用方法

1、get

get实现比较简单比较好理解，两个步骤，先indexFor定位到hash桶 -> 再进行链表遍历查找。

public V get(Object key) {    if (key == null) // key == null 的情况        return getForNullKey();    int hash = hash(key.hashCode());    for (Entry
     
       e = table[indexFor(hash, table.length)];  e != null;  e = e.next) { // indexFor定位hash桶        Object k;        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) // 遍历链表查找            return e.value;    }    return null;}// 处理 key == null 的情况// 根据putForNullKey方法（后面说）可以知道，key == null的节点，一定放在index = 0的hash桶中，判断null要使用 "=="private V getForNullKey() {    for (Entry
      
        e = table[0]; e != null; e = e.next) {        if (e.key == null)            return e.value;    }    return null;}

这里专门说下get方法的一个疑问。那就是for循环中的这句代码：

1.6的：if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

后续版本也有：

1.7的：if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))

1.8的：if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))

这里一起说，后面说1.7，1.8时再贴一份。

1.6中已经在putForNullKey中先行处理了null，明确了到这里key不可能是null。那么1.6中为什么还要加上(k = e.key) == key？合理原因是用 == 能加快比较，比较奇葩的原因是，虽然equals(null)一般都是返回false，不排除有极个别的恶意的实现是返回true。

个人关注的疑问是这个： e.hash == hash 这句是否多余？

Java中equals和hashCode的

通常规定：==为true ---> equals为true，equals为true ---> hashCode相等，==为true ---> hashCode相等（具体看api docs中Object类的说明）。后面的一个判断 ((k = e.key) == key || key.equals(k)) 就是判断key和e.key是否equals（就是通常意义上的“相等”，null使用==，非null使用equals，已经说了这里的key不可能为null）。那么如果后面的条件返回true，则有 == 或者 equals必定有一个返回true。再按照上面的通常规定，可以知道hashCode也是一样的，运算得到的hash也一样，那么e.hash == hash就不用比较了一定是true。

这个e.hash == hash存在的比较合理的解释就是突出hashCode的作用，明确表示：

在HashMap（以及其他的HashXXX）中，Key的hash值（hash值是根据hashCode算出来的，这里也可以理解为hashCode）的优先于==和equals。HashXXX中在查找key是否”相等“时，先使用hash值（可以理解为hashCode）判断一次，hash值相等时，再才使用==或者equals判断。如果一开始比较hash值就不相等，那么就是认为是不“相等”的对象，不再去管 == 或者equals。如果hash值相等，但是equals/==判断为不等，这种也视为“不相等”。下面的demo可以展示这一点。

// jdk1.8，请使用1.8运行，1.8的hash函数比较简单，容易构造数据// 需要用调试器才看得出来在同一条Entry链上，请使用调试器public class TestHashCode {    public static void main(String[] args) {        Key k = new Key();        Map
     
       map = new HashMap<>();        map.put(k, "1");        k.i = 2; // 修改hashCode        map.put(k, "2"); // 现在put了两个key "equals 且 ==" 的K-V对，hashCode不一样，实际hash值        k.i = 16; // 修改hashCode        map.put(k, "16"); // 现在put了三个key "equals 且 ==" 的K-V对，并且第三个跟第一个在同一条Entry链（index = 0）上，hashCode不一样，实际hash值也不一样        System.err.println(map); // 现在这个HashMap有三个K-V对，它们的key都是 "equals 且 ==" 的 ，但是它们的hashCode各不同，算出来的hash值不一样，在HashMap中这"三个"key是不"相等"的        Key newK = new Key();        newK.i = 16;        map.put(newK, "new16");        System.err.println(map); // 又添加了一个，并且也在index = 0的Entry链上，它的hash值和第三个相等，但是equals判断不相等，所以在HashMap看来它跟第三个是不"相等"的        // 因为Key的toString是直接使用Object.toString()，会用到hashCode，因此打印出来的结果中，四个K-V的key看上去都是一样的    }    static class Key {        int i = 0;        public int hashCode() {            return i;        }    }}

虽然HashXXX中hashCode优先，但是平时还是不要用这一点，非常迷惑人。而在其他的大多数情况下，==和equals是优先于hashCode的，判断对象相等基本上都是直接使用 ==或者equals，根本不使用hashCode。所以大家还是要尽量遵守equals和hashCode的通常规定，不要写出奇怪的equals和hashCode方法，同时尽量避免修改已经放到HashXXX中的对象中会改变hashCode和equals结果的field。大多数情况，使用不变类，比如String、Integer等，充当key是一个很好的选择。

2、put方法

实现比较简单。四个步骤，先indexFor定位到hash桶 -> 再进行链表遍历查找，确定是否添加 -> 如果添加就添加在链表头 -> 扩容判断。要说的都写注释上面了。

public V put(K key, V value) {    if (key == null) // 处理 key == null 的情况        return putForNullKey(value);    int hash = hash(key.hashCode()); // indexFor定位hash桶    int i = indexFor(hash, table.length);    // 先确认是否添加了“相等”的key    for (Entry
     
       e = table[i]; e != null; e = e.next) {        Object k;        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // “相等”是指满足此条件，上面的hash方法中说了            V oldValue = e.value;            e.value = value;            e.recordAccess(this); // 此方法HashMap中是空方法，留给子类实现            return oldValue;        }    }    modCount++;    addEntry(hash, key, value, i); // 执行真正的添加操作    return null; // 新添加的key，没有旧的value，返回null}// 处理 key == null 的情况，总是把它放在index = 0的hash桶中private V putForNullKey(V value) {    // 先确认是否已经添加了null key    for (Entry
      
        e = table[0]; e != null; e = e.next) {        if (e.key == null) {            V oldValue = e.value;            e.value = value;            e.recordAccess(this);            return oldValue;        }    }    modCount++;    addEntry(0, null, value, 0); // 执行真正的添加操作    return null;}// 在Entry链的头部插入新的节点，并检查是否需要扩容void addEntry(int hash, K key, V value, int bucketIndex) {    Entry
       
         e = table[bucketIndex];    table[bucketIndex] = new Entry
        
         (hash, key, value, e); // 先把新的节点添加进去    if (size++ >= threshold) // 然后判断是否要扩容，在把size加1        resize(2 * table.length); // 把第(threshold + 1)个添加了再扩容为2倍大小（例如，默认构造的HashMap时，在执行put第13个key互不“相等”的K-V时扩容）}

下面简单画了个put的示意图，可以看下。

3、remove方法

两个步骤，先indexFor定位hash桶 -> 然后遍历链表，找到“相等的就删除”。

public V remove(Object key) {    Entry
    
      e = removeEntryForKey(key);    return (e == null ? null : e.value);}// 就是链表中节点的删除，很简单final Entry
     
       removeEntryForKey(Object key) {    int hash = (key == null) ? 0 : hash(key.hashCode()); // 计算hash值    int i = indexFor(hash, table.length); // 定位hash桶    Entry
      
        prev = table[i];    Entry
       
         e = prev;    while (e != null) { // 遍历链表寻找key“相等”的节点        Entry
        
          next = e.next;        Object k;        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {            modCount++;            size--;            // 修改指针，删除节点            if (prev == e)                table[i] = next;            else                prev.next = next;            e.recordRemoval(this); // 这个方法交给子类实现            return e;        }        prev = e;        e = next;    }    return e;}

4、其他的一些基本方法

都比较简单，也没什么好说的。

public int size() {    return size;}public boolean isEmpty() {    return size == 0;}public boolean containsKey(Object key) {    return getEntry(key) != null;}public void clear() {    modCount++;    Entry[] tab = table;    for (int i = 0; i < tab.length; i++)        tab[i] = null;    size = 0;}// 分null、非null两种情况判断，也很好理解public boolean containsValue(Object value) {    if (value == null)        return containsNullValue();    Entry[] tab = table;    for (int i = 0; i < tab.length ; i++)        for (Entry e = tab[i] ; e != null ; e = e.next)            if (value.equals(e.value))                return true;    return false;}// 处理null value的情况private boolean containsNullValue() {    Entry[] tab = table;    for (int i = 0; i < tab.length ; i++)        for (Entry e = tab[i] ; e != null ; e = e.next)            if (e.value == null)                return true;    return false;}public void putAll(Map
     m) {    int numKeysToBeAdded = m.size();    if (numKeysToBeAdded == 0)        return;    // 这里使用保守的策略，一点小小的优化完善    // 直观的策略(m.size() + size) >= threshold不一定准确，因为两个map中可能会存在许多K-V重叠，可能会白白地扩容一次    // numKeysToBeAdded <= threshold 时本身也只扩容一次，就把这次可能的扩容交给put去进行准确的判断    if (numKeysToBeAdded > threshold) {        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); // 加1是为了有预留空间，避免下一次put就立即扩容        if (targetCapacity > MAXIMUM_CAPACITY)            targetCapacity = MAXIMUM_CAPACITY;        int newCapacity = table.length;        while (newCapacity < targetCapacity)            newCapacity <<= 1;        if (newCapacity > table.length)            resize(newCapacity);    }    for (Iterator
    > i = m.entrySet().iterator(); i.hasNext(); ) {        Map.Entry
     e = i.next();        put(e.getKey(), e.getValue());    }}