转载

HashMap-内部存储

翻译自 http://coding-geek.com/how-do...

并在原文基础上做了修改和补充

Java HashMap类实现了Map<K,V> 接口，这个接口的几个主要的方法如下：

• V put(K key, V value)

• V get(Object key)

• V remove(Object key)

• Boolean containsKey(Object key)

HashMap用一个内部类去存储数据Entry<K, V>，它就是一个简单的键值对，同时有两个额外的数据：

• 指向另一个entry的指针，有点类似于单向无序链表。

• hash值，这个是对应于K的hash 值，以避免每次HashMap使用时重新计算。

在JDK 7中，Entry的部分实现如下：

static class Entry<K,V> implements Map.Entry<K,V> {

final K key;
    V value;
    Entry<K,V> next;
    int hash;

}

HashMap将数据存储到多个Entry链表，然后每个链表都会注册到Entry数组中去，对应于一个bucket。这初始数组的大小是16(DEFAULT_INITIAL_CAPACITY)

HashMap中有一个桶(bucket)的概念, 其实这个桶就是entry数组(HashMap初始化的时候会创建一个固定大小的数组)中的一个元素，如下所示：

/**

* The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry[] table;

有相同hash value的key都会被放到同一个桶中，然后entry之间通过指针相连，就组成了链表。当调用HashMap的put或者是get方法时，方法首先计算key的hash值，然后计算出到底是该属于哪个bucket。找到桶之后，遍历bucket对应的entry 链表，再找到对应的key值，链表里面的查是通过key的equals方法完成的。该步骤的代码如下所示（JDK 7）：

public V get(Object key) {

if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    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.equals(k)))
            return e.value;
    }
    return null;
}

map 生成桶需要经过下面的3步：

• 首先获取key的hash value。

• 然后会再次计算一次hash, 这样做的目的是为了避免hash函数将数据都放在同一个桶中（以下是JDK 7的实现，JDK 8做了简化，原理一样）。

/**

* 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.
 */
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函数造成的冲突。该函数称为‘扰动函数‘。

• 拿到重新计算的hash值之后, 再计算它对应的index，也就是该放到哪个桶里面。

/**

* Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

为什么需要重新计算hash？举个栗子：

shinadata字符串的 HashCode的binary是 1000001111000010101000110010001，上述代码中的length 就是数组（Entry[] table）的长度。（length – 1)=15，15的二进制是1111，如果不做rehash操作，此时1111高位补0，和1000001111000010101000110010001 做位与&运算，那么shinadata 的HashCode 在计算过程中只有最后几位能起作用，无论高位是多少，只要低位是相同的话，那么最后的结果就相同了，这样indexFor方法计算出的index值就容易产生冲突。扰动函数的作用就是为了消除这方面的影响。

为什么内部数组的大小是2的幂？

假设数组大小是17，那么掩码值是16（size -1），二进制是0…010000，现在对于任何哈希值h , h & 16 得到索引不是16就是0。那么这就意味着，数组大小17，使用的桶只能是2个。但是要是用2的幂的值的话，那就不同了，比如16，size - 1 = 15, 二进制是0…001111, h & 15 得到的索引值可以使 0~15。

这部分可以查看JDK 7的源码。 http://hg.openjdk.java.net/jd...

参考：

https://blog.csdn.net/wenyiqi...

https://www.zhihu.com/questio...

翻译自 http://coding-geek.com/how-do...

并在原文基础上做了修改和补充

HashMap-内部存储