[Haskell-cafe] Simple hash table creation

[Brad Larsen]

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:
<http://en.wikipedia.org/wiki/Hash_table>.

Sincerely,
Brad