Re: need clarification on HashMap storage-retrieval

Piper707@hotmail.com wrote:


   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.