Hash Table Data Structure

A hash table is a data structure that stores data in a way where each data can be accessed via a known index, or key.

Think of a hash table as similar to an array, but the key does not need to be a number, it can be a string or really any immutable value.

This is possible because a key can be decoded into an index, which can then be used to access data at that location. We'll talk about this process later.

In Python, a hash table is represented by both a dictionary and a set.

A = {
    'alice': 24,
    'rohit': 33,
    'bob': 27
}
print(A['bob']) # prints 27

Hash tables have many synonyms. In other languages, a hash table is represented by an object or a hash map.

They're all the same.

Hash Table Big O Overview

Operation	Time
Insert	O(1)
Delete	O(1)
Lookup	O(1)

How does hashing work

As promised, let's talk about how a range of keys can be decoded into a indices in an array.

This is possible via a hash function, which is a function that accepts our key and returns the appropriate index, or location in memory.

Most computers have pretty advanced hashing techniques. But let's use our example above to demonstrate what hashing could look like.

When we access A['bob'], the key bob can be hashed as follows:

Convert each character to a number. Python's ord converts a unicode character to its unicode code representation
Sum the unicode codes of all characters
Mod % the sum by the underlying hash table size to get the location.

It's possible that the hash function could return the same location for multiple keys.

This is known as a hash collision.

Under the hood, hash tables usually handle collisions by storing the collided key's values in a linked list as the hash table entry.

That way, we don't have to overwrite collided keys and lose info.

Hash Table Pros

The biggest pro is that on average, inserting, deleting and lookups can be done in constant time O(1).

Hash Table Cons

On occasion, it's possible that a hash collision occurs, and it takes longer than constant time to retrieve data.
There's no ordering of the time that entries are added to the hash table.

Tip: Python's collections library has a neat utitlty called OrderedDict which does track the order entries are added to the hash table.

Hash Table in Python

See the implementation of a HashTable in Python, as well as the hash function _hash.

class HashNode:
    def __init__(self, key: str, value: int):
        self.key = key
        self.value = value
        self.next = None


class HashTable:
    def __init__(self, capacity):
        self.capacity = capacity
        self.hash_nodes = [None] * capacity

    def _hash(self, key: str) -> int:
        location = 0
        for letter in key:
            location += ord(letter)

        return location % self.capacity

    def insert(self, key: str, value: int):
        new_hash_node = HashNode(key, value)
        hash_node_location = self._hash(key)

        if self.hash_nodes[hash_node_location]:
            # handle collision
            node = self.hash_nodes[hash_node_location]

            while node.next:
                node = node.next

            node.next = new_hash_node
        else:
            self.hash_nodes[hash_node_location] = new_hash_node

    def get(self, key: str) -> HashNode:
        location = self._hash(key)
        node = self.hash_nodes[location]

        while node and node.key != key:
            node = node.next

        if not node:
            return None

        return node.value


hash_table_capacity = 10
A = HashTable(hash_table_capacity)
A.insert('bob', 27)
A.insert('alice', 24)
A.insert('rohit', 33)

print('bob\'s age: ', A.get('bob'))
print('alice\'s age: ', A.get('alice'))
print('rohit\'s age: ', A.get('rohit'))
print('unknown person\'s age: ', A.get('kyrie'))

1class HashNode:
2    def __init__(self, key: str, value: int):
3        self.key = key
4        self.value = value
5        self.next = None
6
7
8class HashTable:
9    def __init__(self, capacity):
10        self.capacity = capacity
11        self.hash_nodes = [None] * capacity
12
13    def _hash(self, key: str) -> int:
14        location = 0
15        for letter in key:
16            location += ord(letter)
17
18        return location % self.capacity
19
20    def insert(self, key: str, value: int):
21        new_hash_node = HashNode(key, value)
22        hash_node_location = self._hash(key)
23
24        if self.hash_nodes[hash_node_location]:
25            # handle collision
26            node = self.hash_nodes[hash_node_location]
27
28            while node.next:
29                node = node.next
30
31            node.next = new_hash_node
32        else:
33            self.hash_nodes[hash_node_location] = new_hash_node
34
35    def get(self, key: str) -> HashNode:
36        location = self._hash(key)
37        node = self.hash_nodes[location]
38
39        while node and node.key != key:
40            node = node.next
41
42        if not node:
43            return None
44
45        return node.value
46
47
48hash_table_capacity = 10
49A = HashTable(hash_table_capacity)
50A.insert('bob', 27)
51A.insert('alice', 24)
52A.insert('rohit', 33)
53
54print('bob\'s age: ', A.get('bob'))
55print('alice\'s age: ', A.get('alice'))
56print('rohit\'s age: ', A.get('rohit'))
57print('unknown person\'s age: ', A.get('kyrie'))
58

In a coding interview, you should use existing hashing libraries, such as Python's built-in dictionary or set. As long as you can articulate how it works under the hood.

6 Essential Hash Tables Coding Interview Problems

Master Hash Tables by trying the coding challenges below.

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.