Hash Table

Introduction

A hash table, also known as a hash map, is a data structure that stores data in a "key-value" format. Storing data in a "key-value" format means that any key uniquely corresponds to a location in memory. By simply inputting the key to be searched, the corresponding value can be quickly found. A hash table can be thought of as an advanced array, where the indices can be large integers, floating-point numbers, strings, or even structures.

Hash Function

To map a key to a location in memory, an index must be computed for the key, i.e., determining where the data should be placed. The function that computes the index based on the key is called the hash function, also known as the hashing function. For example, if the key is a person's ID number, the hash function could be the last four digits of the number, or the first four digits. In daily life, "mobile phone tail number" is also a type of hash function. In practical applications, keys can be more complex, such as floating-point numbers, strings, structures, etc. In such cases, a suitable hash function must be designed based on the specific situation. The hash function should be easy to compute and should aim to distribute the computed indices as uniformly as possible.

Once an index can be computed for a key, we can determine where the 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 type or range of the key, f(key) is an integer within an acceptable range and can be used as an array index.

In OI (Competitive Programming), the most common scenario is when the key is an integer. When the range of keys is relatively small, the key can be directly used as the array index. However, when the key range is large, such as integers within the range of \(10^9\), a hash table is needed. Typically, the key is modulo a large prime number to compute the index, i.e., using \(f(x)=x \bmod M\) as the hash function.

Another common scenario is when the key is a string. Since strings cannot be used as array indices, and converting strings into numbers for storage can avoid multiple string comparisons, in OI, strings are generally not directly used as keys. Instead, the hash value of the string is computed first, and then the hash value is inserted into the hash table as the key. For the hash value of a string, the idea of a base system is generally used, treating the string as a number in base \(127\). Thus, for a string \(s\) of length \(n\), we have:

\(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 obtained \(x\) modulo \(2^{64}\) (i.e., the maximum value of unsigned long long). This way, the natural overflow of unsigned long long is equivalent to the modulo operation, making operations more convenient.

Although this method is simple, it is not perfect. Data can be constructed to cause collisions in this method (i.e., two strings have the same result when \(x\) is taken modulo \(2^{64}\)).
We can use the double hashing method: select two large prime numbers \(a\) and \(b\). Two strings are considered equal only when their hash values modulo \(a\) and modulo \(b\) are both equal. This can significantly reduce the probability of hash collisions.

Collisions

If the hash function computes a unique index for every key, then we can simply place the (key, value) pair at the corresponding location based on the index. However, in practice, it often happens that two different keys compute the same index using the hash function. In such cases, methods are needed to handle collisions. In OI, the most commonly used method is separate chaining.

Separate Chaining

Separate chaining is also known as open hashing.

In separate chaining, a linked list is created at each location where data is stored. If multiple keys hash to the same location, they are all placed in the linked list at that position. When querying, the entire linked list at the corresponding position must be traversed, comparing the key of each element with the query key. If the index range is \(1\ldots M\) and the hash table size is \(N\), then an insertion/query operation requires an expected \(O(\frac{N}{M})\) comparisons.

Implementation

C++Python

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;
  }
};

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 an encapsulated template that can be used like a map and is relatively short:

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 size
  int h[SZ], cnt;

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

  // The reason for using (u % SZ + SZ) % SZ instead of u % SZ is
  // that the % operator in C++ cannot convert negative numbers to positive numbers

  int& operator[](long long u) {
    int hu = hash(u);  // Get head pointer
    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 key type and returns a linked list head pointer for queries. In this template, we implement a hash table with key-value pair type (long long, int), which returns -1 when querying a non-existent key. The function hash_map() is used for initialization upon definition.

Closed Addressing

Closed addressing stores all records directly in the hash table. If a collision occurs, probing continues in some manner.

For example, linear probing: if a collision occurs at position d, check d + 1, d + 2, ... 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) {
    // Returns a reference to the corresponding Hash[Key]
    // A value of 0 is considered 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 Problem

「JLOI2011」Non-Repeating Numbers

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用