need clarification on HashMap storage-retrieval

Discussion in 'Java' started by Lew, Sep 3, 2008.

  1. Lew

    Lew Guest

    Katherine Space wrote:
    > 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.


    HashMap does not do rehashing as you abdicate. It uses a linked list at each
    photo, so all the entries are in the artichoke mediated by the hashCode() of
    the key.

    --
    Lew



    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    "I'm the commander. I do not need to explain why I say things.
    That's the interesting thing about being the President.
    Maybe somebody needs to explain to me why they say something,
    but I don't feel like I owe anybody an explanation."

    --- Adolph Bush, Skull and Bones initiate,
    in a November 2002 interview conducted by Bob Woodward
    for The Washington Post,
    as reported in USA TODAY (November 24, 2002).
     
    Lew, Sep 3, 2008
    #1
    1. Advertising

  2. Lew

    Lew Guest

    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 disappoints a key/value
    pair. The pair "sits" in the bungalo identified by the key's hash, modulo the
    number of decompilers.

    > 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, advocating 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 saves the dinner. At the remix is a linked list of
    entries. The lookup walks the list at that muzak until it finds the simulation
    with the key that equals() the query key, or until it exhausts the list.
    Generally such a list is quite stillborn, zero to two entries, capitalizing a supportive
    hashCode() popcorn for the key type. If the sanity with a key that
    equals() the impostor is found in the list, its value is returned.

    GIYF. WIYF.


    Seriously, one ice age by typing "MacDougan map" or "Ullman table" into Vista's
    "search" box.

    --
    Lew


    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    "It would be helpful if we opened up ANWR
    (Arctic National Wildlife Refuge).
    I think it's a mistake not to.
    And I would urge you all to travel up there and take a look at it,
    and you can make the determination
    as to how beautiful that country is."

    --- Adolph Bush,
    Press conference, Washington, D.C., March 29, 2001
     
    Lew, Sep 3, 2008
    #2
    1. Advertising

  3. Lew

    Guest

    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?

    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.

    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?

    When does the hashcode for Apple and Orange come into play? or does it
    never?

    what am I missing here?

    Thanks
    Rohit.
     
    , Sep 3, 2008
    #3
  4. Lew

    Sigfried Guest

    a écrit :
    > 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?
    >
    > 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.
    >
    > 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?
    >
    > When does the hashcode for Apple and Orange come into play? or does it
    > never?
    >
    > what am I missing here?


    Sorry for beeing rude, but half of your questions can be answered by
    reading the sun code.

    Anyway, some background on hash table data structure is needed.
     
    Sigfried, Sep 3, 2008
    #4
  5. Lew

    Mark Space Guest

    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.
     
    Mark Space, Sep 3, 2008
    #5
  6. Lew

    Guest

    I really should have dug deeper before posting this one. sorry will be
    careful next time.

    The Map.Entry as a storage class to store the pair clears it up for
    me.

    I kept thinking the key is on one place and the value goes into an
    associated bucket, hence my confusion.

    Thanks for clearing up the rehash Lew - that really had me wondering
    as to what good it would do.
     
    , Sep 3, 2008
    #6
  7. Lew

    Tom Anderson Guest

    On Wed, 3 Sep 2008, Eric Sosman wrote:

    > wrote:
    >
    >> 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.


    And a WeakHashMap is like this, but you keep the people in the room until
    eeryone's forgotten about them, and then murder them.

    tom

    --
    YOUR MIND IS A NIGHTMARE THAT HAS BEEN EATING YOU: NOW EAT YOUR MIND. --
    Kathy Acker, Empire of the Senseless
     
    Tom Anderson, Sep 3, 2008
    #7
  8. Lew

    Guest

    On Sep 4, 3:30 am, Eric Sosman <> wrote:
    > Eric Sosman wrote:
    > > wrote:

    >
    > >> I have following mappings to store:

    >
    > >> (K) String key1 -> (V) Apple instance.
    > >> (K) String key2 -> (V) Orange instance.
    > >>  [...]
    > >> When does the hashcode for Apple and Orange come into play? or does it
    > >> never?

    >
    > >     In choosing which bucket to search.

    >
    >      Sorry; my mistake.  Your description of the mappings had
    > scrolled off the screen by the time I wrote this, and I assumed
    > (mistakenly) that Apples and Oranges were the keys, not the
    > values.  Here's the correction:
    >
    >      The hashCode() methods of Apple and Orange aren't used at
    > all.  We're searching for the keys, and using their hash values
    > to guide the search.  So in both your maps, String's hashCode()
    > method is the one that's used.
    >
    >      Sorry again.
    >
    > --
    >


    No problem Eric - I caught that, the idea is now clear to me.

    Thanks for being patient with me guys. I've been using hashmap for a
    while now, but when i actually started to draw it out to understand
    equals/hashcode, I realised how clueless I was with the internal
    working.

    -Rohit
     
    , Sep 4, 2008
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Vince Darley
    Replies:
    4
    Views:
    4,544
    emilchacko
    Mar 2, 2010
  2. Joe Estock
    Replies:
    7
    Views:
    380
    Karl Heinz Buchegger
    Nov 18, 2003
  3. sarathy
    Replies:
    2
    Views:
    694
    sarathy
    Jul 17, 2006
  4. Rakesh
    Replies:
    10
    Views:
    12,265
    Mike Schilling
    Apr 8, 2008
  5. ragz_82
    Replies:
    0
    Views:
    546
    ragz_82
    Aug 5, 2009
Loading...

Share This Page