Strengthening Hash Tables with Arrays (ArrayHashMap)

Prerequisites

You should already be familiar with the following before continuing:

Core principles of hash tables

In the previous chapter we strengthened a hash table with a doubly linked list to obtain a LinkedHashMap that preserves insertion order of keys.

Linked lists are not the only structure that can improve a hash table. Arrays, which are closely related to lists, can serve the same purpose.

Adding a randomKey() API

Consider the following exercise: starting from the ordinary hash-table interface, add a new method randomKey() that returns a uniformly chosen key in (O(1)) time:

interface Map<K, V> {
    // Obtain the value for a key, O(1)
    V get(K key);

    // Insert or update a key-value pair, O(1)
    void put(K key, V value);

    // Remove a key-value pair, O(1)
    void remove(K key);

    // Test whether a key is present, O(1)
    boolean containsKey(K key);

    // Return every key, O(N)
    List<K> keys();

    // New API: return a random key in O(1) time
    K randomKey();
}

Uniform randomness

“Random” normally means uniform random: every element is equally likely to be chosen. With (n) elements the probability of selecting any particular one must be exactly (1/n).

How would you implement the new method? The requirement looks simple, yet a correct solution is surprisingly subtle.

A hash table is fundamentally an array (the “table”). Selecting a random key therefore feels like selecting a random element from an ordinary array.

When the array is compact (no gaps) the operation is trivial: draw a random index in the half-open interval ([0, size)) and return the element at that position.

import random

def randomElement(arr: List[int]) -> int:
    # Produce a random index in [0, len(arr))
    return arr[random.randint(0, len(arr) - 1)]

The algorithm runs in (O(1)) time and is perfectly uniform. It relies, however, on the array being free of holes. For the concrete array [1, 2, 3, 4] every generated index points to a live element.

Holes destroy the guarantee. Consider [1, 2, None, 4]. If the random index lands on the empty slot, what should the algorithm do?

One naïve repair is to scan linearly (left or right) until a non-empty cell is found:

# Pseudo-code: return a non-empty random element
def randomElement(arr):
    r = random.Random()
    i = r.randrange(len(arr))
    while arr[i] is None:
        # Index hit a hole; continue searching circularly
        i = (i + 1) % len(arr)
    return arr[i]

Two fatal defects appear:

The loop can examine every cell in the worst case, raising the complexity to (O(n)).

The fixed scan direction biases the distribution. For the example above the three live elements are chosen with probabilities (1/4), (1/4) and (2/4) respectively—not uniform.

An alternative is to keep drawing fresh random indices until a non-empty cell appears:

# Pseudo-code: keep resampling until a live element is found
def randomElement(arr):
    r = random.Random()
    i = r.randrange(len(arr))
    while arr[i] is None:
        i = r.randrange(len(arr))
    return arr[i]

Uniformity is restored, yet the running time now depends on the random number generator and is therefore not guaranteed (O(1)).

Selecting a random element from an array that contains holes is already non-trivial. A hash table makes the problem harder still:

With open addressing the underlying table is precisely a sparse array.

With chaining each slot holds a linked list; a random index must be followed by a random node inside that list.

Even if both steps are individually uniform, the overall distribution is not. In a typical chaining illustration the keys stored in a three-node chain each have probability (1/6), while keys stored in a two-node chain have probability (1/4).

A note on probabilistic algorithms

Randomized algorithms appear both in theory and in practical systems. Later chapters will examine classic techniques used in games and weighted sampling; those details are not required here.

The only obvious remaining approach is to materialize every key into a dense array by calling keys() and then pick a random entry. That solution is (O(n)) and therefore unacceptable.

At this point it is easy to feel stuck. The difficulty is typical of classic data-structure design problems; inventing a solution on the spot during an interview is rarely realistic. The rest of the article shows how an auxiliary array can be used to obtain an (O(1)) randomKey() while preserving the other hash-table operations.

Design idea

The earlier discussion of chaining was intentionally misleading. As with the linked-list enhancement, becoming entangled in the concrete collision-resolution strategy obscures the essential picture.

Treat the hash table as a black-box key-value store. The only property that matters is that it supports (O(1)) insertions, deletions and lookups.

A compact array already supports uniform random access. Therefore the simplest way to obtain a random key is to keep an auxiliary array that stores every key currently present in the map:

# High-level sketch
class MyArrayHashMap:
    def __init__(self):
        # Compact list of all keys
        self.arr = []
        self.map = {}

    def put(self, key, value):
        if key not in self.map:
            self.arr.append(key)
        self.map[key] = value

    def get(self, key):
        return self.map[key]

    def randomKey(self):
        return random.choice(self.arr)

    def remove(self, key):
        # Still to be written
        ...

The sketch guarantees both uniformity and (O(1)) time for randomKey. The missing piece is deletion: removing a key from the map is easy, but removing an arbitrary element from the middle of a dense array normally costs (O(n)) because subsequent elements must be shifted.

Deleting an arbitrary array element in (O(1)) time

The shift can be avoided by swapping the target element with the last element and then popping the last position. A pop at the end of an array is (O(1)).

The price is that the relative order of the remaining elements is scrambled. In the present setting that order is irrelevant, so the swap is harmless.

Concrete illustration: given arr = [1, 2, 3, 4, 5] and the desire to delete 2, first exchange 2 with the final element to obtain [1, 5, 3, 4, 2]. A single pop then removes 2 while restoring contiguity.

The only remaining obstacle is locating the index of the element that must be swapped. A linear scan would again be (O(n)). Because a hash table is already available, we can store the mapping from each key to its current index inside the auxiliary array. Look-ups of that index then become (O(1)).

With that mapping the whole design is complete.

Implementation

import random

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val

class MyArrayHashMap:
    def __init__(self):
        # Maps each key to the index where it currently lives in arr
        self.map = {}
        # Dense storage of key-value nodes
        self.arr = []

    def get(self, key):
        if key not in self.map:
            return None
        index = self.map[key]
        return self.arr[index].val

    def put(self, key, val):
        if self.containsKey(key):
            # Update an existing entry
            i = self.map[key]
            self.arr[i].val = val
            return

        # Insert a brand-new entry at the end
        self.arr.append(Node(key, val))
        self.map[key] = len(self.arr) - 1

    def remove(self, key):
        if key not in self.map:
            return
        index = self.map[key]
        node = self.arr[index]

        # Exchange the target node with the final node
        last = self.arr[-1]
        self.arr[index] = last
        self.arr[-1] = node

        # Repair the index recorded for the node that moved
        self.map[last.key] = index

        # Discard the now-redundant final position
        self.arr.pop()

        # Forget the deleted key
        self.map.pop(node.key)

    def randomKey(self):
        n = len(self.arr)
        randomIndex = random.randint(0, n - 1)
        return self.arr[randomIndex].key

    def containsKey(self, key):
        return key in self.map

    def size(self):
        return len(self.map)

if __name__ == '__main__':
    map = MyArrayHashMap()
    map.put(1, 1)
    map.put(2, 2)
    map.put(3, 3)
    map.put(4, 4)
    map.put(5, 5)

    print(map.get(1))          # 1
    print(map.randomKey())

    map.remove(4)
    print(map.randomKey())
    print(map.randomKey())

The ArrayHashMap structure is now finished. An ArrayHashSet can be obtained by a thin wrapper around the same class; the wrapper itself is omitted here.