Java基础
HashMap, JDK7

HashMap源码分析JDK7

哈希算法

  • 直接定址法：直接以关键字k或者k加上某个常数（k+c）作为哈希地址。

  • 数字分析法：提取关键字中取值比较均匀的数字作为哈希地址。

  • 除留余数法：用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址。

  • 分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。

  • 平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址。

  • 伪随机数法：采用一个伪随机数当作哈希函数

解决碰撞算法

衡量一个哈希函数的好坏的重要指标就是发生碰撞的概率以及发生碰撞的解决方案。任何哈希函数基本都无法彻底避免碰撞，常见的解决碰撞的方法有以下几种：

  • 开放定址法：开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

  • 链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。

  • 再哈希法：当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。

  • 建立公共溢出区：将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。

数据存储结构

HashMap是由数组和链表来实现的对数据的存储，采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。

1
2
3
4
5
6
7
8
9
10
11
12
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    Entry(int h, K k, V v, Entry<K,V> n) { // 头插法的体现
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

hashSeed问题

对key的hashCode进行了二次hash，即hash扰动，以获得更好的散列值。这里做二次hash的目的是避免自定义对象的hashCode方法，算出来的hashCode离散性比较差，从而导致某些链表特别长，而有些特别短，从而导致性能差。

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

上面用到的hashSeed值在HashMap初始化时默认为0，根据源码来看hashSeed可能会在初始化table时通过inflateTable中调用的initHashSeedAsNeeded方法被重新设置。currentAltHashing显然为false，useAltHashing通过下面分析可知其值为也为false，故initHashSeedAsNeeded始终返回false，而hashSeed值始终得不到重新设置，所以其始终为0。

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

sun.misc.VM.isBooted()的源码如下，但是实际通过调用发现其返回值为true。

1
2
3
4
private static volatile boolean booted = false;
public static boolean isBooted() {
    return booted;
}

而关于Holder.ALTERNATIVE_HASHING_THRESHOLD，如下所示该值取决于altThreshold的值，实际调试发现该值其实为null，故Holder.ALTERNATIVE_HASHING_THRESHOLD为Integer.MAX_VALUE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static class Holder {
    static final int ALTERNATIVE_HASHING_THRESHOLD;
    static {
        String altThreshold = java.security.AccessController.doPrivileged(new sun.security.action.GetPropertyAction("jdk.map.althashing.threshold")); // null
        int threshold;
        try {
            threshold = (null != altThreshold) ? Integer.parseInt(altThreshold) : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
            if (threshold == -1) {
                threshold = Integer.MAX_VALUE;
            }
            if (threshold < 0) {
                throw new IllegalArgumentException("value must be positive integer.");
            }
        } catch(IllegalArgumentException failed) {
            throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
        }
        ALTERNATIVE_HASHING_THRESHOLD = threshold;
    }
}

构造方法

HashMap的前三个构造方法仅仅是给负载系数loadFactor和数组容量阈值threshold赋值，并不会对数组table进行填充初始化等。HashMap的填充是在真正使用时才会通过inflateTable方法进行填充。如HashMap(Map<? extends K, ? extends V> m)、put(K key, V value)、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
33
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量16
static final int MAXIMUM_CAPACITY = 1 << 30;	// 最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;	// 加载因子
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // 用于存储链表数据
transient int size;	// 存储KV的数量, 所有链表元素总和
int threshold; // threshold=capacity*loadFactor，size大于threshold时会执行resize操作
final float loadFactor; // 装载因子，用来衡量HashMap满的程度
transient int modCount;	// 记录当前集合被修改的次数: 添加，删除，为了实现快速失败的机制

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();
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
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);
}

表的初始化

inflateTable方法是为了初始化数组table，当通过构造方法创建HashMap时设置了initialCapacity，但是实际上创建数组时，使用的并不是我们设置initialCapacity来创建的数组的长度，而是通过roundUpToPowerOf2方法对数组容量进行了优化，不管怎么设置initialCapacity大小，数组容量始终是2的幂，且是大于等于threshold的最近的2的幂。也为后续通过indexFor方法为hash值取模起到帮助。

highestOneBit方法是为了获取二进制数据的最高位，低位全部置0，在调用highestOneBit方法之所以传入的是(number - 1) << 1而不是直接传入number << 1，因为若number本身就是2的幂，就会造成将数组容量扩大一倍，若number = 16期望返回的是16，若传入number << 1将放回32.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private void inflateTable(int toSize) {
    int capacity = roundUpToPowerOf2(toSize);
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
// 获取大于等于number的最接近的2的幂的数作为数组的容量
private static int roundUpToPowerOf2(int number) {
    return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
// 获取数据二进制的最高位，低位全部置0
public static int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

添加方法

当存在相同的key且hash相同时，是替换已有的值，并将旧值返回，而不知直接插入到链表中。之所以即要判断散列值也要判断key，是因为不同的输入可能会散列成相同的输出。根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。同一散列函数计算出的散列值相同的现象叫做碰撞。

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) // 若key为空，将其插入到table[0]中
        return putForNullKey(value);
    int hash = hash(key); // 计算hash值
    int i = indexFor(hash, table.length); // 通过hash值和数组长度取模得到数组下标
    for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
        Object k; // 若链表存在，在遍历链表，若存在key相等的则替换value
        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); // 若数组下标对应的链表为空或key不存在，则新建链表或用头插法插入数据
    return null;
}

仅当 b = 2^n 时位运算才可以转换成取模运算，a % b = a & (b - 1) 。故HashMap才将初始长度设置为 16，且扩容只能是以 2 的倍数扩容。由上面可知数组容量始终是2的幂，故可通过h & (length-1)对hash值取余，从而获取对应的table数组的下标。使用位运算代替取模运算，除了性能之外，还有一个好处就是可以很好的解决负数的问题。

1
2
3
static int indexFor(int h, int length) { // 取模运算得到数组下标
    return h & (length-1);
}

通过put方法中key为空的情况调用的putForNullKey()方法可知，HashMap中key为空的数据始终是存储到数组table下标为0的链表中。故table[0]的链表长度适中是1.

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); // key为空的元素只能有一个
    return null;
}

table数组的长度并不是初始化后就固定不变了，将链表变得非常长后效率将变得低下，故当元素个数大于等于threshold = capacity * loadFactor时且该数组下标对应的链表不为空，就对数组进行扩容。且是按两倍进行扩容。并将数据从旧的table中拷贝到新的table中。在createEntry仅仅只有两行代码，实现了数据在链表中的头插法插入。

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
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; // 重新计算一次hash
        bucketIndex = indexFor(hash, table.length); // 获取新的数组下标
    }
    createEntry(hash, key, value, bucketIndex); // 使用头插法插入数据
}
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) { // 若数组长度已经是最大容量了，不需要再扩容了
        threshold = Integer.MAX_VALUE; // 则将threshold设置为最大值
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
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++;
}

由于newCapacity容量变化了，故indexFor返回的数据下标将可能变化或变成另一个固定的值，故旧的table中同一个链表的数据拷贝到新的table中可能会拆分成两个链表，且将旧表中的数据使用的头插法进行拷贝到新的table中的链表中，链表中的数据将被反序。而不是直接将数组的前N个元素对拷贝到新的数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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) { // 实际传入的false，不需要重新计算hash
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 重新计算数组下标，新下标要么不变，要么等于原来的下标加上旧的数组长度
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i]; // 头插法
            newTable[i] = e;
            e = next;
        }
    }
}

在1.8之前，新插入的元素都是放在了链表的头部位置，但是这种操作在高并发的环境下容易导致死锁，所以1.8之后，新插入的元素都放在了链表的尾部。

获取方法

首先计算hash值通过indexFor()方法得到该key在table中的存储位置，遍历链表，在获取数据时不仅判断了hash值是否相等，还判断了key是否相等，故有时候重写hashCode和equals方法尤为重要。

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
public V get(Object key) {
    if (key == null)
        return getForNullKey(); // key为空的逻辑
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}
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;
}
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;
}