Основы хеширования
Что такое хеш-таблица?
Хеш-таблица — структура данных, которая связывает ключи со значениями через хеш-функцию. Обеспечивает доступ, вставку и удаление в среднем за O(1).
Ключ "apple" ---> hash("apple") = 3 ---> bucket[3] = "яблоко"
Ключ "banana" --> hash("banana") = 7 ---> bucket[7] = "банан"
Ключ "cherry" --> hash("cherry") = 3 ---> КОЛЛИЗИЯ! bucket[3] уже занят
Хеш-функция
Хеш-функция преобразует ключ произвольного размера в число фиксированного размера (индекс в массиве).
Требования к хорошей хеш-функции
- Детерминированность — один и тот же вход всегда даёт один и тот же выход
- Равномерное распределение — ключи распределяются по бакетам равномерно
- Скорость — вычисляется быстро
- Лавинный эффект — маленькое изменение ключа сильно меняет хеш
Примеры хеш-функций
PHPGo
<?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
}
- 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
PHPGo
<?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)
}
}
}
При коллизии ищем следующее свободное место в самом массиве.
Linear Probing: проверяем следующий бакет по очереди.
hash("apple") = 3
hash("cherry") = 3 <- коллизия! Проверяем 4... занят, 5... свободен!
Бакеты:
[0] [1] [2] [3:apple] [4:banana] [5:cherry] [6] [7]
^ ^
оба имеют hash=3 нашли свободное место
PHPGo
<?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])
}
}
}
| Свойство | 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
PHP: array (ассоциативный массив)
PHPGo
<?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)
}
}
Итоги
- Хеш-функция: ключ -> индекс в массиве
- Коллизии: chaining (списки) vs open addressing (проба)
- Среднее O(1), худшее O(n)
- Load factor ~ 0.75 — порог для resize
- Resize = O(n), но амортизированно O(1) на операцию