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 nmax / 10, the expected time would be 5 comparisons, but the dedicated table size would not be too large.
Contents Page-10 Prev Next Page+10 Index