Hash Table

A Hash Table is a data structure that implements an associative array, mapping keys to values using a hash function. It provides average O(1) time complexity for insertion, deletion, and lookup operations.

Hash Table Visualization

Key
0
—
Key
1
—
Key
2
—
Key
3
—
Key
4
—
Key
5
—
Key
6
—
Key
7
—
Key
8
—
Key
9
—
Hash Function: value % 10

Complexity

Time Complexity: O(1) average, O(n) worst for insert/delete/search
Space Complexity: O(n)

Pseudocode

class HashTable:
  function hash(key):
    return hash_function(key) % table_size
  
  function insert(key, value):
    index = hash(key)
    table[index] = value
  
  function get(key):
    index = hash(key)
    return table[index]