多个元素的散列table和线性探测的解决方案

Question

我正在尝试为处理多个 "animals" 的散列 table 中的线性探测编写解决方案，类似于下面提供给我的解决方案。

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 语句，我相信如果索引已经被占用，我试图添加的 "animal" 将被跳过，并且 "i" 将增加到下一个动物在循环结束时。

Answer 1

一般来说，线性探测从散列函数提供的索引开始，然后寻找最接近空单元格的索引。

确实不需要特殊的环绕式外壳。使用模运算符要容易得多。

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");
}

Answer 2

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

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++;
    }
}

片段的分解：

Animals 需要填充到 hashAnimals 的空闲 spaces 中。指针当前位置为5，freespace应该从当前位置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;
        }

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

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

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

多个元素的散列table和线性探测的解决方案

Solution to hash table and linear probing for multiple elements

java

hashtable

linear-probing