[Haskell-cafe] Simple hash table creation

Brad Larsen 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?
> Michael

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 mailing list