** Hashing with Buckets**

* Hashing with buckets*, also called * separate chaining*,
is a simple method that works well. The array that is indexed by
the hash function points to a linked list of entries for the
items with that hash value; such a list is called a * bucket*.

Insertion is simply a push of a new linked list entry onto the list given by the array entry indexed by the hash value. Search is linked list search on that entry.

Expected time is * n / ( 2 · tablesize ) *.
Although formally this is *O(n)*, in practice one can make it
*O(1)* by making *tablesize* large enough.

If *tablesize* is *n _{max} / 10*, the expected time would be 5
comparisons, but the dedicated table size would not be too large.