Java使用什么散列函数来实现Hashtable类？

Question

从CLRS("算法导论")一书中,有几种散列函数,如mod,multiply等.

Java使用什么散列函数将密钥映射到插槽？

我看到Java语言中使用的哈希函数存在一个问题.但它没有回答这个问题,我认为这个问题的明确答案是错误的.它说hashCode()允许你为Hashtable做你自己的散列函数,但我认为这是错误的.

hashCode()返回的整数是Hashtble的真实密钥,然后Hashtable使用散列函数来散列hashCode().这个答案暗示的是Java让你有机会给Hashtable一个散列函数,但不,这是错误的.hashCode()给出真正的密钥,而不是散列函数.

那么Java使用的哈希函数究竟是什么呢？

Answer 1

当在OpenJDK中向HashMap添加或请求密钥时,执行流程如下:

1. 使用开发人员定义的hashCode()方法将密钥转换为32位值.
2. 然后,通过第二个散列函数(其安德鲁的答案包含源代码)将32位值转换为散列表内的偏移量.第二个哈希函数由HashMap的实现提供,并且不能被开发人员覆盖.
3. 如果哈希表中尚不存在密钥,则哈希表的对应条目包含对链接列表的引用或null.如果存在冲突(具有相同偏移的多个键),则将键及其值简单地收集在单个链接列表中.

如果选择适当高的哈希表大小,则冲突的数量将受到限制.因此,单个查找平均只需要恒定的时间.这称为预期的恒定时间.但是,如果攻击者控制插入哈希表的密钥并了解正在使用的哈希算法,他可能会引发大量哈希冲突,从而迫使线性查找时间.这就是为什么最近一些哈希表实现已被更改为包含一个随机元素,使攻击者更难以预测哪些键会导致冲突.

一些ASCII艺术

key.hashCode()
     |
     | 32-bit value
     |                              hash table
     V                            +------------+    +----------------------+
HashMap.hash() --+                | reference  | -> | key1 | value1 | null |
                 |                |------------|    +----------------------+
                 | modulo size    | null       |
                 | = offset       |------------|    +---------------------+
                 +--------------> | reference  | -> | key2 | value2 | ref |
                                  |------------|    +---------------------+
                                  |    ....    |                       |
                                                      +----------------+
                                                      V
                                                    +----------------------+
                                                    | key3 | value3 | null |
                                                    +----------------------+

Answer 2

根据hashmap的源代码,每个hashCode都使用以下方法进行哈希处理:

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

每个hashCode再次进行哈希处理的原因是为了进一步防止冲突(参见上面的注释)

HashMap还使用一种方法来确定哈希码的索引(因为长度总是2的幂,你可以使用&而不是%):

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

put方法看起来像:

int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);

哈希码的目的是为给定对象提供唯一的整数表示.那么,有意义的是,Integer的hashCode方法只返回值,因为每个值对于该Integer对象都是唯一的.