Hash tables

A hash table consists of zero or more entries, each consisting of a key and a value. Given the key for an entry, the hashing function can very quickly locate the entry, and hence the corresponding value. There may be at most one entry in a hash table with a particular key, but many entries may have the same value.

<#554#><#554#> hash tables grow gracefully as the number of entries increases, so that there are always less than three entries per hash bucket, on average. This allows for fast lookups regardless of the number of entries in a table.


#note555#


#entry557#


#entry590#


#entry598#


#entry610#


#entry620#


#entry636#


#entry649#


#entry664#


#entry680#


#entry694#