Re: need clarification on HashMap storage-retrieval
Piper707@hotmail.com wrote:
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?
Conceptually I would say it's both. I haven't actually looked at
HashMap to determine how it's physically stored. A HashMap<K,V> has inside:
class Bucket {
K key;
V value;
}
so it just pairs them up. Realistically, the bucket is probably an
array of Objects.
2) How does hashmap.get(key1) find the associated value?
Something like:
1. Use the hashcode to get the bucket index.
2. Use equals to determine if the key has been found.
3. If so, return the associated value from the bucket.
4. If not, rehash and go back to 2
If the rehash algorithm doesn't work, HashMap probably throws some sort
of runtime error. I don't know it's rehashing strategy (list? overflow
map? different hash algorithm?) so I can't really say.
- use equals to make sure key1 exists in the hashmap
- 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?
HashMap uses equals() to determine if the bucket is correct, step 2
above. If it's not equal the HashMap goes to a different bucket. The
rehashing strategy determines which bucket it looks in next. The
simplest strategy is, given an array of buckets, just to look in the
next bucket in the array until you find it. This is pretty bad though
because it can degenerate in to O(n) search pretty quickly. More
sophisticated rehashing randomizes the location of the next bucket.
When does the hashcode for Apple and Orange come into play? or does it
never?
Never, just for the key.