close

Mr.Muzi

一只很安静的monkey

Java Map 03 - HashMap

字数统计: 1.4k 阅读时长: 5 mins • 分类: 源码阅读 • 标签: JDK 1.7, Java集合

  关于 java.util.HashMap<K, V> 的部分笔记，HashMap是一个遍历顺序无序，不允许key重复的存储键值对映射的集合实现类。底层依赖了一个数组集合，数组中的每个元素维护了具有需要存储在相同下标位置的键值对实体链表结构。本文演示代码段的执行环境基于JDK版本1.7。

概述

  HashMap是Map接口的实现类，提供了接口声明的所有方法的具体实现。HashMap允许存储key为null、value为null的元素。HashMap可以被视为等同于散列表（hash table），但是不同的是，散列表是线程安全的，主要方法都被synchronized关键字做了修饰，而HashMap是非线程安全的。Hashmap不保证元素遍历的顺序。

  HashMap执行get()和put()操作时可以保证常量时间的性能开销，如果需要遍历map集合，时间开销与map数组容量和存储的键值对数量之和成比例。

  HashMap中有两个参数会影响map的操作性能：initial capacity和load factor。initial capacity决定了map集合中桶（键值对实体数组）的大小，而load factor决定了当桶填充到什么程度时会执行数组扩容处理。如果执行了扩容操作，那么需要将当前map集合的键值对实体重新计算hashcode值并分配在扩容后数组中的位置。默认的加载因子是0.75，这个值保证了map的操作性能可以在时间和空间利用方面达到一个理想的平衡。

  如果在向map集合中插入元素前可以估计出插入的元素数量，可以提前完成集合空间分配，避免在加入过程中频繁重新分配空间导致性能降低。

  Hashmap是一个非线程安全的实现类。所以如果需要在多线程环境中使用hashmap，需要付诸额外的操作来保证多线程环境下的线程安全特性。一个常用的执行方式如下：

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

  HashMap同样支持快速失败检查，但是并不保证可以一定捕捉到快速失败检查。

  HashMap底层数据结构如图1所示：

图 - 1
 

 

继承关系

1
2
3
4
// HashMap<E>
--java.lang.Object
  --java.util.AbstractMap<K,V>
    --java.util.HashMap<K,V>

 

实现接口

类名 实现接口
HashMap<E> Serializable, Cloneable,Map<K,V>

 

HashMap

Constructor Summary

public HashMap(int initialCapacity, float loadFactor)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    threshold = initialCapacity;
    init();
}

  初始化一个空HashMap集合，集合的初始容量和加载因子由initialCapacity和loadFactor确认。

  第2 ~ 6行代码检查initialCapacity参数是否有效并确定最后的initialCapacity值，initialCapacity的最大值是MAXIMUM_CAPACITY（1<< 30或者$2^{30}$)。第7 ~ 9行代码则用来检查loadFactor的有效性。

  最后会调用一个init()方法。该方法在HashMap中是个方法体为空的方法，主要是给子类调用的，可以让子类在集合创建后，插入元素前执行一些想要的操作。

public HashMap(int initialCapacity)

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

  初始化一个空HashMap集合，集合的初始容量由initialCapacity和确认，加载因子默认为0.75。调用构造器方法HashMap(int initialCapacity, float loadFactor)完成初始化操作。

public HashMap()

1
2
3
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

  初始化一个空HashMap集合，集合的初始容量默认为16，加载因子默认为0.75。调用构造器方法HashMap(int initialCapacity, float loadFactor)完成初始化操作。

ublic HashMap(Map<? extends K, ? extends V> m)

1
2
3
4
5
6
7
public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);

    putAllForCreate(m);
}

  初始化一个空HashMap集合，并将m中的键值对保存到初始化的map中。在初始化过程中，集合的容量大小由m存储的键值对数量决定，保证空map集合可以将m中的键值对全部存储下来，且默认加载因子是0.75。初始化完成后通过inflateTable(int toSize)方法完成map集合底层存储数据结构的初始化操作。最后通过调用方法putAllForCreate(Map<? extends K, ? extends V> m)将m集合中的键值对保存到初始化的集合中。

部分方法

void init()

1
2
void init() {
}

  空方法，留给子类发挥。

private void inflateTable(int toSize)

1
2
3
4
5
6
7
8
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

  完成map底层存储结构初始化。首先根据传入的toSize寻找一个大于等于toSize的最小2次幂结果。第5行代码确定最终的初始空间容量并在第6行代码中初始化一个存储空间结构 — Entry[] table。最后根据容量初始化一个散列掩码（hashing mask value）以完成底层存储结构初始化过程。

private static int roundUpToPowerOf2(int number)

1
2
3
4
5
6
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
        ? MAXIMUM_CAPACITY
        : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

  计算求得一个大于等于number的最小2次幂结果。如果number比最大容量还大，那么就返回最大容量；如果number = 1，那么直接返回1，否则返回大于number的最小2次幂结果。在计算过程：

    

中，number -1 是为了保证当number自身为2次幂时可以取到自身而不是大于自身的最小2次幂结果。因为方法实现的返回大于等于number的最小2次幂结果。所以number -1保证了这个条件，然后计算(number - 1) << 1)过程，并通过Integer.highestOneBit()返回一个满足条件的数字。

final boolean initHashSeedAsNeeded(int capacity)

1
2
3
4
5
6
7
8
9
10
final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
        (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0;
    }
    return switching;
}

  初始化一个散列掩码（hashing mask value）。只有在实际需要的时候才会初始化这个值，也就是延迟初始化。在初始化时hashSeed的默认值为0。在我们尚未给hashmap赋值时，sun.misc.VM.isBooted()得到的是true，ALTERNATIVE_HASHING_THRESHOLD的值为Integer.MAX_VALUE = 2147483647 [0x7fffffff]。所以useAltHashing的值为false。第5行代码执行得到false。

  该方法用来计算一个hashSeed，hashSeed不为0的时候，对 String 类型的key 采用sun.misc.Hashing.stringHash32的 hash算法；对非 String 类型的 key，多一次和hashSeed的异或，这样可以一定程度上减少碰撞的概率。但是由于在产生hashSeed的过程中调用了Romdum.nextInt()方法，而该方法内部使用的AtomicLong，其操作类型是CAS(Compare And Swap)，所以多线程环境中性能无法满足要求，所以在JDK 7u40之后被移除，且在JDK 8中也不再使用该字段。

private void putAllForCreate(Map<? extends K, ? extends V> m)

1
2
3
4
private void putAllForCreate(Map<? extends K, ? extends V> m) {
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        putForCreate(e.getKey(), e.getValue());
}

  将m集合中的键值对保存到当前map集合中。调用的是putForCreate(K key, V value)方法。

private void putForCreate(K key, V value)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void putForCreate(K key, V value) {
    int hash = null == key ? 0 : hash(key);
    int i = indexFor(hash, table.length);

    /**
     * Look for preexisting entry for key.  This will never happen for
     * clone or deserialize.  It will only happen for construction if the
     * input Map is a sorted map whose ordering is inconsistent w/ equals.
     */
    for (Entry<K,V> 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);
}

  将key-value键值对映射存储到当前map集合中。在构造器和伪构造器方法（clone，readObject）中替换put方法完成键值对插入操作。该方法不会对map集合做扩容处理，检查修改状态等。而且该方法调用createEntry，而不是addEntry完成操作。

  第2行代码根据key完成hashCode值计算。之后根据indexFor()方法返回该hashcode在散列表中的下标位置。

  第10 ~ 17行代码遍历当前map集合，如果当前map集合中存在和参数key相同的键值对映射，那么就替换键值对的valu值，否则调用createEntry(int hash, K key, V value, int bucketIndex)将键值对加入到当前map集合中。

final int hash(Object k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

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

  一种补充的计算hashcode的方法。计算得到的随机hashSeed，来降低冲突发生的几率，如果hashSeed不等于0，且key是String字符串，那么通过方法sun.misc.Hashing.stringHash32()完成hashcode计算。否则

  这个方法的目的是对key的hashcode进行扰动计算，防止不同hashcode的高位不同但低位相同导致的hash冲突，尽量做到key的hashcode任何一位的变化都能对最终结果产生影响。

static int indexFor(int h, int length)

1
2
3
4
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

  将hashcode转换成散列表中的下标。利用&做取模运算得到hashcode在散列表中的下标。

void createEntry(int hash, K key, V value, int bucketIndex)

1
2
3
4
5
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

  创建一个键值对映射。table[buckedIndex]维护的是一个Entry结构的链表，得到这个链表结构，同时第3行代码会在第bucketIndex位置上创建一个新的对象实体，该对象实体的next节点是当前Entry结构的首部元素节点，最后同步size值，该值维护了当前map集合中存储的键值对数量。操作示意图如图2所示：

图 - 2
 

  Alpha为createEntry方法执行前map集合的状态，Bravo为createEntry方法执行后的场景，如果根据key计算hashcode得到数组下标bucketIndex位置尚未存储元素，那么新创建的键值对实体会是该下标位置的第一个元素，如图2Bravo里的键值对“A11=123”。如果数组下标bucketIndex位置已经存储了元素，那么第2代码和第三行代码中的new Entry<>(hash, key, value, e)部分执行的是Bravo阶段中步骤（1）的结果，新创建了一个键值对实体“B11=12”，且将键值对“B11=12”的next节点指向了键值对实体”B12=123“。第3行代码执行完后，Bravo阶段中步骤（2）也就执行完成了，新创建的键值对实体“B11=12”成为下标位置N-3处的链表结构的首部节点。

public V put(K key, V value)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    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);
    return null;
}

  将传入的key-value映射保存到当前map集合中。如果当前map集合中已经存在了key对应的键值对映射，那么原有映射的value值会被传入的value替换。

  如果当前map集合为空，那么调用inflateTable(int toSize)方法完成map底层数组初始化操作。

  如果key为null，那么调用putForNullKey(V value)加入一个key为null的键值对映射。

  计算key的hashcode值和在底层数组中的下标位置。取得该下标位置的映射实体对象，如果对象为空，那么调用addEntry(int hash, K key, V value, int bucketIndex)完成键值对添加。否则执行第9 ~ 17行代码替换已存在键值对映射的value值并返回被替换的值。因为put操作属于结构化修改，所以更新modCount的值。

private V putForNullKey(V value)

1
2
3
4
5
6
7
8
9
10
11
12
13
private V putForNullKey(V 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;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

  向当前map集合中存储一个key为null的键值对映射。由于key为null时其hashcode为0，所以其在数组中的下标为0。所以取得下标为0的键值对实体，如果实体存在，直接替换下标为0的实体的value值，并返回被替换的值。否则调用addEntry(int hash, K key, V value, int bucketIndex)完成键值对添加。

void addEntry(int hash, K key, V value, int bucketIndex)

1
2
3
4
5
6
7
8
9
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

  向当前map集合中加入一个键值对映射。

  如果当前map存储的键值对数量达到了扩容阈值限制(capacity*load factor)，且计算得到的bucketIndex下标位置处已经被占用，那么首先执行扩容处理。扩容规则是按照当前容量的两倍进行扩容。扩容完成后重新计算key的hashcode值和在数组中的下标位置。

  通过createEntry(int hash, K key, V value, int bucketIndex)完成键值对的创建和保存。

public void putAll(Map<? extends K, ? extends V> m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public void putAll(Map<? extends K, ? extends V> m) {
    int numKeysToBeAdded = m.size();
    if (numKeysToBeAdded == 0)
        return;

    if (table == EMPTY_TABLE) {
        inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
    }

    /*
     * Expand the map if the map if the number of mappings to be added
     * is greater than or equal to threshold.  This is conservative; the
     * obvious condition is (m.size() + size) >= threshold, but this
     * condition could result in a map with twice the appropriate capacity,
     * if the keys to be added overlap with the keys already in this map.
     * By using the conservative calculation, we subject ourself
     * to at most one extra resize.
     */
    if (numKeysToBeAdded > threshold) {
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
        if (targetCapacity > MAXIMUM_CAPACITY)
            targetCapacity = MAXIMUM_CAPACITY;
        int newCapacity = table.length;
        while (newCapacity < targetCapacity)
            newCapacity <<= 1;
        if (newCapacity > table.length)
            resize(newCapacity);
    }

    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
}

  将集合m中的所有键值对映射都存储到当前map集合中。

  如果m集合为空，那么不做任何处理直接返回。如果当前map集合为空，那么先完成初始化操作。如果存储m集合中的键值对需要的空间超过了当前map集合的扩容限制阈值threshold，那么第20行代码会计算存储m集合需要的空间大小，第21 ~ 22行代码计算最终确定的目标空间大小，第23 ~ 25行代码以当前map空间的两倍逐次扩容直至满足目标空间大小的要求。第26 ~ 27行代码如果需要的空间超过了当前map集合的数组物理空间大小，那么就执行扩容处理。

  扩容完成后，遍历集合m，将m中的每个键值对映射加入到当前map集合中。

void resize(int newCapacity)

1
2
3
4
5
6
7
8
9
10
11
12
13
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, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

  扩容当前map集合。扩容之后重新计算集合中已有键值对映射的hashcode和下标值并完成键值对存储位置的更新。如果当前map集合的容量已经达到了最大容量限制（$2^{30} $），那么不再扩容，并返回扩容限制阈值。

  初始化一个新的数组，调用transfer(Entry[] newTable, boolean rehash)将当前map集合中的键值对都迁移到扩容后的新数组中，最后计算更新扩容限制阈值threshold。

void transfer(Entry[] newTable, boolean rehash)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

  将当前map集合中的键值对映射从旧数组迁移到新数组中。

  遍历旧数组中的每个键值对实体，如果需要重新计算hashcode值，那么调用hash(Object k)重新计算hashcode值。之后重新计算每个键值对在新数组中的下标位置。第10行代码会将每个键值对的后继节点统一置为null，表示每个链表只会有一个元素。第11行代码将键值对实体存储到新数组中对应下标位置上。操作过程如图3所示：

图 - 3
 

  遍历旧数组table的每个键值对映射实体，首先得到某个下标位置链表结构的首部节点和首部节点的后继节点，并决定是否需要重新计算hashcode值。之后根据hashcode和新数组容量计算出当前节点在新数组的下标位置，这里有两种情况需要考虑，一种是新数组的下标位置为空，尚未存储元素，另外一种是新数组的下标位置已经有键值对实体存储了。

  如果是前一种情况，第10行代码执行后，在图3中是步骤（1）的情况，第11行代码执行后新数组下标位置的链表首部元素就是当前节点，即步骤（2）。之后将next指针指示的节点赋值给当前节点循环计算直至到达链表尾部。

  如果是后一种情况，第10行代码执行过程中，首先经历步骤（4.1），该过程会将现有新数组下标位置的首部元素指针从数组上断开，继而经历步骤（4.2），将当前遍历节点的后继指针指向链表首部元素。第11行代码执行后会经历步骤（5），当前元素会被加入到新数组下标位置链表的首部。之后将next指针指向的元素赋值给当前遍历节点循环遍历直至链表遍历结束。

public V remove(Object key)

1
2
3
4
public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

  删除当前map集合中和入参key匹配的键值对映射，并返回被删除的value值。底层调用removeEntryForKey(Object key)方法完成操作。

final Entry<K,V> removeEntryForKey(Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> 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;
}

  删除当前map集合中和入参key匹配的键值对映射，并返回被删除的键值对实体。如果当前map集合为空，那么直接返回null。

  根据key计算出key对应的hashcode和在数组中的下标值。实际流程如图4所示：

图 - 4
 

  第5 ~ 9行代码计算当前入参key的hashcode值以及根据hashcode值计算匹配key的键值对在数组中的下标位置。取得该下标处链表结构的首部节点，开始遍历，找到hashcode值一致且key相等节点。如果该节点正好是链表的第一个节点，那么执行第17 ~ 18行代码后图3中键值对实体“B12=123”会被移除链表并返回。如果该节点是链表中的某个节点，那么执行第17 ~ 18行代码后图3中键值对实体“B13=123”会被移除链表并返回。

  如果没有找到匹配的key，那么返回null。

final Entry<K,V> removeMapping(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
final Entry<K,V> removeMapping(Object o) {
    if (size == 0 || !(o instanceof Map.Entry))
        return null;

    Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
    Object key = entry.getKey();
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        if (e.hash == hash && e.equals(entry)) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}

  从当前集合中删除实体o（o被期望为一个键值对实体对象）。第5行代码将对象o转成了一个键值对实体，并计算出该键值对key的hashcode值以及其在当前map集合中的下标位置，然后根据下标找到该下标位置处的链表结构，找到与o的key匹配的键值对实体（比较整个entry实体的hashcode值），并删除。最后返回被删除的键值对实体对象。

public void clear()

1
2
3
4
5
public void clear() {
    modCount++;
    Arrays.fill(table, null);
    size = 0;
}

  清空整个数组实现清空map集合的功能。

public V get(Object key)

1
2
3
4
5
6
7
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

  获取map集合中key对应的value值，如果没有对应映射，那么返回null。如果key为null，那么调用getForNullKey()方法得到null对应的键值对映射的value信息。否则调用getEntry(Object key)完成查找。最后返回结果给方法调用方。

private V getForNullKey()

1
2
3
4
5
6
7
8
9
10
private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

  map集合中key为null的元素只有一个，且其hashcode为0，所以在散列表中的下标为0。所以第5 ~ 8行代码会直接取下标为0的元素实体，并返回。

public boolean containsKey(Object key)

1
2
3
public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

  判断当前map集合中是否含有key对应的键值对映射，如果有，那么返回true。否则返回false。

public boolean containsValue(Object value)

1
2
3
4
5
6
7
8
9
10
11
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;
}

  判断当前map集合中是否含有入参value匹配的键值对实体。如果有返回true，否则返回false。

  如果value为null，那么调用containsNullValue()方法完成操作并返回结果。否则第6 ~ 10行代码中外层遍历底层数组中的每个位置的链表集合，里层遍历每个链表集合中的每个键值对实体，检查是否有匹配value的键值对实体对象，如果有返回true，否则返回false。

private boolean containsNullValue()

1
2
3
4
5
6
7
8
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;
}

  判断当前map集合中是否含有value为null的键值对实体。如果有返回true，否则返回false。

  第3 ~ 6行代码中外层遍历底层数组中的每个位置的链表集合，里层遍历每个链表集合中的每个键值对实体，检查是否有value为null的键值对实体对象，如果有返回true，否则返回false。

final Entry<K,V> getEntry(Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

  返回key对应的键值对映射对象实体。如果当前map集合为空，那么直接返回null。调用hash(Object k)计算key的hashcode。第7行代码根据计算得到的hashcode值得到底层数组中对应下标位置处的链表集合，取出存储的value值并返回。

public int size()

1
2
3
public int size() {
    return size;
}

  返回当前map集合中存储的键值对数量。

public boolean isEmpty()

1
2
3
public boolean isEmpty() {
    return size == 0;
}

  判断当前map集合是否为空。

public Object clone()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Object clone() {
    HashMap<K,V> result = null;
    try {
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        // assert false;
    }
    if (result.table != EMPTY_TABLE) {
        result.inflateTable(Math.min(
            (int) Math.min(
                size * Math.min(1 / loadFactor, 4.0f),
                // we have limits...
                HashMap.MAXIMUM_CAPACITY),
            table.length));
    }
    result.entrySet = null;
    result.modCount = 0;
    result.size = 0;
    result.init();
    result.putAllForCreate(this);

    return result;
}

  克隆复制一个当前map集合副本并返回。该副本是当前map集合的浅度复制对象。

Iterator<K> newKeyIterator()

1
2
3
4
5
6
7
8
9
Iterator<K> newKeyIterator()   {
    return new KeyIterator();
}

private final class KeyIterator extends HashIterator<K> {
    public K next() {
        return nextEntry().getKey();
    }
}

  返回一个基于当前map集合的key的迭代器。

Iterator<V> newValueIterator()

1
2
3
4
5
6
7
8
9
Iterator<V> newValueIterator()   {
    return new ValueIterator();
}

private final class ValueIterator extends HashIterator<V> {
    public V next() {
        return nextEntry().value;
    }
}

  返回一个基于当前map集合的value的迭代器。

Iterator<Map.Entry<K,V>> newEntryIterator()

1
2
3
4
5
6
7
8
9
Iterator<Map.Entry<K,V>> newEntryIterator()   {
    return new EntryIterator();
}

private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
    public Map.Entry<K,V> next() {
        return nextEntry();
    }
}

  返回一个基于当前map集合的键值对的迭代器。

public Set<K> keySet()

1
2
3
4
public Set<K> keySet() {
    Set<K> ks = keySet;
    return (ks != null ? ks : (keySet = new KeySet()));
}

  返回当前map集合包含的所有key的一个Set形式集合。对这个集合做的修改会同步出现在当前map集合中，反之亦然。KeySet的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private final class KeySet extends AbstractSet<K> {
    public Iterator<K> iterator() {
        return newKeyIterator();
    }
    public int size() {
        return size;
    }
    public boolean contains(Object o) {
        return containsKey(o);
    }
    public boolean remove(Object o) {
        return HashMap.this.removeEntryForKey(o) != null;
    }
    public void clear() {
        HashMap.this.clear();
    }
}

public Collection<V> values()

1
2
3
4
public Collection<V> values() {
    Collection<V> vs = values;
    return (vs != null ? vs : (values = new Values()));
}

  返回当前map集合中包含的所有value的一个Collection形式集合。对这个集合做的修改会同步出现在当前map集合中，反之亦然。Values的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private final class Values extends AbstractCollection<V> {
    public Iterator<V> iterator() {
        return newValueIterator();
    }
    public int size() {
        return size;
    }
    public boolean contains(Object o) {
        return containsValue(o);
    }
    public void clear() {
        HashMap.this.clear();
    }
}

public Set<Map.Entry<K,V>> entrySet()

1
2
3
4
5
6
7
8
public Set<Map.Entry<K,V>> entrySet() {
    return entrySet0();
}

private Set<Map.Entry<K,V>> entrySet0() {
    Set<Map.Entry<K,V>> es = entrySet;
    return es != null ? es : (entrySet = new EntrySet());
}

  返回当前map集合中包含的所有键值对实体的Set表示形式。对这个集合做的修改会同步出现在当前map集合中，反之亦然。EntrySet的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
    public boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<K,V> e = (Map.Entry<K,V>) o;
        Entry<K,V> candidate = getEntry(e.getKey());
        return candidate != null && candidate.equals(e);
    }
    public boolean remove(Object o) {
        return removeMapping(o) != null;
    }
    public int size() {
        return size;
    }
    public void clear() {
        HashMap.this.clear();
    }
}

private void writeObject(java.io.ObjectOutputStream s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void writeObject(java.io.ObjectOutputStream s)
        throws IOException {
    // Write out the threshold, loadfactor, and any hidden stuff
    s.defaultWriteObject();

    // Write out number of buckets
    if (table==EMPTY_TABLE) {
        s.writeInt(roundUpToPowerOf2(threshold));
    } else {
        s.writeInt(table.length);
    }

    // Write out size (number of Mappings)
    s.writeInt(size);

    // Write out keys and values (alternating)
    if (size > 0) {
        for(Map.Entry<K,V> e : entrySet0()) {
            s.writeObject(e.getKey());
            s.writeObject(e.getValue());
        }
    }
}

  hashmap自定义序列化操作。

private void readObject(java.io.ObjectInputStream s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
private void readObject(java.io.ObjectInputStream s)
         throws IOException, ClassNotFoundException {
    // Read in the threshold (ignored), loadfactor, and any hidden stuff
    s.defaultReadObject();
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new InvalidObjectException("Illegal load factor: " +
                                         loadFactor);
    }

    // set other fields that need values
    table = (Entry<K,V>[]) EMPTY_TABLE;

    // Read in number of buckets
    s.readInt(); // ignored.

    // Read number of mappings
    int mappings = s.readInt();
    if (mappings < 0)
        throw new InvalidObjectException("Illegal mappings count: " +
                                         mappings);

    // capacity chosen by number of mappings and desired load (if >= 0.25)
    int capacity = (int) Math.min(
        mappings * Math.min(1 / loadFactor, 4.0f),
        // we have limits...
        HashMap.MAXIMUM_CAPACITY);

    // allocate the bucket array;
    if (mappings > 0) {
        inflateTable(capacity);
    } else {
        threshold = capacity;
    }

    init();  // Give subclass a chance to do its thing.

    // Read the keys and values, and put the mappings in the HashMap
    for (int i = 0; i < mappings; i++) {
        K key = (K) s.readObject();
        V value = (V) s.readObject();
        putForCreate(key, value);
    }
}

  hashmap自定义反序列操作。

int capacity()

1
int   capacity()     { return table.length; }

float loadFactor()

1
float loadFactor()   { return loadFactor;   }

 

Entry<K,V>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> 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 Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }

    public final String toString() {
        return getKey() + "=" + getValue();
    }

    /**
     * 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) {
    }

    /**
     * This method is invoked whenever the entry is
     * removed from the table.
     */
    void recordRemoval(HashMap<K,V> m) {
    }
}

  Entry是HashMap集合的内部类，实现了Map.Entry<K,V>接口。实际上map集合内部的存储结构就是一个Entry形式的数组，数组中的每个元素都是一个Entry实体。

  Entry中包含了四个字段：value（map集合中键值对的值内容），key（map集合中键值对的键内容），next（当前entry节点的下一个节点）和hash（map集合中键值对的键的hashcode值）。

  实体自身的hashcode计算方式是将当前实体的key的hashcode和value的hashcode求异或运算得到结果。

  比较两个实体是否相等，首先判断两个实体的类型是否一致，其次分别判断两个实体的key和value是否都相等。

 

HashIterator<E>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;        // next entry to return
    int expectedModCount;   // For fast-fail
    int index;              // current slot
    Entry<K,V> current;     // current entry

    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();

        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
        current = e;
        return e;
    }

    public void remove() {
        if (current == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Object k = current.key;
        current = null;
        HashMap.this.removeEntryForKey(k);
        expectedModCount = modCount;
    }
}

  HashIterator是基于当前map集合的键值对实体的一个迭代器实现。构造函数HashIterator()会定位到当前map集合中第一个不为null的键值对实体上。

  根据next是否为null来判断是否可以继续向后遍历。

  在nextEntry()方法中，执行逻辑如图5所示：

图 - 5
 

  在完成HashIterator初始化完成之后，next指针会指向当前数组中第一个非空的键值对实体对象。如果当前指向处理的键值对实体的后继节点为空，那么就继续向后遍历数组，直到找到下一个非空的键值对实体链表结构并将next指针指向该链表的首部节点。得到当前处理的键值对实体对象节点并返回该对象。

  借助remove()方法完成删除当前节点的操作。取得当前键值对实体对象中的key值信息，调用HashMap的removeEntryForKey()方法将该节点删除，同时更新expectedModCount。

 

涉及基础知识点

  1. 为什么要把数组的Size设置为2的N次方

    1. indexFor利用&做取模运算计算散列表下标值，a & b中要求b的二进制位全部由1构成，所以需要散列表长度为$ 2^n $ 。此外，利用位操作实现取模运算比算术取模运算效率非常好，所以这么做可以提高运行效率；
    2. 不同的hash值发生碰撞的概率相对来说比较小，可以让键值对实体在数组中均匀分布；

  2. 加载因子对map集合查找效率的影响

    1. 加载因子越大，填满的数组元素越多，分配的内存空间空闲小，链表长度增加，查找效率变低；
    2. 加载因子越小，填满的数组元素越少，分配的内存空间空闲多，链表长度减少，查找效率变高；

    因为在addEntry()方法中，由两个因素决定是否需要进行扩容操作：(size >= threshold) 和 (null != table[bucketIndex])。即使(null != table[bucketIndex])条件满足了，由于扩容限制阈值太大导致前一个条件size >= threshold一直无法满足，因此无法执行扩容操作，只能在链表首部不停的追加元素，导致链表长度变大。

 

参考文献

  1. ChiuCheng. 深入理解HashMap(二): 关键源码逐行分析之hash算法 [E]
  2. csfreebird. Java HashMap 分析之三:放入元素 [E]
  3. Yikun. Java HashMap工作原理及实现 [E]
  4. ImportNew. HashMap的工作原理 [E]
  5. Liujiacai. Java HashMap 源码解析 [E]
  6. Stack Overflow. Understanding strange Java hash function [E]
  7. Stack Overflow. Can anybody explain how java design HashMap’s hash() function? [E]
  8. Hollis. 全网把Map中的hash()分析的最透彻的文章，别无二家 [E]
  9. Carson_Ho. Java：这是一份详细&全面的HashMap 1.7 源码分析 [E]
  10. zhihu. JDK 源码中 HashMap 的 hash 方法原理是什么？ [E]
  11. miaoLoveCode. Java中的HashMap [E]

 
 
 
 

------------- End of this article, thanks! -------------
 


  版权声明：本文由N.C.Lee创作和发表，采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可，转载请注明作者及出处。
  本文作者为 N.C.Lee
  本文标题为 Java Map 03 - HashMap
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-HashMap.html