Hash Table

Introduction

A hash table, also called a hash map, is a data structure that stores data as “key-value” pairs. Storing data in this form means that every key uniquely corresponds to a location in memory. By entering a key to look up, we can quickly find its corresponding value. A hash table can be understood as an advanced array whose indices may be large integers, floating-point numbers, strings, or even structures.

Hash Functions

To map a key to a location in memory, we need to compute an index for the key—that is, determine where the data should be placed. The function that computes an index from a key is called a hash function, also known as a hashing function. For example, if the key is a person's identity-card number, the hash function could be the last four digits or the first four digits. The commonly used “last digits of a phone number” is also a hash function. In practice, keys may be more complicated, such as floating-point numbers, strings, or structures, so an appropriate hash function must be designed for each situation. A hash function should be easy to compute and should make the computed indices as uniformly distributed as possible.

Once we can compute an index for a key, we know where its corresponding value should be stored. Suppose we use an array a to store data and the hash function is f; then the key-value pair (key, value) should be placed at a[f(key)]. Regardless of the key's type or range, f(key) is an integer in an acceptable range and can serve as an array index.

In OI, the most common case is an integer key. When the key range is small, the key itself can be used as an array index. But when the range is large—for example, when keys are integers in a range of $10^9$—a hash table is needed. A common choice is to use the key modulo a large prime as the index, that is, to use $f(x)=x \bmod M$ as the hash function.

Another common case is a string key. Since strings cannot be used as array indices, and converting strings to numbers also avoids repeated string comparisons, OI solutions generally do not use strings directly as keys. Instead, they first compute a string hash and insert that hash value into the hash table as the key. For string hashing, we usually use the positional numeral-system idea and regard a string as a number in base $127$. Thus, for every string $s$ of length $n$,

$x = s_0 \cdot 127^0 + s_1 \cdot 127^1 + s_2 \cdot 127^2 + \dots + s_n \cdot 127^n$

We can take the resulting $x$ modulo $2^{64}$, the maximum value of unsigned long long. The natural overflow of unsigned long long is then equivalent to taking this modulo, making the operation more convenient.

Although this method is simple, it is not perfect. Data can be constructed to make it collide, meaning that two strings have the same result after their $x$ values are reduced modulo $2^{64}$.
We can use double hashing instead: choose two large primes $a,b$, and regard two strings as equal only when their hash values are equal modulo both $a$ and $b$. This greatly reduces the probability of hash collisions.

Collisions

If the hash function produced a different index for every key, we could simply place each (key, value) at its indexed position. In practice, however, two different keys often produce the same index. We then need methods for handling collisions. In OI, the most common method is separate chaining.

Separate Chaining

Separate chaining is also called open hashing.

Separate chaining creates a linked list at every data location. If several keys map to the same location, we simply put all of them into the linked list at that location. During a query, the entire linked list at the corresponding location is scanned, comparing each stored key with the queried key. If the index range is $1\ldots M$ and the hash table has size $N$, one insertion or query requires an expected $O(\frac{N}{M})$ comparisons.

Implementation

C++

constexpr int SIZE = 1000000;
constexpr int M = 999997;

struct HashTable {
  struct Node {
    int next, value, key;
  } data[SIZE];

  int head[M], size;

  int f(int key) { return (key % M + M) % M; }

  int get(int key) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value;
    return -1;
  }

  int modify(int key, int value) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value = value;
  }

  int add(int key, int value) {
    if (get(key) != -1) return -1;
    data[++size] = Node{head[f(key)], value, key};
    head[f(key)] = size;
    return value;
  }
};

Python

M = 999997
SIZE = 1000000

class Node:
    def __init__(self, next=None, value=None, key=None):
        self.next = next
        self.value = value
        self.key = key

data = [Node() for _ in range(SIZE)]
head = [0] * M
size = 0

def f(key):
    return key % M

def get(key):
    p = head[f(key)]
    while p:
        if data[p].key == key:
            return data[p].value
        p = data[p].next
    return -1

def modify(key, value):
    p = head[f(key)]
    while p:
        if data[p].key == key:
            data[p].value = value
            return data[p].value
        p = data[p].next

def add(key, value):
    if get(key) != -1:
        return -1
    size = size + 1
    data[size] = Node(head[f(key)], value, key)
    head[f(key)] = size
    return value

Here is another encapsulated template that can be used like map and is shorter:

struct hash_map {  // Hash table template

  struct data {
    long long u;
    int v, nex;
  };  // Forward-star structure

  data e[SZ << 1];  // SZ is a const int representing the size
  int h[SZ], cnt;

  int hash(long long u) { return (u % SZ + SZ) % SZ; }

  // Forward-star structure (u % SZ + SZ) % SZ   u % SZ  
  // C++   %  number number

  int& operator[](long long u) {
    int hu = hash(u);  // Forward-star structure
    for (int i = h[hu]; i; i = e[i].nex)
      if (e[i].u == u) return e[i].v;
    return e[++cnt] = data{u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
  }

  hash_map() {
    cnt = 0;
    memset(h, 0, sizeof(h));
  }
};

Here, the hash function is designed for the type of key and returns a linked-list head pointer for queries. This template implements a hash table whose key-value type is (long long, int), and returns -1 when the queried key does not exist. The hash_map() function initializes the table when it is defined.

Open Addressing

Open addressing stores all records directly in the hash table. When a collision occurs, it continues probing according to a chosen rule.

For example, with linear probing, if a collision occurs at d, we check d + 1, d + 2, and so on in sequence.

Implementation

constexpr int N = 360007;  // N is the maximum number of elements that can be stored

class Hash {
 private:
  int keys[N];
  int values[N];

 public:
  Hash() { memset(values, 0, sizeof(values)); }

  int& operator[](int n) {
    // Return a reference to the corresponding Hash[Key]
    // A nonzero value is considered occupied; 0 means empty
    int idx = (n % N + N) % N, cnt = 1;
    while (keys[idx] != n && values[idx] != 0) {
      idx = (idx + cnt * cnt) % N;
      cnt += 1;
    }
    keys[idx] = n;
    return values[idx];
  }
};

Example Problems

「JLOI2011」Non-repeating Numbers