1

我正在处理一项任务，我必须将 10,000 个数字散列到负载大小为 0.1、.2 .3 .... 到 0.9 的散列表中。我的问题是我的散列函数给了我一些溢出或类似的东西。如果我对负载因子为 0.5 的表（如 36077(mod)20,000）进行哈希处理，它会给我 16070 作为键。这只发生在高于负载因子的数字上。这是我的散列函数的代码。

    public int linearHash(int in){
    int hashKey = in%hashTableArray.length;
    while(this.hashTableArray[hashKey] != 0){
        hashKey += 1;
    }
    return hashKey;
}

谢谢你。

4

2 回答 2

0

Reimeus指出OutOfBound问题并给出了解决方案。我只是想补充一些关于你处理碰撞的方式。

您的功能看起来像开放寻址方法。而不是hashKey += 1;也许你可以考虑增加in

 public int linearHash(int in){   
    int hashKey = in%hashTableArray.length;
    while(this.hashTableArray[hashKey] != 0){
        in ++;
        hashKey = in%hashTableArray.length;
    }
    return hashKey;
}

上面的示例代码没有检查哈希表溢出。自动增量不应发生hashTableArray.length多次。否则你的程序会陷入死循环

请注意，通过检查来决定插槽是否空闲hashTableArray[hashKey] != 0是不安全的。例如，你的元素中是否有数字0和20000。

于 2012-11-02T21:59:52.213 回答
0

您没有检查是否超出了循环hashTableArray中的索引范围。while你可以这样做：

while (hashKey < hashTableArray.length && this.hashTableArray[hashKey] != 0){
于 2012-11-02T21:23:42.650 回答