Hashing

Hash table is implemented as an array that allows random access. There are two common ways to deal with key collisions:

• Chaining: colliding elements are put in a linked list in each slot of table. This increase the total size of the data structure. The expected running time for search is \(\Theta(1 + \alpha)\) where \(\alpha\) = # keys stored in the table / # slots in table, i.e., the load factor.
• Open addressing:  the hash function takes two arguments, the key k and the trial number i. The hash function has the property that if we keep trying h(k, i), we will even hit all slots of the table. An example of such a hash function is double hashing: \(h(k, i) = h_1(k) + i\cdot h_2(k)\)