Hashtable - A data structure for storing pairs. Multiple values which hash to the same value - Use collision resolution techniques: the most popular one is chaining, other methods are: Open addressing - In another strategy, called open addressing, all entry records are stored in the bucket array itself. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found. When searching for an entry, the buckets are scanned in the same sequence, until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include: linear probing in which the interval between probes is fixed (usually 1). quadratic probing in which the interval between probes increases by some constant (usually 1) after each probe. double hashing in which the interval between probes is computed by another hash function.