是否有不同的方法来计算HashMap中的表索引 [英] Are there different ways to calculate the table index in HashMap
问题描述
http://en.wikipedia.org/wiki/Hash_table
我正在查看维基,这里是查找表索引的步骤。
I was looking at the wiki and here are the steps to find the table index.
hash = hashfunc(key) // calculate hash value.
index = hash % array_size // calculate index value through modulus.
但它在Java中的表现方式似乎完全不同。
But it seems the way it is performed in Java is quite different.
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);
}
计算表索引的indexFor方法似乎有所不同。任何人都可以对此有所了解。
The indexFor method which calculates the table index seems to be different. Can anyone add some light on this.
更新:
散列算法可能相应的变化,但我们计算表索引的方式应该是即使我没有错,但我看到wiki做什么和java的方式有冲突?。
Hashing algorithim might vary accordingly, but the way we calculate the table index should be even if i am not wrong, but i see a conflict in what wiki does and the way java does?.
要测试的示例代码:
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Test {
public static void main(String args[]) {
Map<String, String> m = new HashMap<String, String>();
m.put("Shane", null);
Iterator<String> itr = m.keySet().iterator();
while (itr.hasNext()) {
String key = itr.next();
int hash = hash(key.hashCode());
System.out.println("&&& used" + "table[" + (hash & 15) + "]=" + key);
System.out.println("%%% used" + "table[" + (hash % 15) + "]=" + key);
}
}
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
}
输出:
&&& usedtable[14]=Shane
%%% usedtable[8]=Shane
运行上面的程序,当我使用%时,你可以看到表索引是不同的,当我使用&时,表索引是不同的。
Run the above program and you could see the table index is different when i use % and table index is different when i use &.
推荐答案
但它在Java中的表现方式似乎完全不同。
But it seems the way it is performed in Java is quite different.
实际上它们完全一样。
hash = hashfunc(key) // calculate hash value.
与
hash = hash(key.hashCode());
和
index = hash % array_size (assumes the hash is unsigned)
与
return h & (length-1);
因为长度是2的幂。
这篇关于是否有不同的方法来计算HashMap中的表索引的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!