Find key by value in Hashtable (or other)

[Dan]

I have the need to translate values back and forth. I have created a
Hashtable to do this because I don't care about intrinsic order and I
want it to be a fast as possible. My only concern is that I doubled
the size of my Hashtable to accommodate translating both ways. Kind of
like the following, but longer with more complicated data.

Hashtable ht = new Hashtable();
ht.Add("x1", "y1");
ht.Add("x2", "y2");
ht.Add("y1", "x1");
ht.Add("y2", "x2");

Basically, I have the feeling that this is a poor structure and I'm
missing the elegant solution that makes the above mini-example only 2
adds. To do this I would need 2 methods like the following:

val = ht.fromkey(obj key)
key = ht.fromval(obj val)

Is there some other collection that would better suit this? Is adding
each translation both ways wrong in some way?

These translation tables will not be very long. Therefore, this is
more a question of how to make the code cleaner (and me less bothered
by the inelegance) than performance.

-Dan

[Dan]

Thank you for the responses. As per your suggestions I will make it 2
tables. When originally looking at it I considered 1 table vs. 2 to be
about equivalent and chose the one I though might consume a little less
resources.

Jon,
I would like to know why when a key is equal to a value it would cause
problems. In my case every key has an equivalent value (though no key
is equivalent to it's value). It always helps for the next problem to
have a little deeper understanding. If you have a sec could you post
why this would be the case.

Thanks again,
Dan

[Bruce Wood]

Dan,

The problem Jon is referring to may also raise its head with two hash
tables.

Will it ever be possible that you will have two keys with the same
value? Or two values with the same key? Either one of these situations
will cause trouble for you, because Hashtable retains only the last
entry you set for a given key. (Or, if you use the Add method, will
throw an ArgumentException if the key is already in the table.)

If you use only one table, and you have a pair with key "a1" and value
"a1" and you say:
ht.Add("a1", "a1");
ht.Add("a1", "a1");
then the second line will throw an ArgumentException because the key
"a1" is already in the hash table.

You will have a similar problem if you happen to have two keys with the
same value:
ht1.Add("k1", "v1");
ht2.Add("v1", "k1");
ht1.Add("k2", "v1");
ht2.Add("v1", "k2"); // will fail with an ArgumentException
there are ways to code so that the fourth line doesn't fail with an
ArgumentException, but then you'll lose the information that value v1
also has key k1, because the relationship between v1 and k2 will
overwrite the previous relationship.

If you're in a situation in which the same value can have multiple keys
(or the same key can have multiple values), then you have to use a
Hashtable of ArrayLists:

Hashtable htKeyToValue = new Hashtable();
Hashtable htValueToKey = new Hashtable();

// for each key "k" and value "v":
ArrayList valueList = (ArrayList)htKeyToValue["k"];
if (valueList == null)
{
// First time we've seen this key
valueList = new ArrayList();
htKeytoValue.Add("k", valueList);
}
valueList.Add("v");
ArrayList keyList = (ArrayList)htValueToKey["v"];
if (keyList == null)
{
// First time we've seen this value
keyList = new ArrayList();
htValuetoKey.Add("v", keyList);
}
keyList.Add("k");

[Jon Skeet [C# MVP]]

Dan <da*************@yahoo.com> wrote:

Thank you for the responses. As per your suggestions I will make it 2
tables. When originally looking at it I considered 1 table vs. 2 to be
about equivalent and chose the one I though might consume a little less
resources.

I would like to know why when a key is equal to a value it would cause
problems. In my case every key has an equivalent value (though no key
is equivalent to it's value). It always helps for the next problem to
have a little deeper understanding. If you have a sec could you post
why this would be the case.

Okay, consider the situation where you have two different pairs, (x, y)
and (y, x). Using a one-table solution, the second pair to be added
would overwrite both entries of the first, despite it being a different
pair. Using a two-table solution, you end up with x->y and y->x in both
tables, each one representing a distinct pair.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

[Jon Skeet [C# MVP]]

Bruce Wood <br*******@canada.com> wrote:

The problem Jon is referring to may also raise its head with two hash
tables.

Actually, I was raising a slightly different problem. Having two pairs
with the same first part or with the same second part would indeed
cause problems whatever you do, but I was considering the situation
when there were two distinct pairs (x, y) and (y, x), which the two-
table solution can cope with, but the one-table solution can't.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

[Dan]

Thanks for the replies.

I understand Bruce's point, but in my situation I will not have
duplicate keys. I will have the situation Jon is describing for every
entry (every x->y has a y->x). So, the short answer is I will go to 2
tables. On the purely acedemic side, I have not seen the problem Jon
is refering to. The 1 table structure I have appears to be working
fine for both translations. Most failed translations would throw
exceptions based on the fact that x is a character and y is a number.
If i get back a char for y, the program will break. Just looking at
the text files for the reverse translation, I see all of the
charachters I'm looking for.

If x -> y is overwritten by y -> x that would imply to me (uninformed
as I may be) that somehow the keys and values were being stored in the
same structure. I thought all of the keys were stored as hashcodes and
associated with the reference to the value.

[Bruce Wood]

We had assumed that your keys and your values were of the same data
type. The relationship x->y _will_ overwrite y->x if you are hashing
each relationship in its original order and in its reverse order for
reverse lookup, so the relationship x->y results in _two_ entries in a
single hash table: x->y and y->x (for the reverse lookup). Then if you
have another key/value pair y->x you are in trouble. Of course, as I
said, this assumed that the keys and the values were of the same data
type, which in your case they're not. However, it's an odd design to
have a hash table with two different data types as keys.

You say that you won't have duplicate keys... but will you have
duplicate values? In other words, can you possibly have:

x -> y
z -> y

? If so, then you have to use the hash table of arrays for the reverse
lookup hash table, because you want to store the relationship

y -> x, z

[Dan]

Actualy the keys and values are all the same data type (string).
However, the y side is converted to an int by the class that is using
the hashtable. I have a converter class that can be called that wraps
up the Hashtable and other details of the conversion.

Some of the actual table:

//Positive 0 thru 9
chtConversionTable.Add("0", "{");
chtConversionTable.Add("1", "A");
....
//Negative 0 thru 9
chtConversionTable.Add("10", "}");
chtConversionTable.Add("11", "J");
....
//Reversed positive 0 thru 9
chtConversionTable.Add("{", "0");
chtConversionTable.Add("A", "1");
....
//Reversed negative 0 thru 9
chtConversionTable.Add("}", "10");
chtConversionTable.Add("J", "11");
....

Negative numbers have 10 added because there is a diference between -0
and +0 since they are trailing digits. Each no key is repeated and no
value is repeated. Keys have one and only one matching value that is
part of a seperate pair. Sorry if my posts were misleading.

Thanks,
Dan