Hashtable/Two keys

[Alexander Mueller]

Hello,

I have objects which I need to reference by two keys. Usually (with only
one key) a hashtable would be the obvious way, but unfortunately it only
supports one key. Of course I could run two hashtables with identical
values and different key types, but this doesnt seem to me to the best
solution. What would be the best way to approach that? Thanks.

 

[Cram TeXeD]

Hello,

I have objects which I need to reference by two keys. Usually (with only
one key) a hashtable would be the obvious way, but unfortunately it only
supports one key. Of course I could run two hashtables with identical
values and different key types, but this doesnt seem to me to the best
solution. What would be the best way to approach that? Thanks.

Take a look to jakarta commons collections
http://jakarta.apache.org/commons/c...ache/commons/collections/map/MultiKeyMap.html

8:0) Cram TeXeD

 

[Alexander Mueller]

Take a look to jakarta commons collections
http://jakarta.apache.org/commons/c...ache/commons/collections/map/MultiKeyMap.html

8:0) Cram TeXeD

Thanks!

 

[Alexander Mueller]

Take a look to jakarta commons collections
http://jakarta.apache.org/commons/c...ache/commons/collections/map/MultiKeyMap.html

8:0) Cram TeXeD

MultiKeyMap actually seems to do what I was looking for, however I would
like to know whether there might be any "native" Java solution which I
overlooked. I am not really liking the idea to add a 546 KB library just
because I need one class (yes, I know I could extract the necessary
files, but well ....)

Thanks again,
Alexander

 

[Kevin McMurtrie]

Hello,

I have objects which I need to reference by two keys. Usually (with only
one key) a hashtable would be the obvious way, but unfortunately it only
supports one key. Of course I could run two hashtables with identical
values and different key types, but this doesnt seem to me to the best
solution. What would be the best way to approach that? Thanks.

So make a new key class that implements equals() and hashCode() on two
Objects.

Various java.util.* classes implement deep equals() and hashCode()
methods for sets, lists, maps, collections, etc. They can be keys too.
Be careful about which ones are ordered containers and which aren't.

 

[Alexander Mueller]

So make a new key class that implements equals() and hashCode() on two
Objects.

Various java.util.* classes implement deep equals() and hashCode()
methods for sets, lists, maps, collections, etc. They can be keys too.
Be careful about which ones are ordered containers and which aren't.

This would work if it would be a key pair, but its about individual
keys. I either have on or the other, but never both for a query.

Alexander

 

[Alexander Mueller]

Take a look to jakarta commons collections
http://jakarta.apache.org/commons/c...ache/commons/collections/map/MultiKeyMap.html

8:0) Cram TeXeD

I just played around a bit with MultiKeyMap, but it seems if you store a
value with two keys, you also need exactly these two keys for retrieving
it. But I only have one.

Alexander

 

[Patricia Shanahan]

This would work if it would be a key pair, but its about
individual keys. I either have on or the other, but never
both for a query.

Alexander

If instances of the two key types can never compare equal to
each other, you could just put each value in one HashTable
twice, once with each key. However, you will probably get
better performance by using two separate tables. After all,
the point of hashing is to separate out keys that can never
be equal.

Patricia

 

[Alexander Mueller]

If instances of the two key types can never compare equal to
each other, you could just put each value in one HashTable
twice, once with each key. However, you will probably get
better performance by using two separate tables. After all,
the point of hashing is to separate out keys that can never
be equal.

Patricia

Thank you Patricia, this is actually something I just came to think of
today as well, but I am not sure how fond I am of this idea - especially
as I do not have any guarantee that the keys are never equal (one is
String, the other Long).

Separate tables are something I definitely want to avoid, not only
because of possible synchronisation issues.

Alexander

 

[Kevin McMurtrie]

This would work if it would be a key pair, but its about individual
keys. I either have on or the other, but never both for a query.

Alexander

So use: t.put(key1, value); t.put(key2, value);

 

[Alexander Mueller]

Thank you Patricia, this is actually something I just came to think of
today as well, but I am not sure how fond I am of this idea - especially
as I do not have any guarantee that the keys are never equal (one is
String, the other Long).

Although it might actually work, given that Hashtable does not only
compare on the hash code of a key object but also on the type its class.
I guess I will have to try.

Alexander

 

[Kevin McMurtrie]

If instances of the two key types can never compare equal to
each other, you could just put each value in one HashTable
twice, once with each key. However, you will probably get
better performance by using two separate tables. After all,
the point of hashing is to separate out keys that can never
be equal.

Patricia

Actually, the point of a hashing map is constant access time. There's
no need for two of them unless the keys' hashCode() methods don't work
very well.

 

[Patricia Shanahan]

Thank you Patricia, this is actually something I just
came to think of today as well, but I am not sure how
fond I am of this idea - especially as I do not have any
guarantee that the keys are never equal (one is String,
the other Long).

This is where the API Javadocs come in handy:

Long's equals "The result is true if and only if the
argument is not null and is a Long object that contains the
same long value as this object."

String's equals "The result is true if and only if the
argument is not null and is a String object that represents
the same sequence of characters as this object."

No String or Long will ever consider itself equal to an
object of the other class.

Separate tables are something I definitely want to avoid,
not only because of possible synchronisation issues.

Alexander

If synchronization is an issue for two tables, you are doing
it wrong and will get into trouble with double insertion in
a single table.

Whatever decision you make about implementation, you should
encapsulate it in a class, so that most of your program
neither knows nor cares how it is done. Suppose you used
double insertion. If this can be accessed from multiple
threads, you need to synchronize in your class, to prevent
access while the structure is inconsistent.

Patricia

 

[Lisa]

http://jakarta.apache.org/commons/collections/apidocs/org/apache/commons/col
lections/map/MultiKeyMap.html

I just played around a bit with MultiKeyMap, but it seems if you store a
value with two keys, you also need exactly these two keys for retrieving
it. But I only have one.

If you only have one you won't be able to use two to store
anything so the problem goes away.

 

[Alexander Mueller]

If you only have one you won't be able to use two to store
anything so the problem goes away.

Sorry, my statement might have been confusing . Only one key for
retrieval of course - otherwise I wouldnt have asked the question from
start .

Alexander

 

[Alexander Mueller]

No String or Long will ever consider itself equal to an
object of the other class.

So Hashtable uses equals for comparison?! I wasnt sure, somehow I
thought it would be hashCode().

If synchronization is an issue for two tables, you are doing
it wrong and will get into trouble with double insertion in
a single table.

Not synchronisation as in "synchronized" but as in general code
synchronisation .

Its not really an issue, maintaining two entries/lists/whatever just
makes me worrying a bit more than maintaining one, I guess you know what
I mean, dont you ?

Thanks again for your thoughts Patricia,
Alexander

 

[Lisa]

Sorry, my statement might have been confusing . Only one key for
retrieval of course - otherwise I wouldnt have asked the question from
start .

Alexander

If you have two to start (a and b), make a new one (c)
that is the exclusive or of what you have and use (c)
as your key. Then later, when you have only one of (a, b)
you can exclusive or the one you have with (c) to get
the one you don't have.

 

[Patricia Shanahan]

So Hashtable uses equals for comparison?! I wasnt sure,
somehow I thought it would be hashCode().

"More formally, if this map contains a mapping from a key k
to a value v such that (key==null ? k==null :
key.equals(k)), then this method returns v; otherwise it
returns null. (There can be at most one such mapping.)"
(API Javadoc for Map).

The hash code cannot be sufficient to determine equality.
There are 2**64 distinct Long values, but only 2**32 hash
code results. The exact rules are in the javadocs for
Object, but the general idea is that .equals() equality
implies equal hash codes, but not the other way round.

HashTable and HashMap map hash code values to buckets, so
given a probe key they only need to look at keys in the same
bucket to be sure of finding any key that is .equal() to the
probe.

Not synchronisation as in "synchronized" but as in
general code synchronisation .

Its not really an issue, maintaining two
entries/lists/whatever just makes me worrying a bit more
than maintaining one, I guess you know what I mean, dont
you ?

Not really, because the same difficulties apply to keeping a
single index structure with two keys. You are going to have
to think through the rules for what operations are supported
(can one delete by a single key?), write a class that does
those operations, and make sure it does them right.

 

[Alexander Mueller]

If you have two to start (a and b), make a new one (c)
that is the exclusive or of what you have and use (c)
as your key. Then later, when you have only one of (a, b)
you can exclusive or the one you have with (c) to get
the one you don't have.

..... sounds rather like a C or ASM approach

Seriously, I am not quite sure how a XOR should help in this case. I am
not after calculating an unknown value but just have the problem that I
have an object which I need to access/reference by two values (a string
and a long), however java.lang.Hashtable lets me specify only one value
as key.

If you could elaborate your XOR solution, I would really appreciate it
however.

Alexander

 

[Alexander Mueller]

Not really, because the same difficulties apply to keeping a
single index structure with two keys. You are going to have
to think through the rules for what operations are supported
(can one delete by a single key?), write a class that does
those operations, and make sure it does them right.

Okay .

Well, the solution with two identical entries will definitely also work
- its rather a personal thing. One entry for one object (as the "ideal"
solution would be) makes me feel more "comfortable" than two entries.

Alexander