A hash table delivers expected O(1) time complexity for data retrieval and insertion by mapping arbitrary keys into a fixed-size array. This technique compresses a large key space (e.g., integers up to 10^9) into a manageable index range (typically 10^5 to 10^6). Unlike discretization, which preserves relative order, hashing focuses solely on efficient key-to-index mapping without ordering guarantees.

Hash Function Design

The most straightforward mapping strategy applies the modulo operator: key % M. To minimize collision frequency, M should be a prime number positioned far from powers of two. In algorithmic problem solving, selecting the smallest prime larger than the expected data volume yields optimal distribution.

Since the domain exceeds the codomain, multiple keys inevitably map to identical indices. Two primary strategies resolve these collisions.

Separate Chaining

This approach treats each array slot as the head of a linked list. When multiple keys hash to the same index, they are appended to the corresponding list. Under uniform hashing assumptions, list lengths remain constant on average, preserving O(1) performance.

Implementation Mechanics

Arrays simulate the linked structure for memory efficiency:

• bucket_head[]: Stores the starting node index for each slot.
• node_data[]: Holds the actual key values.
• node_next[]: Points to the subsequent node in the chain.
• alloc_ptr: Tracks the next available node index.

Insertion computes the target slot, then performs a head-insertion into the linked list. Querying traverses the chain at the computed slot until a match is found or the list ends. Negative keys require careful modulo handling: (key % M + M) % M guarantees a non-negative index.

Deletion is typically avoided in algorithmic contexts. When necessary, a boolean flag array marks entries as logically removed rather than physically unlinking nodes.

#include <cstdio>
#include <cstring>

const int TABLE_SIZE = 100003; // Prime capacity
int bucket_head[TABLE_SIZE];
int node_data[TABLE_SIZE];
int node_next[TABLE_SIZE];
int alloc_ptr = 0;

inline int hash_key(int val) {
    return (val % TABLE_SIZE + TABLE_SIZE) % TABLE_SIZE;
}

void chain_insert(int val) {
    int slot = hash_key(val);
    node_data[alloc_ptr] = val;
    node_next[alloc_ptr] = bucket_head[slot];
    bucket_head[slot] = alloc_ptr++;
}

bool chain_query(int val) {
    int slot = hash_key(val);
    for (int curr = bucket_head[slot]; curr != -1; curr = node_next[curr]) {
        if (node_data[curr] == val) return true;
    }
    return false;
}

Open Addressing

Instead of auxiliary lists, this method stores all elements directly within a single contiguous array. The array capacity must exceed the maximum element count by a factor of 2 to 3 to maintain low probe sequences. When a collision occurs at index k, the algorithm linearly scans subsequent positions until an empty slot or the target key is located. Wrapping around to index 0 handles boundarry overflow.

Implementation Mechanics

The array initializes with a sentinel value (e.g., 0x3f3f3f3f) representing vacant slots. A unified probe function locates either the existing key or the first available position.

#include <cstdio>
#include <cstring>

const int CAPACITY = 200003;
const int VACANT = 0x3f3f3f3f;
int linear_table[CAPACITY];

int probe(int val) {
    int pos = (val % CAPACITY + CAPACITY) % CAPACITY;
    while (linear_table[pos] != VACANT && linear_table[pos] != val) {
        pos++;
        if (pos == CAPACITY) pos = 0;
    }
    return pos;
}

// Initialization requires byte-wise filling:
// memset(linear_table, 0x3f, sizeof(linear_table));

Insertion assigns linear_table[probe(val)] = val. Verification checks if linear_table[probe(val)] != VACANT.

Applied Scenario: Dynamic Set Operations

Problem Statement Maintain a collection supporting two commands:

• I x: Insert integer x.
• Q x: Check if x exists. Process N operations (1 ≤ N ≤ 10^5, |x| ≤ 10^9). Output Yes or No for each query.

Both chaining and open addressing solve this efficiently. The choice depends on memory constraints and implementation preference. Chaining uses more pointers but handles higher load factors gracefully. Open addressing offers better cache locality but requires stricter capacity planning.

String Rolling Hash

Prefix hashing converts substrings into numeric fingerprints, enabling O(1) equality checks. The technique interprets a string as a base-P integer, where each character represents a digit.

Core Principles

1. Base Selection: P = 131 or 13331 minimizes collisions.
2. Modulo Arithmetic: Using uint64_t leverages hardware overflow, implicitly applying modulo 2^64. Explicit modulo operations become unnecessary.
3. Zero Mapping: Never map characters to 0. Otherwise, strings like "A" and "AA" would both hash to 0, causing false positives. ASCII values work directly.

Prefix Computation & Substring Extraction

Precompute prefix hashes H[i] and powers P[i]: H[i] = H[i-1] * P + str[i] P[i] = P[i-1] * P

The hash of a substring spanning indices [L, R] (1-based) derives from: Hash(L, R) = H[R] - H[L-1] * P[R-L+1]

This formula aligns the higher-order prefix H[L-1] with H[R] by shifting it left (R-L+1) positions in base P, then subtracts it to isolate the target segment.

#include <cstdio>
#include <cstdint>

using ULL = uint64_t;
const int MAX_LEN = 100010;
const ULL BASE = 131;

char sequence[MAX_LEN];
ULL prefix_hash[MAX_LEN];
ULL base_pow[MAX_LEN];

ULL extract_hash(int left, int right) {
    return prefix_hash[right] - prefix_hash[left - 1] * base_pow[right - left + 1];
}

int main() {
    int str_len, queries;
    scanf("%d %d %s", &str_len, &queries, sequence + 1);

    base_pow[0] = 1;
    for (int i = 1; i <= str_len; ++i) {
        base_pow[i] = base_pow[i - 1] * BASE;
        prefix_hash[i] = prefix_hash[i - 1] * BASE + static_cast<ULL>(sequence[i]);
    }

    while (queries--) {
        int l1, r1, l2, r2;
        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
        if (extract_hash(l1, r1) == extract_hash(l2, r2)) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
    return 0;
}