Re: need clarification on HashMap storage-retrieval
Piper707@hotmail.com wrote:
(K) String key1 -> (V) Apple instance.
(K) String key2 -> (V) Orange instance.
Assume both key1 and key2 give the same hashcode - 745. Since both
keys map to the same hashcode, both apple and orange objects will be
in the same bucket.
1) Do both key and value sit in a bucket or is it only the value? If
only the values, where do the keys sit?
Map <K, V> has a nested type Map.Entry <K, V> that represents a key/value
pair. The pair "sits" in the bucket identified by the key's hash, modulo the
number of buckets.
2) How does hashmap.get(key1) find the associated value?
- use equals to make sure key1 exists in the hashmap
No.
- if found, calculate hashcode of key1
- find bucket associated with that hashcode
- in the bucket find the correct object associated with the key.
How does the last step above, take place? Even if both Apple and
Orange have implemented hashCode and equals, how does the hashmap
figure out which apple links to key 1?
Apple and Orange hashes have nothing to do with it, assuming that the key is
not one of those types.
When does the hashcode for Apple and Orange come into play? or does it
never?
The hash of the key determines the bucket. At the bucket is a linked list of
entries. The lookup walks the list at that bucket until it finds the entry
with the key that equals() the query key, or until it exhausts the list.
Generally such a list is quite short, zero to two entries, assuming a decent
hashCode() implementation for the key type. If the entry with a key that
equals() the candidate is found in the list, its value is returned.
GIYF. WIYF.
<http://en.wikipedia.org/wiki/Hash_table>
Seriously, one minute by typing "Hash map" or "Hash table" into Wikipedia's
"search" box.
--
Lew