Maps

Feb 27th, 2020 - Now

HashMap

存储结构

左侧是一个数组，数组的每个成员是一个链表，每个元素都包含着一个指针，用于元素之间的连接。Hash函数根据Object的性质将Object插入到其中去，同理也从中寻找取出。

Java 7

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    // 下面进行的是一个hash的扰乱
    // 因为在下面我们直接与 length-1 与操作
    // 如果不进行扰动会导致高位的贡献为0
    // 所以这里是将高位部分 (h>>>20) 和中间位 (h>>>12)
    // 和低位都进行了一个计算最后得到我们的数值
    h ^= k.hashCode(); 
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

// indexFor函数获取当前的Object插入的下标  
// 由于 Java 中初始化和扩容hash存储的数组都是 2的幂次
// 所以直接用 & (2^n-1) 代替 % 2^n 的操作
// 还有一个好处就是，取模操作对负数的支持不好
// 直接与操作保证了不会出现负数，无需考虑数组越界
static int indexFor(int h, int length) {
    return h & (length-1);
}

Java8

static final int hash(Object key) {
    int h;
    // 追求速率，直接一次高位与低位的异或混合，而不是四次
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

ConcurrentHashMap

Java7

private int hash(Object k) {
    int h = hashSeed;

    if ((0 != h) && (k instanceof String)) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // Spread bits to regularize both segment and index locations,
    // using variant of single-word Wang/Jenkins hash.
    h += (h <<  15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h <<   3);
    h ^= (h >>>  6);
    h += (h <<   2) + (h << 14);
    return h ^ (h >>> 16);
}

int j = (hash >>> segmentShift) & segmentMask;

Java8

Java 8 里面的求hash的方法从hash改为了spread。

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

HashTable (线程安全)

Java7

private int hash(Object k) {
    // 简单进行hash，并取其hashCode
    // hashSeed will be zero if alternative hashing is disabled.
    return hashSeed ^ k.hashCode();
}

// 没有单独的 indexOf() 只有下面的：
// 和 0x7FFFFFFF 进行与操作是为了避免出现负数求模
int index = (hash & 0x7FFFFFFF) % tab.length;

为什么HashTable的hash函数和取模都采用的是最简单的方式？

需要考虑到 HashTable 的构造函数和扩容函数： HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。 也就是说，HashTable的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。 由于HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。 详细的论证：Link

Reference

1. Hollis | 全网把Map中的hash()分析的最透彻的文章，别无二家。