CODEWITHSUNDEEP
javahashtablelinear-probing
user7939273
user7939273

Reputation:

Solution to hash table and linear probing for multiple elements

I'm trying to write a solution for linear probing in a hash table dealing with multiple "animals", similar to the one below that was given to me. 

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

But I've been told that this would simply be the solution for ONE animal, in ONE position. And so this is my current solution that I've started for multiple animals:

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

But I'm having a problem thinking about a solution of finding a free position. Should I use another for loop? If I simply copied the second if statement above in my code, I believe the "animal" that I'm trying to add would be skipped if the index was already taken, and "i" would increment to the next animal at the end of the loop.

Upvotes: 0

Views: 1535

Answers (2)

Janarthanan
Janarthanan

Reputation: 41

To find the free position in an array consider the following snippet

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

Break up of the snippet:

Animals needs to be populated in the free spaces of hashAnimals. The current position of the pointer is 5. The free space should be identified starting from the current position, which is 5.

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

Iterate animals and populate it in animalsHash using the loop, yes need to have two loops.

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

Once the pointer of animalsHash reaches end position i.e 6, reset it to the start position i.e 0.

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

If there is a free position, populate the current animal and break the loop. Since the current free space is occupied increment the index.

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

Now the hashAnimals will look like {"1", "Cat", "Cow", "4", null, "Dog"} for the given snippet.

Upvotes: 0

sprinter
sprinter

Reputation: 27946

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

Upvotes: 1

Related Questions