调整表大小时在哈希函数中查找错误
调整表大小时在哈希函数中查找错误
提问于 2014-04-08 17:00:32
在准备考试的时候，我遇到了一个关于散列表的问题。我得到了一个长度为11的表，表的哈希函数如下：
h(k,i) = ( k mod 13 + i * (1 + k mod 7) ) mod 11然后哈希表的大小调整为12。因此，新的哈希函数变成：
h'(k,i) = ( k mod 13 + i * (1 + k mod 7) ) mod 12出现了哪些问题？
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-04-08 20:43:01
问题是哈希函数会变得更糟。
在第一种情况下，k和i的不同组合在11个散列箱中的分布非常均匀。在第二种情况下，分布并不是那么均匀--特别是k和i的组合数，对于这两个组合，哈希函数的结果将是0明显更高。
当然，在考试中，人们可能不得不争论为什么会这样。某种程度上与
- K mod 13是介于0和12之间的值。
- K mod 7是介于0和6 (除以12)之间的值。
- 也许，不知何故: 11是一个素数，12有许多除数.
但是(至少对我来说)很难找到一个令人信服的理由来超越这些琐碎的洞察力。也许你有另外一个想法。
import java.util.LinkedHashMap;
import java.util.Map;
public class HashTest
{
public static void main(String[] args)
{
int maxK = 30;
int maxI = 30;
System.out.println(computeFrequencies(h0, maxK, maxI));
System.out.println(computeFrequencies(h1, maxK, maxI));
}
private static Map<Integer, Integer> computeFrequencies(
Hash hash, int maxK, int maxI)
{
Map<Integer, Integer> frequencies =
new LinkedHashMap<Integer, Integer>();
for (int k=0; k<maxK; k++)
{
for (int i=0; i<maxI; i++)
{
int value = hash.compute(k, i);
Integer count = frequencies.get(value);
if (count == null)
{
count = 0;
}
frequencies.put(value, count+1);
}
}
return frequencies;
}
private static interface Hash
{
int compute(int k, int i);
}
private static final Hash h0 = new Hash()
{
@Override
public int compute(int k, int i)
{
return ((k % 13) + i * (1 + (k % 7))) % 11;
}
};
private static final Hash h1 = new Hash()
{
@Override
public int compute(int k, int i)
{
return ((k % 13) + i * (1 + (k % 7))) % 12;
}
};
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22943610
复制相关文章
相似问题
腾讯云开发者
