Hashtable/Two keys

[Virgil Green]

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.

Without testing it, let me propose this. Create a key class that stores your
Long and String whose equals() method will return true if either of the two
class members of the same type matches. The problem I foresee is
implementing a hashCode that will be equal whether the key object has one,
the other, or both member values set. I guess you could rely solely on
equals() and always return a constant hashCode. That would meet the
contract, but I don't know what the consequences would be.

 

[Andrew McDonagh]

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

Whats wrong with simply added the Value object to the map twice, once
with one key, second with the other key?

public void addToMap(Object key1, Object key2, Object Value) {
theMap.put(key1, value);
theMap.put(key2, value);
}

 

[Bjorn Abelli]

...

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.

I'm curious about how these two keys relate to each other?

One approach could be to subclass Hashtable to simply include an "internal"
mapping of the key values to each other.

// Bjorn A

 

[Alexander Mueller]

Without testing it, let me propose this. Create a key class that stores your
Long and String whose equals() method will return true if either of the two
class members of the same type matches. The problem I foresee is
implementing a hashCode that will be equal whether the key object has one,
the other, or both member values set. I guess you could rely solely on
equals() and always return a constant hashCode. That would meet the
contract, but I don't know what the consequences would be.

Thanks Virgil, thats a good suggestions.

Alexander

 

[Patricia Shanahan]

Without testing it, let me propose this. Create a key
class that stores your Long and String whose equals()
method will return true if either of the two class
members of the same type matches. The problem I foresee
is implementing a hashCode that will be equal whether the
key object has one, the other, or both member values set.
I guess you could rely solely on equals() and always
return a constant hashCode. That would meet the contract,
but I don't know what the consequences would be.

The main consequence would be extremely bad hash table
performance, to the point were it would have been better to
use an ArrayList to manage the keys and search it sequentially.

Hash tables depend for their performance on splitting the
keys among many buckets, using the hash code to select the
bucket. The code for get takes the probe key, gets its hash
code, and looks only in the bucket to which that code is
mapped.

If, and only if, the number of keys assigned to a bucket is
bounded by a constant, the search is O(1). If all keys are
assigned to the same bucket, as would be the case for
constant hash code, the search is O(n) where n is the number
of keys in the hash table.

Generally, it is a very bad mistake to use a hash table if
you don't have a good hash function, and returning a
constant is the worst function that nominally meets the
contract.

Patricia

 

[Lisa]

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

Yes it is like C or ASM. Thinking a little more, I see that
you would not likely have (c) when you need to access the data,
so this would not work then. How about putting the data in twice,
once with each key. Or how about having a separate hashtable
that you use to get the other key.

 

[Alexander Mueller]

Yes it is like C or ASM. Thinking a little more, I see that
you would not likely have (c) when you need to access the data,
so this would not work then. How about putting the data in twice,
once with each key. Or how about having a separate hashtable
that you use to get the other key.

As I mentioned in another posting in this thread, this is actually
something I tried to avoid but meanwhile I went for this solution and so
lets see

Thanks in any way!

Alexander

 

[Chris Uppal]

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.

I understand your unease with having two hashtables -- duplication is nearly
always a sign of a (at best) risky program design. However, in this case, I
think your instincts are leading you astray.

I.e. I don't think there is any way that you'll find a solution that is /any/
of:

- simpler
- more matainable
- faster
- takes smaller space

than the solution using two lookup tables.

-- chris

 

[Kevin McMurtrie]

I understand your unease with having two hashtables -- duplication is nearly
always a sign of a (at best) risky program design. However, in this case, I
think your instincts are leading you astray.

I.e. I don't think there is any way that you'll find a solution that is /any/
of:

- simpler
- more matainable
- faster
- takes smaller space

than the solution using two lookup tables.

-- chris

Eh?

A single Hashtable for two keys is simpler, easier to maintain than two,
exactly the same speed, and takes very slightly less space.

Remember, hashed lookup tables have a constant lookup time as long as
the hashing is good. 5 keys or 500000 keys is all the same.

 

[Chris Uppal]

A single Hashtable for two keys is simpler, easier to maintain than two,
exactly the same speed, and takes very slightly less space.

I don't buy either "simpler", or "easier to maintain". It's a technique that
runs counter to programmer's expectations, and as such should be shunned unless
there's a good reason for it. As an example, the code for iterating over the
elements (values) of the table would be considerably more convoluted than a
programmer would expect if they hadn't realised that you were playing games
with the table's contents.

I can buy "very slightly less space" if you are referring to the constant space
overheads of the two datastructures. I presume that you are not advancing that
as an actual /advantage/ of merging the two indexes, but just happily (and
properly) nit-picking ;-)

I'll enter two caveats against "exactly the same speed". One is that increasing
the capacity and occupancy of a hash table in tandem is only "free" for as long
as you don't exhaust the space of hash values. Obviously the bigger the table,
the more likely that is to happen. The second is that I don't think it's
likely to be true in practice once when you take data cache effects into
account. OTOH, the mix of two types of key might give rise to more even
spreading of the hash values (or, there again, it might be worse...).

Then add in the fact that either:
the two sets of keys have distinct types
or:
the two sets of keys no not have distinct types
both of which cause problems. In the first case you can't express the type of
the table using generics (though I admit that what bothers me is more that it
conceptually messy than that it is statically "unsafe"). In the second case
you have to worry about the possibility of the same "key" appearing twice in
two roles.

I think that all merging the tables is likely to achieve is a significantly
more convoluted expression of a lookup that would be essentially as efficient
using two tables.

-- chris