CODEWITHSUNDEEP
c#c++data-structures
tvr
tvr

Reputation: 4575

Dictionary/hash_map key size

The hash value for key is caculated and is divided by a prime number. In general, Is there any standard prime number (say for 32/64 bit) for this?

My understanding is the hashtable is not resizable/adjustable and its internal array depends on this. If I have a hashtable for only 5 elements will there be waste in key space?

Edit: I should have framed this better. What is general approach followed in c++ hash_map (boost) or C# Dictionary

Upvotes: 0

Views: 559

Answers (3)

VinayC
VinayC

Reputation: 49185

Why not use Reflector to see C# Dictionary or HashTable implementations? Both answers by Greg and Jim are correct speaking in general terms and for C# implementation.

In summary, C# Dictionary implementation uses a prime number (that is greater than its capacity) as a size of internal bucket array and uses it for dividing the hash code. Whenever, there is need to resize internal array, it uses twice the existing capacity as a new capacity.

Upvotes: 1

Greg Hewgill
Greg Hewgill

Reputation: 992927

In fact, hash tables sizes can be adjustable automatically. What you might do is allocate an array of size N, using a hash modulo N (some prime number) for indexing into the array. If you keep track of the density of your allocation, then when it increases beyond some threshold you can allocate a new array of size N1 (some larger prime number), and copy over each element from the old array, applying the hash function with the new modulo to find its place in the new hash table. Finally you deallocate the old array and use the new, larger array.

Upvotes: 2

Jim Mischel
Jim Mischel

Reputation: 133975

Often, the prime number is used as the size of the internal array. That is, if somebody asks for a hash table of 100 items, you pick the next prime that's >= 100 and that's the size. In that case, you'd have a table size of 101.

But that's not the only way to do it.

Upvotes: 1

Related Questions