A map of keys and values
This program counts words in a Map: it associates each key with a value. Inside, a HashMap is an array of buckets. With capacity 16, that is 16 drawers.
This program counts words in a Map: it associates each key with a value.
Inside, a HashMap is an array of buckets. With capacity 16, that is 16 drawers.
This program counts words in a Map: it associates each key with a value. Inside, a HashMap is an array of buckets. With capacity 16, that is 16 drawers.
put("cat", 3) does not look for a free slot: it first asks the key for its hashCode().
The key answers with an integer: for "cat" it is 98262.
Java mixes its bits and applies a mask. The result is bucket 7.
put("cat", 3) does not look for a free slot: it first asks the key for its hashCode(). The key answers with an integer: for "cat" it is 98262. Java mixes its bits and applies a mask. The result is bucket 7.
That number is an address: the key goes straight to its bucket, ignoring the others.
The whole entry is stored there: the key together with its value.
That number is an address: the key goes straight to its bucket, ignoring the others. The whole entry is stored there: the key together with its value.
Another key, another hash: "moon" ends up in bucket 2.
With a well-distributed hash, keys almost never share a bucket.
Another key, another hash: "moon" ends up in bucket 2. With a well-distributed hash, keys almost never share a bucket.
Now "bird" arrives. Its hash is different from that of "cat"β¦
β¦but after the mask, the result is bucket 7 again.
It is a collision: two different keys landed in the same bucket.
Now "bird" arrives. Its hash is different from that of "cat"β¦ β¦but after the mask, the result is bucket 7 again. It is a collision: two different keys landed in the same bucket.
Inside the bucket, equals() compares the new key with the one already there.
"bird" is not equal to "cat": they are different keys and both are kept.
Inside the bucket, equals() compares the new key with the one already there. "bird" is not equal to "cat": they are different keys and both are kept.
get("bird") repeats the path: the same key always produces the same hash.
In bucket 7, equals() rules out "cat" and recognizes "bird".
The map returns the value associated with that key: 5.
get("bird") repeats the path: the same key always produces the same hash. In bucket 7, equals() rules out "cat" and recognizes "bird". The map returns the value associated with that key: 5.
It did not walk the collection: one calculation, one bucket. That is why get() is O(1).
In a List, finding an element means walking through it: O(n).
hashCode() picks the drawer; equals() picks the element inside the drawer.
It did not walk the collection: one calculation, one bucket. That is why get() is O(1). In a List, finding an element means walking through it: O(n). hashCode() picks the drawer; equals() picks the element inside the drawer.