Hashing

The Comparison Lower Bound — Why $\Theta(\log n)$ Is the Ceiling

Any deterministic comparison search algorithm can be modelled as a binary decision tree. Each internal node is a comparison between two items — the outcome is True or False, so the tree branches in exactly two directions. Each leaf represents a distinct output: either "found item $x$" or "not found." With $n$ items stored, there are $n + 1$ possible outputs, so the decision tree needs at least $n + 1$ leaves.

A binary tree with at least $n + 1$ leaves has height at least $\lceil \log_2(n+1) \rceil - 1 = \Omega(\log n)$. The height is the length of the longest root-to-leaf path — which is the worst-case number of comparisons. Therefore:

Sorted arrays and balanced BSTs achieve this bound. But what if we are not limited to comparisons? The Word-RAM model has one operation with super-constant branching factor: random memory access. Given an address, we can read the value there in $\Theta(1)$ — branching factor equal to the size of memory itself. This is the doorway hashing walks through.

Direct Access Arrays — $\Theta(1)$ Find, Catastrophic Space

The simplest exploitation of random access: give every item an integer key $k \in \{0, \ldots, u-1\}$ and store item $x$ at index $x.\text{key}$ in an array of length $u$. Finding any item is exactly one array access — $\Theta(1)$. No comparisons at all.

class DirectAccessArray:
    def __init__(self, u):          # O(u) space — the problem
        self.A = [None] * u

    def find(self, k):              # O(1) — just index
        return self.A[k]

    def insert(self, x):            # O(1)
        self.A[x.key] = x

    def delete(self, k):            # O(1)
        self.A[k] = None

    def find_next(self, k):         # O(u) — must scan
        for i in range(k, len(self.A)):
            if self.A[i] is not None:
                return self.A[i]

    def find_max(self):             # O(u) — must scan
        for i in range(len(self.A) - 1, -1, -1):
            if self.A[i] is not None:
                return self.A[i]

# Problem: if keys are 10-letter strings, u = 26^10 ≈ 1.4 × 10^14
# Storing even 1 bit per slot = 17.6 TB. Completely unusable.

#include <vector>
#include <optional>
using namespace std;

template<typename T>
class DirectAccessArray {
    vector<optional<T>> A;
public:
    DirectAccessArray(int u) : A(u) {}  // O(u) space — the problem

    optional<T> find(int k)  { return A[k]; }     // O(1)
    void insert(int k, T x)  { A[k] = x; }        // O(1)
    void remove(int k)       { A[k] = nullopt; }   // O(1)

    // Order operations require O(u) scan — no structure to exploit
    optional<T> find_max() {
        for (int i = A.size()-1; i >= 0; --i)
            if (A[i]) return A[i];
        return nullopt;
    }
};

The space cost is $\Theta(u)$ — the size of the entire key universe, regardless of how many items you actually store. If $n \ll u$, this is catastrophically wasteful. For NSE instrument tokens (32-bit integers), $u = 2^{32} \approx 4 \times 10^9$. Allocating that array takes 16 GB for 4-byte pointers, for storing perhaps 9,000 instruments. We need a smarter approach.

Hashing — Compressing the Key Space

The fix: instead of an array of size $u$, use an array of size $m = \Theta(n)$ — just enough slots for the items you actually store. Map each key $k$ to a slot via a hash function $h : \{0, \ldots, u-1\} \to \{0, \ldots, m-1\}$.

Collision Resolution — Chaining

When two keys hash to the same slot, we need somewhere to put the second item. The cleanest solution: at each slot, store not a single item but a chain — a small data structure (typically a linked list) holding all items that hash to that slot.

To find key $k$: compute $h(k)$, go to slot $h(k)$, then search the chain there for $k$. If chains are short, all operations are $O(1)$ plus the chain search cost. The central question is: how long are the chains?

If $n$ items are distributed roughly evenly across $m = \Theta(n)$ slots, each chain has expected length $n/m = \Theta(1)$. The ratio $\alpha = n/m$ is called the load factor. As long as $\alpha = O(1)$, all operations run in $O(1)$ expected time.

What Makes a Good Hash Function?

Division method (bad in general): $h(k) = k \bmod m$. Simple and fast. Works well when keys are uniformly distributed. Terrible when keys share structure — if all instrument tokens are multiples of some number that divides $m$, they all collide. A determined adversary who knows your hash function can construct inputs that all hash to the same slot, forcing $\Theta(n)$ chains.

The fix: do not use a fixed hash function. Choose one randomly from a large family of functions. Then no adversary can predict which function you are using.

Why Universality Implies Short Chains — The Probability Argument

Fix a key $k_i$ and a universally random hash function $h$. How many other keys collide with $k_i$? For each other key $k_j$, define the indicator random variable:

The chain length at slot $h(k_i)$ is $X_i = \sum_{j} X_{ij}$. By linearity of expectation:

Since $m = \Omega(n)$, the load factor $\alpha = n/m = O(1)$, so:

Expected chain length is $O(1)$ — regardless of the input keys, as long as $h$ is chosen randomly from a universal family. All hash table operations run in $O(1)$ expected time.

from random import randint

class Hash_Table_Set:
    def __init__(self):
        self.A      = []          # array of chains (linked lists)
        self.size   = 0           # number of items stored
        self.p      = 2**31 - 1  # large prime > key universe
        self.a      = randint(1, self.p - 1)  # random multiplier
        self._resize(0)

    def _hash(self, k, m):        # universal hash: O(1)
        return ((self.a * k) % self.p) % m

    def _resize(self, n):         # O(n) — rebuild with new size
        if n == 0 or not (len(self.A) // 4 <= n <= len(self.A)):
            m = max(n * 2, 1)
            new_A = [[] for _ in range(m)]  # new array of empty chains
            for chain in self.A:
                for x in chain:
                    new_A[self._hash(x.key, m)].append(x)
            self.A = new_A

    def find(self, k):            # O(1) expected
        h = self._hash(k, len(self.A))
        for x in self.A[h]:      # scan chain at slot h
            if x.key == k:
                return x
        return None

    def insert(self, x):          # O(1) amortised expected
        self._resize(self.size + 1)
        h = self._hash(x.key, len(self.A))
        for item in self.A[h]:   # check for existing key
            if item.key == x.key:
                item.val = x.val  # update
                return
        self.A[h].append(x)      # no collision — just append
        self.size += 1

    def delete(self, k):          # O(1) amortised expected
        h = self._hash(k, len(self.A))
        for i, x in enumerate(self.A[h]):
            if x.key == k:
                self.A[h].pop(i)
                self.size -= 1
                self._resize(self.size)
                return x
        raise KeyError(k)

    # Order operations — O(n), no structure to exploit
    def find_min(self):
        return min((x for chain in self.A for x in chain),
                   key=lambda x: x.key, default=None)

    def find_max(self):
        return max((x for chain in self.A for x in chain),
                   key=lambda x: x.key, default=None)

#include <vector>
#include <list>
#include <optional>
#include <random>
using namespace std;

// Hash table with chaining and universal hash family
// h_a(k) = (a*k mod p) mod m,  p = 2^31 - 1
template<typename K, typename V>
class Hash_Table_Set {
    using KV = pair<K, V>;
    vector<list<KV>> A;
    int    sz   = 0;
    long   p    = 2147483647LL;   // Mersenne prime 2^31 - 1
    long   a;                      // random multiplier

    int hash(K k, int m) {
        return (int)(((a * (long)k) % p) % m);
    }

    void resize(int n) {
        if (A.empty() || n < (int)A.size()/4 || n >= (int)A.size()) {
            int m = max(n * 2, 1);
            vector<list<KV>> B(m);
            for (auto& chain : A)
                for (auto& [k, v] : chain)
                    B[hash(k, m)].push_back({k, v});
            A = move(B);
        }
    }

public:
    Hash_Table_Set() {
        mt19937 rng(random_device{}());
        a = uniform_int_distribution<long>(1, p-1)(rng);
        resize(0);
    }

    optional<V> find(K k) {              // O(1) expected
        for (auto& [key, val] : A[hash(k, A.size())])
            if (key == k) return val;
        return nullopt;
    }

    void insert(K k, V v) {              // O(1) amortised expected
        resize(sz + 1);
        auto& chain = A[hash(k, A.size())];
        for (auto& [key, val] : chain)
            if (key == k) { val = v; return; }
        chain.push_back({k, v});
        sz++;
    }

    void remove(K k) {                   // O(1) amortised expected
        auto& chain = A[hash(k, A.size())];
        chain.remove_if([&](auto& kv){ return kv.first == k; });
        sz--;
        resize(sz);
    }
};

The Complete Performance Picture

(e) expected over random hash function · (a) amortised over sequence of operations

def build_instrument_maps(master):
    """
    master: list of instrument dicts from XTS API
    Returns two O(1) lookup dicts, built in Θ(n) total.
    """
    symbol_to_token = {}           # str  → int
    token_to_symbol = {}           # int  → str

    for inst in master:
        sym = inst['TradingSymbol']
        tok = inst['ExchangeInstrumentID']
        symbol_to_token[sym] = tok
        token_to_symbol[tok] = sym

    return symbol_to_token, token_to_symbol

# Usage — both lookups are O(1) expected
# sym_map, tok_map = build_instrument_maps(master)
# token = sym_map['NIFTY24JAN24CE24000']    # O(1)
# symbol = tok_map[26000]                    # O(1)

Python's dict and set — Hash Tables Under the Hood

Python's built-in dict and set are hash tables. Python uses open addressing (not chaining) with a probing strategy, but the asymptotic bounds are the same: $O(1)$ expected for get, set, delete; $O(n)$ to build. A few practical notes:

Keys must be hashable — Python computes hash(key) for each key. Integers, strings, and tuples are hashable. Lists and dicts are not (they are mutable, so their hash would change). For custom objects, define __hash__ and __eq__.

As of Python 3.7+, dict preserves insertion order — a deliberate design choice, not an algorithmic property of hash tables. Do not rely on this for ordering by key value; use a sorted structure for that.

The Duplicates Problem — Five Algorithms, Five Complexities

A clean problem that illustrates every tool from this module and the last. Given an array $A$ of $n$ positive integers with values at most $k$, does $A$ contain any duplicate?

Algorithm 1 — Brute force: check all $\binom{n}{2}$ pairs. $\Theta(n^2)$.

Algorithm 2 — Sort first: merge sort in $\Theta(n \log n)$, then scan for adjacent duplicates in $\Theta(n)$. Total: $\Theta(n \log n)$.

Algorithm 3 — Hash table: insert each element; if it is already present, return duplicate found. $O(n)$ expected — each insert and lookup is $O(1)$ expected.

Algorithm 4 — Pigeonhole: if $k < n$, a duplicate must exist by the pigeonhole principle. Return True without looking at the data. $\Theta(1)$.

Algorithm 5 — Direct access array: if $n \leq k$, allocate a boolean array of size $k$. For each element, check and mark. $\Theta(k)$ initialisation, $\Theta(n)$ insertions. Total: $\Theta(k)$.