Re: Hashtable v.s. Dictionary - C# Discussion Boards

Guffa9-Jun-08 21:25

Guffa

9-Jun-08 21:25

George_George wrote:
If more then one elements falls into the same bucket (I think it means hashing conflicting), from your reply, it seems the elements of the same bucket is sorted using Comparer?

The elements are not sorted, they are just placed in buckets and the order in a bucket is not defined.

The comparer is always used when retrieving items. First the bucket is determined from the hash code, then the comparer is used to compare the desired key with the keys of the stored items (even if there is only one in the bucket).

George_George wrote:
From the Key type, we can implement the type from equality class, but how to assign the equality cmoparer for the Dictionary itself?

You can specify a comparer in the constructor to the dictionary. I actually wrote an article about that:

Dictionary with a Custom Key[^]

Despite everything, the person most likely to be fooling you next is yourself.

George_George11-Jun-08 1:19

11-Jun-08 1:19

Hi Guffa,

I take some time to study your article. It is not big, but clear enough, cool! I like it! Smile | :)

A few comments,

1.

Why you use inner class to implement the comparer interface? Why not just let the parking special key class implements the comparer interface directly? Any benefits?

2.

I want to confirm with you that,

when we use Hashtable, Object.Equals and Object.GetHashCode is used. But when we use Dictionary, IEqualityComparer.Equals and IEqualityComparer.GetHashCode is used?

3.

Equality comparer of the Dictionary is what is used as the 1st parameter of the Dictonary constructor, like your inner class ParkingSpaceKey.EqualityComparer?

regards,
George

Alan Balkany6-Jun-08 3:48

6-Jun-08 3:48

A Dictionary IS implemented as a hash table: http://msdn.microsoft.com/en-us/library/xfhwa508(VS.80).aspx[^]

So if you're using a Dictionary, you're using a hash table.

George_George8-Jun-08 22:51

8-Jun-08 22:51

Thanks Alan,

I think it is more correct to say Hashtable is a special type of Dictionary, whose key type is Object, correct?

regards,
George

Alan Balkany9-Jun-08 3:11

9-Jun-08 3:11

I think it's the other way around. A hashtable is a specific type of data structure whose key can be anything that can be represented as binary.

A Dictionary is an object that performs a function, and it can be implemented with a hashtable or other data structures. Often you see this functionality implemented with a red-black tree which can grow dynamically (e.g. in C++'s STL), as opposed to a hashtable which has a fixed size.

George_George9-Jun-08 17:01

9-Jun-08 17:01

Thanks Alan,

Alan Balkany wrote:
as opposed to a hashtable which has a fixed size.

You mean Hashtable does not grow? I think when we insert elements into Hashtable, it grows. Smile | :)

Any comments?

regards,
George

Alan Balkany10-Jun-08 3:12

10-Jun-08 3:12

A hashtable has a fixed size. When it gets too full its performance degrades, so one strategy is to then create a bigger one, and reinsert all the elements into it.

This has some overhead. Normally a hashtable allows insertion and retrieval in constant time. When the hashtable has to grow regularly, it can increase the time for insertion to O(n) or higher, depending on how often it happens.

George_George11-Jun-08 1:22

11-Jun-08 1:22

Thanks Alan,

1.

Alan Balkany wrote:
A hashtable has a fixed size. When it gets too full its performance degrades, so one strategy is to then create a bigger one, and reinsert all the elements into it.

I am confused what do you mean fixed size. I think from developer point of view, we can insert as much elements as possible into Hashtable, so no feel of limitation of fixed size. Any more descriptions or pseudo code please?

2.

Alan Balkany wrote:
When the hashtable has to grow regularly, it can increase the time for insertion to O(n) or higher, depending on how often it happens.

What means grow regularly? Why the performance degrades? Could you provide more description please?

(reference document link is also ok, I am interested in this topic)

regards,
George

Alan Balkany11-Jun-08 3:23

11-Jun-08 3:23

Here's link that explains more: http://en.wikipedia.org/wiki/Hash_table[^]

Hashing transforms a key into the address of a slot to store the data in. There are a fixed number of slots. When multiple keys are mapped to the same slot, there are different ways of handling it, all of which take time.

Type "hash table" into Google, and you'll get much more than I can explain here.

George_George11-Jun-08 3:33

11-Jun-08 3:33

How about my question item 1?

--------------------
I am confused what do you mean fixed size. I think from developer point of view, we can insert as much elements as possible into Hashtable, so no feel of limitation of fixed size. Any more descriptions or pseudo code please?
--------------------

Fixed size means limited size?

regards,
George

Alan Balkany11-Jun-08 3:36

11-Jun-08 3:36

Look at the link I gave, type "hash table" into Google and look at some of those references, and see if they answer your questions. There's a lot of material on hash tables out there, with more complete explanations than I can give you here.

George_George11-Jun-08 16:40

11-Jun-08 16:40

Thanks Alan,

I read the link, clarified a lot of things. I often heard people talk about re-hash, does it mean the same thing of "Table resizing" in the link you mentioned?

regards,
George

Alan Balkany12-Jun-08 3:07

12-Jun-08 3:07

It might. I haven't heard that term in the context of hash tables.

George_George12-Jun-08 3:13

12-Jun-08 3:13

Thanks Alan,

Your reply is clear. I want to check why do you think before Hashtable is fixed size? If the load factor is large enough (e.g. HashMap in Java is 75%), it will be resized to increase its size -- so not fixed. Could you clarify please?

regards,
George

Alan Balkany12-Jun-08 3:17

12-Jun-08 3:17

If you increase the size of the hash table, you also have to change the hashing function to produce keys for this larger size. When you do this, the elements you've already added to the hash table must go to different slots. So every element must be re-inserted in the new larger table.

This process creates a new hash table and replaces the old one. The old one wasn't resized.

George_George12-Jun-08 23:26

12-Jun-08 23:26

Thanks Alan,

So, the root cause is hash function is dependent on table size? Smile | :)

regards,
George

Alan Balkany13-Jun-08 3:14

13-Jun-08 3:14

Yes.

George_George15-Jun-08 19:46

15-Jun-08 19:46

Thanks Alan!

You mentioned before -- "When the hashtable has to grow regularly, it can increase the time for insertion to O(n) or higher, depending on how often it happens.". "It" means? Smile | :)

regards,
George

Alan Balkany16-Jun-08 3:04

16-Jun-08 3:04

Growing regularly. Every time the hashtable "grows", all elements that have been inserted must be reinserted into the new hashtable. When a hashtable has n elements, it takes n operations to copy them, as opposed to a single operation to insert one element.

George_George17-Jun-08 23:24