Hashtable: GetHashCode uniqueness

[Greg Bacchus]

Hi,
I'm just concerned about storing a large amount of items in a Hashtable. It
seems to me that as the number of keys in the Hashtable increases, so does
the chance of key clashes.

Does anyone know about the performance with regards to this?

Cheers
Greg

[Trev Hunter]

I don't have a direct answer to your question, but if you want to provide
your own algorithm for generating hash values, have a look at the
IHashCodeProvider interface.

I guess the chance of Key clashes depends on what you are using as a key
(string, object, integer etc?) and how the hash codes are generated. Sorry I
can't be of more help.

Trev.

"Greg Bacchus" <FB**********@spammotel.com> wrote in message
news:eW**************@TK2MSFTNGP12.phx.gbl...

Hi,
I'm just concerned about storing a large amount of items in a Hashtable. It seems to me that as the number of keys in the Hashtable increases, so does
the chance of key clashes.

Does anyone know about the performance with regards to this?

Cheers
Greg

[Jason Sobell]

Hi,
A Hashtable is the most efficient form of retrieval structure as long as
you have an efficient hash algorithm (seeded random number generator).
and the performance degradation with volume is negligible so long as the
system is using some form of extendable hashing.
Look up info on extensible hashing to see how it all works.
An example link is here:
http://feast.ucsd.edu/CSE232W99/Indexing/sld034.htm
although the 'good' hash algorithm he suggests is a poor one :)
The GetHashCode() in .Net uses a version of the Zobel/Ramakrishna algorithm
(the best performing algorithm I'm aware of) but has been adapted to
produce a guaranteed unique key (not necessary for a hash table but
sometimes required internally by .Net).
If you want to 'roll your own' for some obscure data structure then I've
attached an adaptation of the hash function below.

Cheers,
Jason
Public Function computeHashCode(ByVal StrToHash As String) As Integer
Dim c As Byte() =
System.Text.Encoding.UTF8().GetBytes(StrToHash.ToC harArray())
Dim h As Integer = 31 'seed chosen at random
Dim i As Integer
For i = 0 To c.Length - 1
' L=5, R=2 works well for ASCII input
h = (h Xor ((h * 32) + (h \ 4) + c(i))) And &HFFFF
Next
Return h
End Function
On Tue, 27 Jan 2004 09:48:26 +1300, Greg Bacchus wrote:

Hi,
I'm just concerned about storing a large amount of items in a Hashtable. It
seems to me that as the number of keys in the Hashtable increases, so does
the chance of key clashes.

Does anyone know about the performance with regards to this?

Cheers
Greg

[Jason Sobell]

Sorry, just looked at the doco and the default key from GetHashCode is
*not* guaranteed unique, but I found a page in MSDN describing the issues:
http://msdn.microsoft.com/library/de...hcodetopic.asp

Cheers,
Jason

On Tue, 27 Jan 2004 08:55:22 +1100, Jason Sobell wrote:

Hi,
A Hashtable is the most efficient form of retrieval structure as long as
you have an efficient hash algorithm (seeded random number generator).
and the performance degradation with volume is negligible so long as the
system is using some form of extendable hashing.
Look up info on extensible hashing to see how it all works.
An example link is here:
http://feast.ucsd.edu/CSE232W99/Indexing/sld034.htm
although the 'good' hash algorithm he suggests is a poor one :)
The GetHashCode() in .Net uses a version of the Zobel/Ramakrishna algorithm
(the best performing algorithm I'm aware of) but has been adapted to
produce a guaranteed unique key (not necessary for a hash table but
sometimes required internally by .Net).
If you want to 'roll your own' for some obscure data structure then I've
attached an adaptation of the hash function below.

Cheers,
Jason
Public Function computeHashCode(ByVal StrToHash As String) As Integer
Dim c As Byte() =
System.Text.Encoding.UTF8().GetBytes(StrToHash.ToC harArray())
Dim h As Integer = 31 'seed chosen at random
Dim i As Integer
For i = 0 To c.Length - 1
' L=5, R=2 works well for ASCII input
h = (h Xor ((h * 32) + (h \ 4) + c(i))) And &HFFFF
Next
Return h
End Function

[Eric Gunnerson [MS]]

There are two places where you can get collisions:

1) Two different objects can return the same number from GetHashCode()
2) Two different objects return different numbers from GetHashCode(), but
when become the same number when the two numbers are modded with the hash
table size.

The first one is an inherent feature of GetHashCode(), and depends mostly on
how good the hash code function is. With a function with good uniformity (ie
values spread over the entire int range), this shouldn't be a big issue.

The second one depends on the size of the hash table. You can change the
packing factor on the hashtable class to make the table bigger (and
therefore lookup faster), at the cost of more memory used.

In my experience, the hashtable class is pretty fast given a decent hash
function.

--
Eric Gunnerson

Visit the C# product team at http://www.csharp.net
Eric's blog is at http://weblogs.asp.net/ericgu/

This posting is provided "AS IS" with no warranties, and confers no rights.
"Greg Bacchus" <FB**********@spammotel.com> wrote in message
news:eW**************@TK2MSFTNGP12.phx.gbl...

Hi,
I'm just concerned about storing a large amount of items in a Hashtable. It seems to me that as the number of keys in the Hashtable increases, so does
the chance of key clashes.

Does anyone know about the performance with regards to this?

Cheers
Greg