Accessing a spezific key in a Hashtable

[Guest]

Hello,

I´ve implemented a Hashtable with Int-Keys and Double Values.

Now I want to get the i-th Int-Key of my hashtable.
How do I do that?

I tried it like that:

ICollection intKeys = myHashtable.Keys;
int key = intKeys;

But this does not work, because I cannot access an ICollection like an
array with [].

So how do I do it?


Regards,

Martin

 

[Bruce Wood]

Hello,

I´ve implemented a Hashtable with Int-Keys and Double Values.

Now I want to get the i-th Int-Key of my hashtable.
How do I do that?

I tried it like that:

ICollection intKeys = myHashtable.Keys;
int key = intKeys;

But this does not work, because I cannot access an ICollection like an
array with [].

Well, first of all you have to identify what you mean by the i-th key.
Hashtable has no such concept: the entries are not in any particular
order.

If you want to enumerate across the entire collection, you can use
foreach with myHashtable, myHashtable.Keys, or myHashtable.Values.

If you're expecting the keys to be in particular order (say, numerical
order by integer key) then use a SortedList, not a Hashtable, and you
will be able to use the [] notation.

If neither of these is your case, then please explain why you want the
i-th key, and what you expect that will return to you.

 

[=?ISO-8859-1?Q?Martin_P=F6pping?=]

If neither of these is your case, then please explain why you want the
i-th key, and what you expect that will return to you.

My int keys consist of a random order of int (1325,2313,2335).
The problem is now, that I want to have for example the 2nd value (2313).

But you are right... I think this would not work with a hashtable
because of the hashing order.

Anyway... thank you very much!


Regards,

Martin

 

[Bruce Wood]

My int keys consist of a random order of int (1325,2313,2335).
The problem is now, that I want to have for example the 2nd value (2313).

But you are right... I think this would not work with a hashtable
because of the hashing order.

Then use System.Collections.SortedList. SortedList is just a Hashtable
that also maintains the entries sorted by key value. You can do all of
the hashing you used to do, plus index into the i-th entry in order by
key, which is what you want to do.

 

[Chris Mullins]

If this is what you want to do, then a HashTable isn't the datastructure
you're looking for.

There is no concept of "order" in a hash table. To access the "i-th" key,
you would expect this to be the 3rd key/value pair added into the hashtable.
You could also reasonably expect the "i-th" key to be the 3rd smallest
integer in the hashtable (aka: A sorted valued). The hashtable, however, has
no concept of this.

You should look at other datastructures, or using a few datastructures in
conjunction with each other, to solve your problem.

The Sorted List may be more what you're looking for.

 

[Brian Gideon]

Martin,

I could be wrong, but what it sounds like to me is that you want a
dictionary (meaning key-value pair) that preserves temporal ordering.
If that's the case then you'll have to whip up your own in 1.1 or use
the KeyedCollection in 2.0.

Brian

 

[Thomas T. Veldhouse]

Then use System.Collections.SortedList. SortedList is just a Hashtable
that also maintains the entries sorted by key value. You can do all of
the hashing you used to do, plus index into the i-th entry in order by
key, which is what you want to do.

I do believe you lose the constant lookup times of a hashtable when using a
sorted list; if that is important to you.

 

[Thomas T. Veldhouse]

I do believe you lose the constant lookup times of a hashtable when using a
sorted list; if that is important to you.

It appears that I was incorrect.

"The SortedList generic class is a binary search tree with O(log n) retrieval,
where n is the number of elements in the dictionary. In this, it is similar to
the SortedDictionary generic class. The two classes have similar object
models, and both have O(log n) retrieval. Where the two classes differ is in
memory use and speed of insertion and removal:

SortedList uses less memory than SortedDictionary.

SortedDictionary has faster insertion and removal operations for unsorted
data, O(log n) as opposed to O(n) for SortedList.

If the list is populated all at once from sorted data, SortedList is faster
than SortedDictionary."

However, I am correct in indicating that simply using a Dictionary (or
Hashtable) will be much faster than using a SortedList.

"The Dictionary generic class provides a mapping from a set of keys to a set
of values. Each addition to the dictionary consists of a value and its
associated key. Retrieving a value by using its key is very fast, close to
O(1), because the Dictionary class is implemented as a hash table."

O(1) is much faster than O(log n) or O(n). Lookup time is constant in all
cases, but with the SortedLists it is based upon the size of the list.

 

[Brian Gideon]

It appears that I was incorrect.

No, you're right. Hashtable and Dictionary have average-case
retrieval, insertion, and deletion complexity near O(1) and a
SortedList does not. You even said as much at the end your post

"The SortedList generic class is a binary search tree with O(log n) retrieval,
where n is the number of elements in the dictionary. In this, it is similar to
the SortedDictionary generic class. The two classes have similar object
models, and both have O(log n) retrieval. Where the two classes differ is in
memory use and speed of insertion and removal:

SortedList uses less memory than SortedDictionary.

SortedDictionary has faster insertion and removal operations for unsorted
data, O(log n) as opposed to O(n) for SortedList.

If the list is populated all at once from sorted data, SortedList is faster
than SortedDictionary."

However, I am correct in indicating that simply using a Dictionary (or
Hashtable) will be much faster than using a SortedList.

"The Dictionary generic class provides a mapping from a set of keys to a set
of values. Each addition to the dictionary consists of a value and its
associated key. Retrieving a value by using its key is very fast, close to
O(1), because the Dictionary class is implemented as a hash table."

O(1) is much faster than O(log n) or O(n). Lookup time is constant in all
cases, but with the SortedLists it is based upon the size of the list.

For what's worth, SortedList is implemented with an array,
SortedDictionary with a red-black binary search tree (probably
top-down), Dictionary with chaining for collision resolution, and
Hashtable with rehashing for collision resolution.