0

我正在尝试在处理多个“动物”的哈希表中编写线性探测的解决方案，类似于下面给我的那个。

index++;
if(index == hashAnimals.length) {
    index = 0;
}
if(hashAnimals[index] == null){
    hashAnimals[index] = new Animal(animals.get(i));
}

但有人告诉我，这只是一种动物的解决方案，在一个位置。所以这是我目前针对多种动物的解决方案：

int index = 0;
for(int i = 0; i < hashAnimals.length) {
    if(index = hashAnimals.length){
        index = 0;
    }

但是我在考虑找到一个自由职位的解决方案时遇到了问题。我应该使用另一个 for 循环吗？如果我只是在我的代码中复制了上面的第二个 if 语句，我相信如果索引已经被占用，我试图添加的“动物”将被跳过，并且“i”将在末尾递增到下一个动物循环。

4

2 回答 2

1

In general, linear probing starts with the index provided by the hash function and then looks for the closest index for an empty cell.

There's really no need to have a special wrap-around case. Much easier to just use a modulo operator.

Animal[] hashTable = new Animal[SIZE];

void put(Animal animal) {
    for (int i = 0; i < SIZE; i++) {
        int index = (animal.hashCode() + i ) % SIZE;
        if (hashTable[index] == null) {
            hashTable[index] = animal;
            return;
        }
    }
    throw new IllegalStateException("No empty cells in hash table");
}
于 2017-11-27T05:03:41.183 回答
0

要在数组中查找空闲位置，请考虑以下代码段

String animals[] = {"Dog","Cat","Cow"};
String hashAnimals[] = {"1", null, null, "4", null, null};
int index =5;
for(int j=0; j<animals.length; j++) {
    for(int i=0; i<hashAnimals.length; i++) {
        if(index == hashAnimals.length) {
            index = 0;
        }
        if(hashAnimals[index] == null){
            hashAnimals[index] = animals[j];
            index++;
            break;
        }
        index++;
    }
}

分解片段：

需要在 hashAnimals 的空闲空间中填充动物。指针的当前位置为 5。可用空间应从当前位置开始识别，即 5。

String animals[] = {"Dog","Cat","Cow"};
String hashAnimals[] = {"1", null, null, "4", null, null};
int index =5;

使用循环迭代动物并在animalsHash中填充它，是的，需要有两个循环。

for(int j=0; j<animals.length; j++) {
    for(int i=0; i<hashAnimals.length; i++) {

一旦animalsHash的指针到达结束位置即6，将其重置为开始位置即0。

        if(index == hashAnimals.length) {
            index = 0;
        }

如果有空闲位置，则填充当前动物并打破循环。由于当前空闲空间被占用，因此增加索引。

        if(hashAnimals[index] == null){
            hashAnimals[index] = animals[j];
            index++;
            break;
        }
        index++;

现在 hashAnimals 看起来像 {"1", "Cat", "Cow", "4", null, "Dog"} 对于给定的片段。

于 2017-11-27T08:32:18.367 回答