HashMap源码摘要

发表于 | 分类于 | 阅读次数:
字数统计: 1,708 | 阅读时长 ≈ 7

本篇主要分析HashMap源码。

java.util包(Java7)下的HashMap是一个泛型容器，它的继承关系见代码：

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

此文章主要围绕本人阅读HashMap源码引出的问题来展开，HashMap没有实现Collection，属于一种Map容器。

构造与初始化

先来看主要的初始化代码：

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

initialCapacity就是初始化容量，loadFactor就是负载因子，默认是0.75，在后续要在本篇分析的代码中，用来计算threshold，至于init()的作用见本篇最后参考文献，该方法可以使构造初始化和反序列化的功能更规整。

和初始化相关的部分，有这么一个辅助方法：

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

其中Integer.highestOneBit()是将传入参数的二进制表示的最高位进行保留，其它位全部设为零，再返回，整个辅助方法的目的是产生一个大于等于number的最小2的幂次方的值，这个方法是为下面这个方法服务的：

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

这个方法用来计算threshold，在table == EMPTY_TABLE时，初始化一个table，Entry就是一般算法书中的Node，貌似Java8已经用Node代替Entry了。

从上面可知，在HashMap中table的大小设置为2的幂次方，这和算法书上推荐素数的策略不一样，使用2的幂次方和采用的hash()策略有很大关系，下面是生成hash()方法和生成table索引的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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);
    }
    /**
     * Returns index for hash code h.
     */
    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);
    }

h & (length-1)相当于h % length，但前者具有更高的效率，所以length最好是偶数，因为如果是奇数最后末位是0，通过除留取余法会很容易让两个key在table中处于相同的index，也就是碰撞冲突，而将table的大小设置为2的幂次方，一方面它是偶数，另一方面，它的产生也可以很容易就通过位运算来获得，提高了性能，而且扩容通常都是double一次(这是非常普遍的扩容策略)。当然，取2的幂次方仍然容易产生碰撞，所以要对原本的hash值扰动计算，进行再hash，扰动计算的细节见本篇最后参考文献中某问题下的回答。

以上就是本人对HashMap初始化内容的理解。

接受null键

HashMap是接受null键的，首先看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;
    }

当需要取以null为键的值的时候，首先判断size是否为0，如果size为0就直接返回null，不用做无谓的查找了。接着我们可以发现，以null为键的entry只存储在以table[0]值为表头的链表中(看来默认null % length = 0)，依次遍历这个链表直到键值 == null为止。

Put

下面分析招牌的put()，该方法内第一个for循环之前的内容在原理上前文已经分析过了。for循环后的代码如下：

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

由这段代码可以看出，两个实体entry(node)的hash值相同并且只要键值==，那么其实就不用计算equals()了，直接更新value，返回旧值；如果前面的条件不满足，就添加entry，代码如下：

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

addEntry()和createEntry()的区别在于，addEntry()要进行一次数组扩容的判断，如果需要扩容，此时bucketIndex需要重新计算以适应新的table.length，关于扩容的内容后续再进行具体分析，下面看看createEntry()代码：

1
2
3
4
5
6
7
8
9
10
11
12
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++;
    }
Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

这两段代码也非常简单，值得一提的是，后续添加的entry将成为table相关索引指向的链表的表头。

扩容

前述中，在addEntry()中进行(size >= threshold) && (null != table[bucketIndex])判断并为真的时候，需要resize()，下面是resize()的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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];
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(newTable, rehash);
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

这段代码也并不复杂，实现的关键是transfer(newTable, 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;
        }
    }
}

这段代码的构造和之前设计put()方法的思路是相似的，只不过这里需要被“put()”的是原本存在的entry，这个entry是通过遍历hash桶每一个索引关联的链表得到的。

小结

在本人看来，HashMap是空间换时间的算法，理想状态在O(1)进行操作。但通过上述分析也可以看出，如果碰撞较多，存在最坏的时间复杂度O(n)；因为每个键值的存储都依赖hash，但hash的生成和存储顺序并不一致，所以HashMap不具有顺序性；此外HashMap不是线程安全的。应对以上场景可以考虑LinkedHashMap以及ConcurrentHashMap。Java 8中HashMap的源码分析可以参考最后列举的文献，最大改动就是当碰撞较多后，链表会过长(8元素以上)，此时将链表转换为一棵红黑树。

参考文献