Основы хеширования

Что такое хеш-таблица?

Хеш-таблица — структура данных, которая связывает ключи со значениями через хеш-функцию. Обеспечивает доступ, вставку и удаление в среднем за O(1).

Ключ "apple" ---> hash("apple") = 3 ---> bucket[3] = "яблоко"
Ключ "banana" --> hash("banana") = 7 ---> bucket[7] = "банан"
Ключ "cherry" --> hash("cherry") = 3 ---> КОЛЛИЗИЯ! bucket[3] уже занят

Хеш-функция

Хеш-функция преобразует ключ произвольного размера в число фиксированного размера (индекс в массиве).

Требования к хорошей хеш-функции

Детерминированность — один и тот же вход всегда даёт один и тот же выход
Равномерное распределение — ключи распределяются по бакетам равномерно
Скорость — вычисляется быстро
Лавинный эффект — маленькое изменение ключа сильно меняет хеш

Примеры хеш-функций

<?php
declare(strict_types=1);

// Simple hash function for strings
function simpleHash(string $key, int $tableSize): int
{
    $hashValue = 0;
    for ($i = 0; $i < strlen($key); $i++) {
        $hashValue += ord($key[$i]);
    }
    return $hashValue % $tableSize;
}

// Better quality (polynomial rolling hash)
function polynomialHash(string $key, int $tableSize, int $p = 31): int
{
    $hashValue = 0;
    $pPower = 1;
    for ($i = 0; $i < strlen($key); $i++) {
        $hashValue = ($hashValue + ord($key[$i]) * $pPower) % $tableSize;
        $pPower = ($pPower * $p) % $tableSize;
    }
    return $hashValue;
}

// simpleHash sums byte values and takes modulo.
func simpleHash(key string, tableSize int) int {
	hashValue := 0
	for i := 0; i < len(key); i++ {
		hashValue += int(key[i])
	}
	return hashValue % tableSize
}

// polynomialHash uses polynomial rolling hash for better distribution.
func polynomialHash(key string, tableSize, p int) int {
	hashValue := 0
	pPower := 1
	for i := 0; i < len(key); i++ {
		hashValue = (hashValue + int(key[i])*pPower) % tableSize
		pPower = (pPower * p) % tableSize
	}
	return hashValue
}

// Simple hash function for strings
static int SimpleHash(string key, int tableSize)
{
    int hashValue = 0;
    foreach (char c in key)
    {
        hashValue += c;
    }
    return hashValue % tableSize;
}

// Better quality (polynomial rolling hash)
static int PolynomialHash(string key, int tableSize, int p = 31)
{
    long hashValue = 0;
    long pPower = 1;
    foreach (char c in key)
    {
        hashValue = (hashValue + c * pPower) % tableSize;
        pPower = pPower * p % tableSize;
    }
    return (int)hashValue;
}

# Simple hash function for strings
def simple_hash(key: str, table_size: int) -> int:
    return sum(ord(ch) for ch in key) % table_size

# Better quality (polynomial rolling hash)
def polynomial_hash(key: str, table_size: int, p: int = 31) -> int:
    hash_value = 0
    p_power = 1
    for ch in key:
        hash_value = (hash_value + ord(ch) * p_power) % table_size
        p_power = p_power * p % table_size
    return hash_value

### Что используют реальные языки

PHP array: DJB33A (DJBX33A) хеш-функция для строковых ключей
Python dict: модифицированный SipHash (криптографический, защита от collision attacks)
Go map: AES-based hash на поддерживаемых CPU
Java HashMap: hashCode() объекта + дополнительное перемешивание

Коллизии

Коллизия — когда два разных ключа получают одинаковый хеш. Это неизбежно (принцип Дирихле: если ключей больше, чем бакетов).

Метод 1: Chaining (цепочки)

Каждый бакет — это связный список (или массив). При коллизии просто добавляем элемент в список.

Бакеты:
[0] -> None
[1] -> ("cat", 1) -> ("bat", 2) -> None
[2] -> None
[3] -> ("apple", 5) -> ("cherry", 8) -> None
[4] -> ("dog", 3) -> None

<?php
declare(strict_types=1);

final class HashTableChaining
{
    /** @var array<int, array<int, array{string, mixed}>> */
    private array $buckets;
    private int $count = 0;

    public function __construct(private int $size = 16)
    {
        $this->buckets = array_fill(0, $this->size, []);
    }

    private function hash(string $key): int
    {
        return crc32($key) % $this->size;
    }

    public function put(string $key, mixed $value): void
    {
        $idx = $this->hash($key);
        // Check if key already exists
        foreach ($this->buckets[$idx] as $i => [$k, $v]) {
            if ($k === $key) {
                $this->buckets[$idx][$i] = [$key, $value];
                return;
            }
        }
        $this->buckets[$idx][] = [$key, $value];
        $this->count++;
        // Check load factor
        if ($this->count / $this->size > 0.75) {
            $this->resize();
        }
    }

    public function get(string $key): mixed
    {
        $idx = $this->hash($key);
        foreach ($this->buckets[$idx] as [$k, $v]) {
            if ($k === $key) {
                return $v;
            }
        }
        throw new \RuntimeException("Key not found: {$key}");
    }

    public function delete(string $key): void
    {
        $idx = $this->hash($key);
        foreach ($this->buckets[$idx] as $i => [$k, $v]) {
            if ($k === $key) {
                array_splice($this->buckets[$idx], $i, 1);
                $this->count--;
                return;
            }
        }
        throw new \RuntimeException("Key not found: {$key}");
    }

    private function resize(): void
    {
        $oldBuckets = $this->buckets;
        $this->size *= 2;
        $this->buckets = array_fill(0, $this->size, []);
        $this->count = 0;
        foreach ($oldBuckets as $bucket) {
            foreach ($bucket as [$key, $value]) {
                $this->put($key, $value);
            }
        }
    }
}

import (
	"fmt"
	"hash/crc32"
)

type entry struct {
	key   string
	value any
}

// HashTableChaining implements a hash table with chaining.
type HashTableChaining struct {
	buckets [][]entry
	size    int
	count   int
}

func NewHashTableChaining(size int) *HashTableChaining {
	return &HashTableChaining{
		buckets: make([][]entry, size),
		size:    size,
	}
}

func (h *HashTableChaining) hash(key string) int {
	return int(crc32.ChecksumIEEE([]byte(key))) % h.size
}

func (h *HashTableChaining) Put(key string, value any) {
	idx := h.hash(key)
	// Check if key already exists
	for i, e := range h.buckets[idx] {
		if e.key == key {
			h.buckets[idx][i].value = value
			return
		}
	}
	h.buckets[idx] = append(h.buckets[idx], entry{key, value})
	h.count++
	// Check load factor
	if float64(h.count)/float64(h.size) > 0.75 {
		h.resize()
	}
}

func (h *HashTableChaining) Get(key string) (any, error) {
	idx := h.hash(key)
	for _, e := range h.buckets[idx] {
		if e.key == key {
			return e.value, nil
		}
	}
	return nil, fmt.Errorf("key not found: %s", key)
}

func (h *HashTableChaining) Delete(key string) error {
	idx := h.hash(key)
	for i, e := range h.buckets[idx] {
		if e.key == key {
			h.buckets[idx] = append(h.buckets[idx][:i], h.buckets[idx][i+1:]...)
			h.count--
			return nil
		}
	}
	return fmt.Errorf("key not found: %s", key)
}

func (h *HashTableChaining) resize() {
	oldBuckets := h.buckets
	h.size *= 2
	h.buckets = make([][]entry, h.size)
	h.count = 0
	for _, bucket := range oldBuckets {
		for _, e := range bucket {
			h.Put(e.key, e.value)
		}
	}
}

using System;
using System.Collections.Generic;

public sealed class HashTableChaining<TValue>
{
    private readonly record struct Entry(string Key, TValue Value);

    private List<Entry>[] _buckets;
    private int _size;
    private int _count;

    public HashTableChaining(int size = 16)
    {
        _size = size;
        _buckets = CreateBuckets(size);
    }

    private static List<Entry>[] CreateBuckets(int size)
    {
        var buckets = new List<Entry>[size];
        for (int i = 0; i < size; i++)
        {
            buckets[i] = [];
        }
        return buckets;
    }

    // GetHashCode may be negative, so mask off the sign bit
    private int Hash(string key) => (key.GetHashCode() & 0x7FFFFFFF) % _size;

    public void Put(string key, TValue value)
    {
        var bucket = _buckets[Hash(key)];
        // Check if key already exists
        for (int i = 0; i < bucket.Count; i++)
        {
            if (bucket[i].Key == key)
            {
                bucket[i] = new Entry(key, value);
                return;
            }
        }
        bucket.Add(new Entry(key, value));
        _count++;
        // Check load factor
        if ((double)_count / _size > 0.75)
        {
            Resize();
        }
    }

    public TValue Get(string key)
    {
        foreach (var e in _buckets[Hash(key)])
        {
            if (e.Key == key)
            {
                return e.Value;
            }
        }
        throw new KeyNotFoundException($"Key not found: {key}");
    }

    public void Delete(string key)
    {
        var bucket = _buckets[Hash(key)];
        for (int i = 0; i < bucket.Count; i++)
        {
            if (bucket[i].Key == key)
            {
                bucket.RemoveAt(i);
                _count--;
                return;
            }
        }
        throw new KeyNotFoundException($"Key not found: {key}");
    }

    private void Resize()
    {
        var oldBuckets = _buckets;
        _size *= 2;
        _buckets = CreateBuckets(_size);
        _count = 0;
        foreach (var bucket in oldBuckets)
        {
            foreach (var e in bucket)
            {
                Put(e.Key, e.Value);
            }
        }
    }
}

// In real code use Dictionary<string, TValue>: it already resolves
// collisions with bucket chaining. The class above is for learning.

from typing import Any

class HashTableChaining:
    def __init__(self, size: int = 16) -> None:
        self._size = size
        self._count = 0
        self._buckets: list[list[tuple[str, Any]]] = [[] for _ in range(size)]

    def _hash(self, key: str) -> int:
        return hash(key) % self._size

    def put(self, key: str, value: Any) -> None:
        bucket = self._buckets[self._hash(key)]
        # Check if key already exists
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self._count += 1
        # Check load factor
        if self._count / self._size > 0.75:
            self._resize()

    def get(self, key: str) -> Any:
        for k, v in self._buckets[self._hash(key)]:
            if k == key:
                return v
        raise KeyError(f"Key not found: {key}")

    def delete(self, key: str) -> None:
        bucket = self._buckets[self._hash(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self._count -= 1
                return
        raise KeyError(f"Key not found: {key}")

    def _resize(self) -> None:
        old_buckets = self._buckets
        self._size *= 2
        self._buckets = [[] for _ in range(self._size)]
        self._count = 0
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)

# In real code use dict. Note the difference: CPython's dict resolves
# collisions with open addressing, not chaining.

### Метод 2: Open Addressing (открытая адресация)

При коллизии ищем следующее свободное место в самом массиве.

Linear Probing: проверяем следующий бакет по очереди.

hash("apple") = 3
hash("cherry") = 3  <- коллизия! Проверяем 4... занят, 5... свободен!

Бакеты:
[0] [1] [2] [3:apple] [4:banana] [5:cherry] [6] [7]
                ^                     ^
           оба имеют hash=3     нашли свободное место

<?php
declare(strict_types=1);

final class HashTableOpenAddr
{
    private const string DELETED = '__DELETED__';

    /** @var array<int, string|null> */
    private array $keys;
    /** @var array<int, mixed> */
    private array $values;
    private int $count = 0;

    public function __construct(private int $size = 16)
    {
        $this->keys = array_fill(0, $this->size, null);
        $this->values = array_fill(0, $this->size, null);
    }

    private function hash(string $key): int
    {
        return abs(crc32($key)) % $this->size;
    }

    /** Find position for key using linear probing */
    private function probe(string $key): int
    {
        $idx = $this->hash($key);
        $firstDeleted = null;

        for ($i = 0; $i < $this->size; $i++) {
            if ($this->keys[$idx] === null) {
                return $firstDeleted ?? $idx;
            }
            if ($this->keys[$idx] === self::DELETED) {
                $firstDeleted ??= $idx;
            } elseif ($this->keys[$idx] === $key) {
                return $idx;
            }
            $idx = ($idx + 1) % $this->size;
        }

        return $firstDeleted ?? throw new \OverflowException('Table is full');
    }

    public function put(string $key, mixed $value): void
    {
        if ($this->count / $this->size > 0.7) {
            $this->resize();
        }
        $idx = $this->probe($key);
        if ($this->keys[$idx] !== $key) {
            $this->count++;
        }
        $this->keys[$idx] = $key;
        $this->values[$idx] = $value;
    }

    public function get(string $key): mixed
    {
        $idx = $this->probe($key);
        if ($this->keys[$idx] === $key) {
            return $this->values[$idx];
        }
        throw new \RuntimeException("Key not found: {$key}");
    }

    private function resize(): void
    {
        $oldKeys = $this->keys;
        $oldValues = $this->values;
        $this->size *= 2;
        $this->keys = array_fill(0, $this->size, null);
        $this->values = array_fill(0, $this->size, null);
        $this->count = 0;
        foreach ($oldKeys as $i => $key) {
            if ($key !== null && $key !== self::DELETED) {
                $this->put($key, $oldValues[$i]);
            }
        }
    }
}

import (
	"errors"
	"hash/crc32"
	"math"
)

const deletedKey = "__DELETED__"

// HashTableOpenAddr implements a hash table with open addressing (linear probing).
type HashTableOpenAddr struct {
	keys   []string
	values []any
	used   []bool // tracks occupied slots (key != "")
	size   int
	count  int
}

func NewHashTableOpenAddr(size int) *HashTableOpenAddr {
	return &HashTableOpenAddr{
		keys:   make([]string, size),
		values: make([]any, size),
		used:   make([]bool, size),
		size:   size,
	}
}

func (h *HashTableOpenAddr) hash(key string) int {
	return int(math.Abs(float64(int32(crc32.ChecksumIEEE([]byte(key)))))) % h.size
}

func (h *HashTableOpenAddr) probe(key string) (int, error) {
	idx := h.hash(key)
	firstDeleted := -1

	for i := 0; i < h.size; i++ {
		if !h.used[idx] {
			if firstDeleted >= 0 {
				return firstDeleted, nil
			}
			return idx, nil
		}
		if h.keys[idx] == deletedKey {
			if firstDeleted < 0 {
				firstDeleted = idx
			}
		} else if h.keys[idx] == key {
			return idx, nil
		}
		idx = (idx + 1) % h.size
	}

	if firstDeleted >= 0 {
		return firstDeleted, nil
	}
	return 0, errors.New("table is full")
}

func (h *HashTableOpenAddr) Put(key string, value any) {
	if float64(h.count)/float64(h.size) > 0.7 {
		h.resize()
	}
	idx, _ := h.probe(key)
	if !h.used[idx] || h.keys[idx] != key {
		h.count++
	}
	h.keys[idx] = key
	h.values[idx] = value
	h.used[idx] = true
}

func (h *HashTableOpenAddr) Get(key string) (any, error) {
	idx, _ := h.probe(key)
	if h.used[idx] && h.keys[idx] == key {
		return h.values[idx], nil
	}
	return nil, fmt.Errorf("key not found: %s", key)
}

func (h *HashTableOpenAddr) resize() {
	oldKeys := h.keys
	oldValues := h.values
	oldUsed := h.used
	h.size *= 2
	h.keys = make([]string, h.size)
	h.values = make([]any, h.size)
	h.used = make([]bool, h.size)
	h.count = 0
	for i, key := range oldKeys {
		if oldUsed[i] && key != deletedKey {
			h.Put(key, oldValues[i])
		}
	}
}

using System;
using System.Collections.Generic;

public sealed class HashTableOpenAddr<TValue>
{
    private const string Deleted = "__DELETED__";

    private string?[] _keys;
    private TValue?[] _values;
    private int _size;
    private int _count;

    public HashTableOpenAddr(int size = 16)
    {
        _size = size;
        _keys = new string?[size];
        _values = new TValue?[size];
    }

    private int Hash(string key) => (key.GetHashCode() & 0x7FFFFFFF) % _size;

    // Find position for key using linear probing
    private int Probe(string key)
    {
        int idx = Hash(key);
        int firstDeleted = -1;

        for (int i = 0; i < _size; i++)
        {
            switch (_keys[idx])
            {
                case null:
                    return firstDeleted >= 0 ? firstDeleted : idx;
                case Deleted when firstDeleted < 0:
                    firstDeleted = idx;
                    break;
                case var k when k == key:
                    return idx;
            }
            idx = (idx + 1) % _size;
        }

        return firstDeleted >= 0
            ? firstDeleted
            : throw new InvalidOperationException("Table is full");
    }

    public void Put(string key, TValue value)
    {
        if ((double)_count / _size > 0.7)
        {
            Resize();
        }
        int idx = Probe(key);
        if (_keys[idx] != key)
        {
            _count++;
        }
        _keys[idx] = key;
        _values[idx] = value;
    }

    public TValue Get(string key)
    {
        int idx = Probe(key);
        if (_keys[idx] == key)
        {
            return _values[idx]!;
        }
        throw new KeyNotFoundException($"Key not found: {key}");
    }

    public void Delete(string key)
    {
        int idx = Probe(key);
        if (_keys[idx] != key)
        {
            throw new KeyNotFoundException($"Key not found: {key}");
        }
        // Tombstone instead of null, otherwise the probe chain breaks
        _keys[idx] = Deleted;
        _values[idx] = default;
        _count--;
    }

    private void Resize()
    {
        var oldKeys = _keys;
        var oldValues = _values;
        _size *= 2;
        _keys = new string?[_size];
        _values = new TValue?[_size];
        _count = 0;
        for (int i = 0; i < oldKeys.Length; i++)
        {
            if (oldKeys[i] is { } key && key != Deleted)
            {
                Put(key, oldValues[i]!);
            }
        }
    }
}

from typing import Any

class HashTableOpenAddr:
    _DELETED = "__DELETED__"

    def __init__(self, size: int = 16) -> None:
        self._size = size
        self._count = 0
        self._keys: list[str | None] = [None] * size
        self._values: list[Any] = [None] * size

    def _hash(self, key: str) -> int:
        return hash(key) % self._size

    # Find position for key using linear probing
    def _probe(self, key: str) -> int:
        idx = self._hash(key)
        first_deleted: int | None = None

        for _ in range(self._size):
            current = self._keys[idx]
            if current is None:
                return idx if first_deleted is None else first_deleted
            if current == self._DELETED:
                if first_deleted is None:
                    first_deleted = idx
            elif current == key:
                return idx
            idx = (idx + 1) % self._size

        if first_deleted is None:
            raise OverflowError("Table is full")
        return first_deleted

    def put(self, key: str, value: Any) -> None:
        if self._count / self._size > 0.7:
            self._resize()
        idx = self._probe(key)
        if self._keys[idx] != key:
            self._count += 1
        self._keys[idx] = key
        self._values[idx] = value

    def get(self, key: str) -> Any:
        idx = self._probe(key)
        if self._keys[idx] == key:
            return self._values[idx]
        raise KeyError(f"Key not found: {key}")

    def delete(self, key: str) -> None:
        idx = self._probe(key)
        if self._keys[idx] != key:
            raise KeyError(f"Key not found: {key}")
        # Tombstone instead of None, otherwise the probe chain breaks
        self._keys[idx] = self._DELETED
        self._values[idx] = None
        self._count -= 1

    def _resize(self) -> None:
        old_keys = self._keys
        old_values = self._values
        self._size *= 2
        self._keys = [None] * self._size
        self._values = [None] * self._size
        self._count = 0
        for key, value in zip(old_keys, old_values):
            if key is not None and key != self._DELETED:
                self.put(key, value)

# This is exactly the scheme CPython uses for dict: open addressing with
# a perturbed probe sequence instead of plain linear probing.

### Сравнение методов

Свойство	Chaining	Open Addressing
Реализация	Проще	Сложнее
Кеш-эффективность	Хуже (указатели)	Лучше (линейная)
Load factor	Может быть > 1	Строго < 1
Удаление	Просто	Нужен DELETED
Кластеризация	Нет	Проблема
Используется в	Java HashMap, PHP array	Python dict

Load Factor

Load factor = количество_элементов / размер_таблицы.

Load factor = 0.5: таблица заполнена наполовину
Load factor = 0.75: типичный порог для resize
Load factor = 1.0: таблица полностью заполнена (для open addressing — плохо!)

Когда load factor превышает порог (обычно 0.75):

Создаём новую таблицу в 2 раза больше
Перехешируем все элементы
Это стоит O(n), но происходит редко — амортизированно O(1)

Сложность операций

Операция	Среднее	Худшее (все коллизии)
Вставка	O(1)	O(n)
Поиск	O(1)	O(n)
Удаление	O(1)	O(n)

Худший случай наступает, когда все ключи попадают в один бакет (плохая хеш-функция или атака).

Хеш-таблицы в PHP

Array (ассоциативный массив)

<?php
declare(strict_types=1);

// PHP array IS a hash table (ordered hash map)
$d = [];
$d['name'] = 'Alice';         // O(1)
echo $d['name'];               // O(1)
unset($d['name']);             // O(1)
isset($d['name']);             // O(1)
array_key_exists('name', $d); // O(1)

// Iteration — O(n), insertion order is preserved!
foreach ($d as $key => $value) {
    echo "{$key}: {$value}\n";
}

package main

import "fmt"

func main() {
	// Go map is a hash table (unordered)
	d := map[string]string{}
	d["name"] = "Alice"          // O(1)
	fmt.Println(d["name"])       // O(1)
	delete(d, "name")            // O(1)

	_, exists := d["name"]       // O(1) existence check
	fmt.Println(exists)

	// Iteration — O(n), order is NOT guaranteed in Go!
	for key, value := range d {
		fmt.Printf("%s: %s\n", key, value)
	}
}

using System;
using System.Collections.Generic;

// Dictionary<K, V> is a hash table with chaining
var d = new Dictionary<string, string>();
d["name"] = "Alice";                    // O(1)
Console.WriteLine(d["name"]);           // O(1)
d.Remove("name");                       // O(1)
bool has = d.ContainsKey("name");       // O(1)
bool found = d.TryGetValue("name", out string? name); // O(1), no exception
Console.WriteLine($"{has} {found} {name}");

// Iteration — O(n), order is NOT guaranteed by contract
foreach (var (key, value) in d)
{
    Console.WriteLine($"{key}: {value}");
}

# dict IS a hash table (open addressing under the hood)
d: dict[str, str] = {}
d["name"] = "Alice"           # O(1)
print(d["name"])              # O(1)
del d["name"]                 # O(1)
print("name" in d)            # O(1)
print(d.get("name", "unknown"))  # O(1), no KeyError on a missing key

# Iteration — O(n), insertion order is preserved since Python 3.7!
for key, value in d.items():
    print(f"{key}: {value}")

> **Запомни:** Хеш-таблица — это массив + хеш-функция. Среднее O(1) для всех операций. Коллизии неизбежны, важно как их разрешать. Load factor > 0.75 = время для resize. PHP array гарантирует порядок вставки и использует chaining для разрешения коллизий.

Итоги

Хеш-функция: ключ -> индекс в массиве
Коллизии: chaining (списки) vs open addressing (проба)
Среднее O(1), худшее O(n)
Load factor ~ 0.75 — порог для resize
Resize = O(n), но амортизированно O(1) на операцию