CODEWITHSUNDEEP
javahash
ough lala
ough lala

Reputation: 31

Hash Table insert

I don't understand this code, to insert a new element to an array (hash table) I understand that if it's empty, then we add the new element, and we return null (because before, the value was null).

But I don't understand while (e != null && !e.key.equals(c)), it means that while it's not null and while the key is not equal to the one that we want to add? Isn't it supposed to be equal, since we use indiHash(c) to find the position in the array where we add the new element, so if there are in the same bucket they should have the same keys: and then we go to the next one, which means that we are going to add that element at the complete end of the bucket list? I also don't understand 

valuebefore = e.valor;
e.valor = v;

What are we returning? The value of the element that was last on the bucket list before we added the new one?

I don't understand how can there be a if (e != null) because just before, in the while loop, we made sure that the e is null when we leave the loop

public V insert(C c, V v) {

    V valuebefore = null;
    int position = indiHash(c);
    EntryHash<C, V> e = Array[pos];

    while (e != null && !e.key.equals(c))
        e = e.next;

    if (e == null) { 
        Array[position] = new EntryHash<C,V>(c, v, Array[position]);
        size++;
    } else { // 
        valuebefore = e.valor;
        e.valor = v;
    }
    return valuebefore;
}

Upvotes: 1

Views: 944

Answers (1)

JB Nizet
JB Nizet

Reputation: 691785

Many different objects can have the same hash code. And even if they don't have the same one, since the array has a length much shorter than 2^32 (the number of different possible hash codes), objects with different hash codes end up in the same bucket.

So objects which end up in the same bucket are stored in a linked list of entries. The above code tries to find an entry in this linked list that has a key equal to the inserted key. If it doesn't find any, a new entry is created and added to the linked list. Otherwise, the value associated with the found entry is replaced by the new value.

Upvotes: 3

Related Questions