Searching a hash by two different criteria?

Discussion in 'Java' started by Paul Tomblin, May 12, 2005.

  1. Paul Tomblin

    Paul Tomblin Guest

    I have these objects that I want to put into a hash, and then be able to
    pull them out based on either of two criteria, both Strings. So what I've
    done is to make a Key class that has both of the Strings in it, and the
    "equals" method on the Key class will return true if one String is
    non-null and equals the one in the other Key, or if the other String is
    non-null and equals the one in the other Key.

    Is that sufficient, or should I make the Key implement Comparable or
    something?


    /**
    * Key allows the object in the cache to be searched for by UUID *or*
    * by fileName.
    */
    private class Key
    {
    String fileName;
    String UUID;
    public boolean equals(Object obj)
    {
    if (obj instanceof Key)
    {
    Key otherKey = (Key)obj;
    if (UUID != null && otherKey.UUID != null)
    {
    return UUID.equals(otherKey.UUID);
    }
    if (fileName != null && otherKey.fileName != null)
    {
    return fileName.equals(otherKey.fileName);
    }
    }
    return false;
    }
    }


    --
    Paul Tomblin <> http://xcski.com/blogs/pt/
    "Integration by parts -- a very powerful technique."
    Teaching by intimidation -- also a very powerful technique.
    -- Logan Shaw, quoting Chuck Odle, his Calculus teacher
    Paul Tomblin, May 12, 2005
    #1
    1. Advertising

  2. Paul Tomblin wrote:

    > I have these objects that I want to put into a hash, and then be able to
    > pull them out based on either of two criteria, both Strings. So what I've
    > done is to make a Key class that has both of the Strings in it, and the
    > "equals" method on the Key class will return true if one String is
    > non-null and equals the one in the other Key, or if the other String is
    > non-null and equals the one in the other Key.
    >
    > Is that sufficient, or should I make the Key implement Comparable or
    > something?


    The idea is completely broken. You are ignoring the fact that the keys'
    hashcodes are of primary importance when storing values in a hash-based
    Map. Their equality to each other is relevant only in comparing two key
    objects with the same hash code. It is essential for correct operation
    of the standard Hash-based maps that keys' equals() methods be
    "consistent" with their hashCode() methods, which means that if two keys
    are equal to each other then they must have the same hash code. (The
    reverse might not be true, and generally cannot be guaranteed.) The
    only way your key class' equals() method could be consistent with its
    hashCode() method would be if the hashCode() method returned the same
    value for all instances; needless to say, that would remove all value of
    using instances as hash keys.

    The correct solution is to maintain two maps, one for each lookup criterion.

    --
    John Bollinger
    John C. Bollinger, May 12, 2005
    #2
    1. Advertising

  3. Paul Tomblin

    Paul Tomblin Guest

    In a previous article, "John C. Bollinger" <> said:
    >Paul Tomblin wrote:
    >> Is that sufficient, or should I make the Key implement Comparable or
    >> something?

    >
    >The idea is completely broken. You are ignoring the fact that the keys'
    >hashcodes are of primary importance when storing values in a hash-based


    Yeah, I just realized that about 5 seconds ago, and was about to post a
    "never mind".

    >The correct solution is to maintain two maps, one for each lookup criterion.


    Thanks for confirming it. Dammit. That means I can't use the LRU
    functions in LinkHashMap either, because something will fall off of one
    Map but not the other.

    It also turns out that extracting the fileName and UUIDs from the cached
    objects is problematic as well, so I'm going to have to put an object that
    consists of the fileName, the UUID, and the object I was going to cache
    into each Map so that I can get the UUID given the fileName and vice versa.

    --
    Paul Tomblin <> http://xcski.com/blogs/pt/
    chown -R us /yourbase
    - Simon Slavin
    Paul Tomblin, May 12, 2005
    #3
  4. Hi John,

    John C. Bollinger wrote:
    > Paul Tomblin wrote:
    >
    >> I have these objects that I want to put into a hash, and then be able to
    >> pull them out based on either of two criteria, both Strings. So what
    >> I've
    >> done is to make a Key class that has both of the Strings in it, and the
    >> "equals" method on the Key class will return true if one String is
    >> non-null and equals the one in the other Key, or if the other String is
    >> non-null and equals the one in the other Key.
    >>
    >> Is that sufficient, or should I make the Key implement Comparable or
    >> something?

    >
    >
    > The idea is completely broken.
    > [better idea]


    I think, your idea is indeed better and "cleaner".

    But of course two maps need more memory for the references stored
    inside. Also, searching in two maps takes more time than searching in
    one map.

    If that is a problem, Pauls idea might work as well (if I understand him
    correctly), if the Keys hashCode-method is implemented right. I think,
    the following should work:

    public int hashCode() {
    if(UUID!=null) {
    return UUID.hashCode()*2;
    } else {
    return filename.hashCode()*2+1;
    }
    }

    This is consistent with the rule "equals -> same hashCode" and I guess,
    it will also be a "good" hashCode (in the way that different objects
    should have different hashcodes when possible).

    Ciao,
    Ingo
    Ingo R. Homann, May 12, 2005
    #4
  5. Paul Tomblin

    Paul Tomblin Guest

    In a previous article, "Ingo R. Homann" <> said:
    >If that is a problem, Pauls idea might work as well (if I understand him
    >correctly), if the Keys hashCode-method is implemented right. I think,
    >the following should work:
    >
    >public int hashCode() {
    >if(UUID!=null) {
    > return UUID.hashCode()*2;
    >} else {
    > return filename.hashCode()*2+1;
    >}
    >}


    No, this won't help me find objects in the Map that have both UUID and
    fileName set when I only have one of the values.

    I'm afraid I'm stuck with two Maps, and also implementing my own LRU size
    limitations.


    --
    Paul Tomblin <> http://xcski.com/blogs/pt/
    What philology luser tried to hang "fear of sameness" on bigotry?
    Every time i see the word i want to kick his shins.
    -- Pat Wade, on homophobia
    Paul Tomblin, May 12, 2005
    #5
  6. Hi Paul,

    Paul Tomblin wrote:
    > In a previous article, "Ingo R. Homann" <> said:
    >
    >>If that is a problem, Pauls idea might work as well (if I understand him
    >>correctly), if the Keys hashCode-method is implemented right. I think,
    >>the following should work:
    >>
    >>public int hashCode() {
    >>if(UUID!=null) {
    >> return UUID.hashCode()*2;
    >>} else {
    >> return filename.hashCode()*2+1;
    >>}
    >>}

    >
    > No, this won't help me find objects in the Map that have both UUID and
    > fileName set when I only have one of the values.


    Ah, OK, I thought, only one of the two keys will be set, and never both.

    Now, two maps seem to be the only solution.

    Ciao,
    Ingo
    Ingo R. Homann, May 12, 2005
    #6
  7. Paul Tomblin wrote:

    > In a previous article, "John C. Bollinger" <> said:
    >>Paul Tomblin wrote:
    >>> Is that sufficient, or should I make the Key implement Comparable or
    >>> something?

    >>
    >>The idea is completely broken. You are ignoring the fact that the keys'
    >>hashcodes are of primary importance when storing values in a hash-based

    >
    > Yeah, I just realized that about 5 seconds ago, and was about to post a
    > "never mind".
    >
    >>The correct solution is to maintain two maps, one for each lookup
    >>criterion.

    >
    > Thanks for confirming it. Dammit. That means I can't use the LRU
    > functions in LinkHashMap either, because something will fall off of one
    > Map but not the other.
    >
    > It also turns out that extracting the fileName and UUIDs from the cached
    > objects is problematic as well, so I'm going to have to put an object that
    > consists of the fileName, the UUID, and the object I was going to cache
    > into each Map so that I can get the UUID given the fileName and vice
    > versa.
    >



    MultiKeyMap should help:
    http://jakarta.apache.org/commons/c...ache/commons/collections/map/MultiKeyMap.html

    and
    MultiKeyMap.decorate(new LRUMap()) creates an least recently used map.

    --
    Cheers
    grundig
    Marcin Grunwald, May 12, 2005
    #7
    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. Mohit
    Replies:
    1
    Views:
    646
    Martin Honnen
    Apr 20, 2004
  2. neocortex
    Replies:
    8
    Views:
    519
    thebjorn
    Feb 11, 2008
  3. rp
    Replies:
    1
    Views:
    493
    red floyd
    Nov 10, 2011
  4. Srijayanth Sridhar
    Replies:
    19
    Views:
    596
    David A. Black
    Jul 2, 2008
  5. Ralf Baerwaldt
    Replies:
    1
    Views:
    119
    Paul Lalli
    Jul 20, 2004
Loading...

Share This Page