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:-
Please share your valuable insights on this.
Entry<K,V>
is an instance that can represent a link in a linked list. Note that thenext
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.