Hash Table

Internal

• Data Structures

Overview

A hash table is a dynamic set that supports INSERT, DELETE and SEARCH - a dictionary.

The simplest, and the most time-efficient implementation of a hash table is a direct address table. However, this implementation is in most cases inefficient from the point of view of allocated space. A much more practical implementation uses an array whose length is proportional with the number of keys actually stored.

Direct-Address Table

Direct-address tables make sense when we can afford to allocate an array that has one element for every possible key.

Hash Table

When the number of keys actually stored is small relative to the total number of possible keys, a hash table is much more effective alternative to a direct-address table.

A hash table uses an array of size proportional to the number of keys actually stored.

The index of the array element used to store a key is computed from the key.

Collisions are possible. A collision is the situation in which more than one key maps on the same array element. There are different techniques to handle those. Chaining is the most common. Open addressing is another way.

Hash Table Time Complexity

In the worst case, searching an element in a hash table can take as long as the search in a linked list Θ(n). However, on average SEARCH, INSERT and DELETE operations take O(1).

Open Addressing

Open addressing is a technique employed when we need to deal with collisions in a hash table.

Perfect Hashing

Perfect hashing can support searches in O(1) worst-case time, when the set of keys being stored is static - the set of keys never changes once it is stored.

TODO

TODO Hash Map