[Haskell-cafe] Simple hash table creation
brad.larsen at gmail.com
Tue Nov 17 16:36:12 EST 2009
On Tue, Nov 17, 2009 at 4:22 PM, michael rice <nowgate at yahoo.com> wrote:
> So, what you're telling me is, my dummy hash function IS being used, and because of collisions the other values are placed in different locations?
If Data.HashTable is implemented using separate chaining, then all the
key/value pairs would be hashed to the same bucket (hash value 7). If
a different scheme is used, then hash collisions would be resolved in
a different way, e.g., through linear probing. Regardless of the
collision resolution scheme used, excessive hash collisions are bad,
and are what can cause the worst-case time complexity of hash table
operations (in most implementations) to be O(n).
The Wikipedia page on hash tables isn't bad:
More information about the Haskell-Cafe