 A hash table is typically implemented as an array. Each array entry is a list of one or more items. A hash function maps values to indices in this array. Each Java object has a hashCode() method that gives an integer for an object. This number's modulo to the array length gives us an index into this array.
For any operation to add, remove, or check whether the set contains an item, we first index into the array (or table), and then perform the rest of the processing.
The basic idea is that, given a table and a hash function, we provide the contains(key), add(key, value), and remove(key) methods, with a constant average time. Â
The following diagram shows how a typical hash table works:
The key is run through a hash function (f()). The resulting modulo of the hash function...
