Reputation: 29
I was going through the internal structure of HashMap
and got stuck in the concept of how a bucket stores multiple objects.
As HashMap
is an array of Entry
objects, every index of array is a bucket. The Entry
class is like
static class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> next_entry;
int hash;
}
On Adding a new key-value pair
So how can a bucket store multiple object as per the 2nd point?
Upvotes: 2
Views: 3253
Reputation: 13556
This is about HashMap in Oracle JDK 1.7.0.55.
Creating a new entry is done through:
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
which clearly shows that the already existing element is stored as next element of the new element. So the array contains the buckets. Buckets themselves are single linked lists made up of Entry
elements.
And when a get
operation is performed, then this single linked list is iterated as can be seen in the for
loop of (comment by me)
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) { // <- see here
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
So the Entry
elements of the single linked list all have keys with the same hash. But by the contract of hashCode
objects not equal to each other may have the same hash codes. So using key.equals(k)
in the above for loop will not be true for the first round in the loop in every case. So the loop may be traversed until the end of the linked list.
Upvotes: 2
Reputation: 7054
HashMap maintains an array: Entry[]; each element of that array represents a "bucket". The remainder of the entries in the bucket are accessed by traversing a linked list maintained in by Entry.next.
Upvotes: 0
Reputation: 201537
Java HashMap
uses a linkedlist
for buckets (but not a java.util.LinkedList
). If a class hard codes the hashCode()
method to a single value; instances of such a class loaded into a HashMap
the structure will degenerate into a linkedlist
. You override equals()
to support replace in the "bucket".
Upvotes: 0