Please share some insights on rehash method in java?

540 views Asked by At

I am looking for some better insight on hashtable/hash-map data-structure.

By going through the api I could make out that inner Entry class is referrred to as bucket. Please correct me if I am wrong.

Please find the following method:-

  public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

    modCount++;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = hash(key);
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    Entry<K,V> e = tab[index];  <-------are we assigining null to this entry?
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
    return null;
}

By the following line of code

Entry<K,V> e = tab[index];

I can assume that we are assigning null to this new entry object; Please correct me here also.

So my another question is :-

why are we not doing this directly

Entry<K,V> e = null 
 instead  of 
Entry<K,V> e = tab[index];

Please find below is the screen shot for the debug also:- enter image description here

Please share your valuable insights on this.

1

There are 1 answers

4
Eran On BEST ANSWER

Entry<K,V> is an instance that can represent a link in a linked list. Note that the next member refers to the next Entry on the list.

A bucket contains a linked list of entries that were mapped to the same index.

Entry<K,V> e = tab[index] will return null only if there's no Entry stored in that index yet. Otherwise it will return the first Entry in the linked list of that bucket.

tab[index] = new Entry<>(hash, key, value, e); creates a new Entry and stores it as the first Entry in the bucket. The previous first Entry is passed to the Entry constructor, in order to become the next (second) Entry in the list.