Contents    Page-10    Prev    Next    Page+10    Index   

Hash Table

Symbols are stored in a hash table, indexed by a hash function applied to the key value ( e.g., multiply a symbol by itself and take some bits from the middle of the product). The hash function always produces the same value for a given symbol, but is otherwise ``random''. If there is a collision (two different symbols hash to the same value), it is necessary to rehash ( e.g., try the next place in the table).

Insert: O(1) Depends on table fullness
Search: O(1) Depends on table fullness

The expected time is only 5 comparisons for a table that is 90% full; time depends on fullness but not on table size.