[cap-talk] Hashtable costs

[David-Sarah Hopwood]

Bill Frantz wrote:
> All of the hash tables I have used have been designed to have more than one
> entry/chain head. These tables are designed to incur an O(n) cost. Is there
> an example of a real-world O(1) hash table? It would have to have a
> guarantee that no chain was more than one element long.

<http://en.wikipedia.org/wiki/Perfect_hashing>
<http://en.wikipedia.org/wiki/Cuckoo_hashing>

-- 
David-Sarah Hopwood ⚥