HashMap＃hash（int）方法的解释

问题描述

有人可以向我解释静态HashMap＃hash（int）方法吗？

生成均匀分布的散列的理由是什么？

  / ** 
 *对给定的hashCode应用一个补充散列函数，
 *可以抵御劣质散列函数。这是至关重要的
 *，因为HashMap使用两个长度的哈希表，所以
 *会碰到hashCodes的冲突，而这些hashCodes在低位中不会有
 *的差异。注意：空键总是映射到散列0，因此索引为0. 
 * / 
 static int hash（int h）{
 //此函数确保只有
 //每个比特位置的常数倍数有一个有界的
 //碰撞次数（默认加载因子大约为8）。 （h>>> 20）^（h>> 12）; 
 return h ^（h>> 7）^（h>> 4）; 
} 
  

一个例子可以让您更容易理解。

澄清
我知道操作符，真值表和按位操作。我真的不能真正解码实现和评论。甚至是背后的推理。

解决方案

>>> 是逻辑右移（无符号扩展）（）和 ^ 是按位异或（）。

As为了做到这一点，文档提供了一个提示： HashMap 使用两个长度表的幂，通过屏蔽掉高位并只取低位。

  // HashMap.java  - 为了简洁而编辑
 static int indexFor（int h， int length）{
 return h& （长度-1）; 
 
 $ b $ public V put（K key，V value）{
 int hash = hash（key.hashCode（））; 
 int index = indexFor（hash，table.length）; 
 // ... 
} 
  

所以 hash（）会尝试将更高的位置关联起来，否则会被屏蔽掉（ indexFor 基本上丢弃<$ c $的高位位c> h ，并且仅取得低于 k 位，其中长度==（1


与 Hashtable （它不应该具有幂次）的对比

  // Hashtable.java  - 为了简洁而编辑
 public -two table）使用键的哈希码。同步V get（Object key）{
 int hash = key.hashCode（）; 
 int index =（hash& 0x7FFFFFFF）％table.length; 
 // ... 
} 
  

通过执行更加昂贵的％操作（而不是简单的位掩码）， Hashtable 的性能对散列较差的哈希码不太敏感（特别是如果 table.length 是一个素数）。

Can someone please explain to me the static HashMap#hash(int) method?

What's the justification behind it to generate uniformly distributed hashes?

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

An example would make it easier to digest.

ClarificationI'm aware of the operators, truth tables and bitwise operations. I just can't really decode the implementation nor the comment really. Or even the reasoning behind it.

解决方案

>>> is the logical right shift (no sign-extension) (JLS 15.19 Shift Operators), and ^ is the bitwise exclusive-or (JLS 15.22.1 Integer Bitwise Operators).

As to why this is done, the documentation offers a hint: HashMap uses power-of-two length tables, and hashes keys by masking away the higher bits and taking only the lower bits of their hash code.

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

So hash() attempts to bring relevancy to the higher bits, which otherwise would get masked away (indexFor basically discards the higher bits of h and takes only the lower k bits where length == (1 << k)).

Contrast this with the way Hashtable (which should have NOT a power-of-two length table) uses a key's hash code.

// Hashtable.java -- edited for conciseness
public synchronized V get(Object key) {
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % table.length;
    // ...
}

By doing the more expensive % operation (instead of simple bit masking), the performance of Hashtable is less sensitive to hash codes with poor distribution in the lower bits (especially if table.length is a prime number).

这篇关于HashMap＃hash（int）方法的解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！