Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Searching a hash by two different criteria?

Reply
Thread Tools

Searching a hash by two different criteria?

 
 
Paul Tomblin
Guest
Posts: n/a
 
      05-12-2005
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 <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
John C. Bollinger
Guest
Posts: n/a
 
      05-12-2005
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
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
 
 
 
Paul Tomblin
Guest
Posts: n/a
 
      05-12-2005
In a previous article, "John C. Bollinger" <(E-Mail Removed)> 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 <(E-Mail Removed)> http://xcski.com/blogs/pt/
chown -R us /yourbase
- Simon Slavin
 
Reply With Quote
 
Ingo R. Homann
Guest
Posts: n/a
 
      05-12-2005
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

 
Reply With Quote
 
Paul Tomblin
Guest
Posts: n/a
 
      05-12-2005
In a previous article, "Ingo R. Homann" <(E-Mail Removed)> 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 <(E-Mail Removed)> 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
 
Reply With Quote
 
Ingo R. Homann
Guest
Posts: n/a
 
      05-12-2005
Hi Paul,

Paul Tomblin wrote:
> In a previous article, "Ingo R. Homann" <(E-Mail Removed)> 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

 
Reply With Quote
 
Marcin Grunwald
Guest
Posts: n/a
 
      05-12-2005
Paul Tomblin wrote:

> In a previous article, "John C. Bollinger" <(E-Mail Removed)> 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/co...ltiKeyMap.html

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

--
Cheers
grundig
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash of hash of hash of hash in c++ rp C++ 1 11-10-2011 04:45 PM
Hash#select returns an array but Hash#reject returns a hash... Srijayanth Sridhar Ruby 19 07-02-2008 12:49 PM
*hash is different from hash.to_a? Trans Ruby 2 11-28-2007 11:32 PM
Searching an example for a defined hash value of a nonexisting hash key Ralf Baerwaldt Perl Misc 1 07-20-2004 03:05 PM
Sort Hash o Hash accordint to two keys Malik Yousef Perl Misc 9 05-07-2004 06:22 PM



Advertisments