Решение для хеш-таблицы и линейного зондирования для нескольких элементов

Question

Я пытаюсь написать решение для линейного зондирования в хеш-таблице, имеющее дело с несколькими "животными", аналогично тому, которое было дано мне ниже.

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

Но у меня проблемы с поиском решения о поиске свободной позиции. Должен ли я использовать другой цикл? Если бы я просто скопировал второе выражение if в моем коде выше, я считаю, что "животное", которое я пытаюсь добавить, будет пропущено, если индекс уже занят, и "i" будет увеличиваться до следующего животного в конце петля.

Answer 1

Чтобы найти свободную позицию в массиве, рассмотрите следующий фрагмент

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

Разрыв фрагмента:

Животные должны быть размещены в свободном пространстве животных. Текущая позиция указателя равна 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"}.

Answer 2

Обычно линейное зондирование начинается с индекса, предоставленного хэш-функцией, а затем ищет ближайший индекс для пустой ячейки.

Там действительно нет необходимости иметь специальный чехол для упаковки. Гораздо проще просто использовать оператор по модулю.

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