Hash Tables

The hash table is the most commonly used data structure for implementing associative arrays. It features \(O(1)\) average search times, making it an efficient data structure to use for caching, indexing, and other time-critical operations.

Minimal Implementation

Hash tables are implemented by using an array of fixed size. To insert a key/value pair, the key is first hashed. Since hashes are just large integers, the hash is then taken modulo the size of the array, yielding an index. The key/value pair is then inserted into a bucket at that index.

Buckets are required because the birthday problem says that hash collisions are inevitable; so instead of each index storing a single key/value pair, it stores a bucket of pairs. In the most basic implementation, buckets are implemented by using linked lists.

Visualization of hash table insertion

Notice that the size of the bucket array doesn't limit the number of key/value pairs that can be stored in the hash table. In the above animation, the bucket array is of length 6, but 8 key/value pairs are inserted. This ratio of the number of pairs to the number of buckets is called the load factor.

\[\text{Load Factor} = \frac{\text{number of pairs}}{\text{number of buckets}}.\]

As the load factor increases, collisions are more likely to occur. As more and more collisions occur, performance degrades. In the absolute worst case, a hash table with only 1 bucket, the hash table behaves like a linked list with \(O(n)\) search, insertion, and deletion times.

Bucket length as a function of load factor

Asymptotic Complexity

See also: big O notation.

	Average	Worst
Space	\(O(n)\)	\(O(n)\)
Search	\(O(1)\)	\(O(n)\)
Insert	\(O(1)\)	\(O(n)\)
Delete	\(O(1)\)	\(O(n)\)

Sample Python implementation

This sample is a minimum implementation of a hash table whose keys must be strings. It uses DJB2 (xor variant) as its hashing function. Buckets are implemented with linked lists. (Note that Python's built-in Dictionary type is implemented with a hash table. This sample implementation is purely for academic purposes.)

class _Node(object):
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next_node = None

    def __str__(self):
        return "'{}': '{}'".format(self.key, self.value)


# a simple hashing algorithm with acceptable collision rate
def _djb2x_hash(string):
    hash = 5381
    byte_array = string.encode('utf-8')

    for byte in byte_array:
        # the modulus keeps it 32-bit, python ints don't overflow
        hash = ((hash * 33) ^ byte) % 0x100000000

    return hash


class HashTable(object):
    def __init__(self, capacity):
        self.bucket_array = [None for i in range(capacity)]
        self.capacity = capacity

    def insert(self, key, value):
        key_hash = _djb2x_hash(key)
        bucket_index = key_hash % self.capacity

        new_node = _Node(key, value)
        existing_node = self.bucket_array[bucket_index]

        if existing_node:
            last_node = None
            while existing_node:
                if existing_node.key == key:
                    # found existing key, replace value
                    existing_node.value = value
                    return
                last_node = existing_node
                existing_node = existing_node.next_node
            # if we get this far, we didn't find an existing key
            # so just append the new node to the end of the bucket
            last_node.next_node = new_node
        else:
            self.bucket_array[bucket_index] = new_node

    def lookup(self, key):
        key_hash = _djb2x_hash(key)
        bucket_index = key_hash % self.capacity

        existing_node = self.bucket_array[bucket_index]
        if existing_node:
            while existing_node:
                if existing_node.pair.key == key:
                    return existing_node.pair.value
                existing_node = existing_node.next_node

        return None

    def delete(self, key):
        key_hash = _djb2x_hash(key)
        bucket_index = key_hash % self.capacity

        existing_node = self.bucket_array[bucket_index]
        if existing_node:
            last_node = None
            while existing_node:
                if existing_node.key == key:
                    if last_node:
                        last_node.next_node = existing_node.next_node
                    else:
                        self.bucket_array[bucket_index] = existing_node.next_node
                last_node = existing_node
                existing_node = existing_node.next_node

    def debug_print(self):
        for i in range(self.capacity):
            node = self.bucket_array[i]
            print('Bucket {}'.format(i))
            if node:
                while node:
                    print('    {}'.format(node))
                    node = node.next_node
            else:
                print('    Empty')

Try it out:

hash_table = HashTable(6)
hash_table.insert('lion', 'yellow')
hash_table.insert('lizard', 'green')
hash_table.insert('horse', 'brown')
hash_table.insert('tiger', 'orange')
hash_table.insert('cardinal', 'red')
hash_table.insert('bear', 'black')
hash_table.insert('elephant', 'grey')
hash_table.insert('moose', 'brown')
hash_table.debug_print()

Bucket 0
    Empty
Bucket 1
    'lion': 'yellow'
Bucket 2
    'tiger': 'orange'
    'elephant': 'grey'
    'moose': 'brown'
Bucket 3
    'lizard': 'green'
    'cardinal': 'red'
Bucket 4
    'horse': 'brown'
Bucket 5
    'bear': 'black'

Contents