Re: need clarification on HashMap storage-retrieval
Piper707@hotmail.com wrote:
Hi,
I'm trying to break down the steps that occur when storing a Key-Value
mapping into a hashmap. Specifically, I want to understand how
hashcode and equals come into play.
I have following mappings to store:
(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?
The "bucket" holds instances of Map.Entry, each of which
holds a reference to one key and one value.
2) How does hashmap.get(key1) find the associated value?
- 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.
The steps are right, pretty much, but in the wrong order.
The get() method gets the hash value from key1.hashCode(), and
does some simple arithmetic on that value to choose one of the
map's buckets. It goes through the Map.Entry instances in the
bucket, looking for one whose key equals() key1. If it finds
such a Map.Entry it returns the Map.Entry's value; otherwise,
the search was unsuccessful.
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?
As above: Use key1's hashCode() to decide which bucket to search,
then look through all the bucket's Map.Entry instances for one whose
key equals() key1. (The actual implementation uses a few additional
techniques to speed up the search, but the essentials are the same.)
When does the hashcode for Apple and Orange come into play? or does it
never?
In choosing which bucket to search.
what am I missing here?
Hard to tell, but I think you don't understand the purpose of
the hashing technique. Let's take a very simple example. Suppose
you have a bunch of people in a room, each with a distinct last
name (the key) and a first name (the value):
Oh, Sadaharu
Ott, Mel
Oort, Jan
Owens, Jesse
...
Ozymandias, n/a
You want to find the first name for someone whose last name is Otter,
so you go to each person in turn and ask "Are you Otter?" "No."
"Next, please: Are you Otter?" "No." "Next, please: Are you Otter?"
"Yes." "Aha! What's your full name?" "Anne Sofie von Otter."
However, this takes too long: You're forced to ask too many
questions, on average, before getting an answer. In fact, to get
the result "Nobody here named Oobleck" you need to ask every single
person in the room. There are many techniques you might use to
speed things up, but here's how you might use a simple hash.
As the people enter the room in the first place, ask each for
his last name and count the number of letters in it. Send those
with an odd letter count to the left side of the room, and those
with even counts to the right. That is, you compute a hash code
(the number of letters in the name) and use it to choose one of
two buckets (left side or right side).
Now to search for Otter, you count the letters and get five,
which as an odd number selects the left-side bucket. You go to
the people on that side only and start asking "Are you Otter?" as
before. You can ignore everyone on the right side because since
they all have even-length names none of them can possibly be Otter;
you save the time that would have been wasted questioning them and
getting "No" as the answer every time. If evens and odds are equally
abundant, you get your answer in about half the time you would have
spent had you not been able to ignore the right-hand side.
You could save even more time by using more buckets: Count the
letters as before, then divide by four and note the remainder. Send
the zeroes to the northeast corner, the ones to the northwest, the
twos to the southwest, and the threes to the southeast. If the four
possible remainders are equally abundant, you can get your result
in about one-quarter the time by eliminating three-quarters of the
candidates from consideration right at the outset.
That's hashing.
--
Eric.Sosman@sun.com