首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >HashMap#hash(int)方法说明

HashMap#hash(int)方法说明
EN

Stack Overflow用户
提问于 2010-03-10 10:23:28
回答 2查看 5.3K关注 0票数 25

有人能给我解释一下静态的HashMap#hash(int)方法吗?

生成均匀分布的散列背后的理由是什么?

代码语言:javascript
复制
/**
 * 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);
}

举个例子会让它更容易理解。

澄清我知道运算符,真值表和按位运算。我真的不能解码实现,也不能真正解码注释。甚至是它背后的原因。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2010-03-10 10:33:11

>>>是逻辑右移位(无符号扩展) (JLS 15.19 Shift Operators),^是按位异或(JLS 15.22.1 Integer Bitwise Operators)。

至于为什么要这样做,文档提供了一个提示:HashMap使用2的幂长度表,并通过屏蔽掉较高的位并只取其哈希码的较低位来散列关键字。

代码语言:javascript
复制
// HashMap.java -- edited for conciseness
static int indexFor(int h, int length) {
    return h & (length-1);
}

public V put(K key, V value) {
    int hash = hash(key.hashCode());
    int index = indexFor(hash, table.length);
    // ...
}

所以hash()试图给高位带来相关性,否则就会被屏蔽掉(indexFor基本上丢弃了h的高位,只取length == (1 << k)的低位k位)。

与此形成对比的是,Hashtable (不应该有2次方的长度表)使用键的哈希码。

代码语言:javascript
复制
// Hashtable.java -- edited for conciseness
public synchronized V get(Object key) {
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % table.length;
    // ...
}

通过执行更昂贵的%操作(而不是简单的位掩码),Hashtable的性能对低位分布较差的哈希码不太敏感(特别是当table.length是质数时)。

票数 16
EN

Stack Overflow用户

发布于 2010-03-10 11:21:04

我不知道所有的转变是如何工作的,但动机在评论中列出:

HashMap的实现方式依赖于hashCode函数的充分实现。特别是,散列值的低位应该均匀分布。如果在较低的位上有许多冲突,HashMap将无法正常运行。

因为hashCode的实现不受HashMap的控制(每个对象都可以实现它们自己的),所以它们提供了一个额外的散列函数,该函数会稍微移动对象的hashCode,以确保低位更随机地分布。同样,我不知道这是如何工作的(或者它有多有效),但我假设它至少取决于高位均匀分布(它似乎将高位网格化到低位中)。

因此,这样做是为了在存在实现不佳的hashCode方法的情况下尽量减少冲突(从而提高性能)。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/2414117

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档