Визуализация
Сценарий: Пробирование
Легенда цветов
Как работает открытая адресация
Идея структуры: В отличие от метода цепочек, в открытой адресации все элементы хранятся в самом массиве хеш-таблицы. Никаких связных списков и дополнительных узлов не создается. Если при добавлении нужный слот (корзина) оказался занят, мы просто ищем следующий свободный слот.
Линейное пробирование (Linear Probing). Самый простой способ найти свободный слот -
шагать вперед по одному: hash, hash+1, hash+2 и так далее, пока
не встретится пустая ячейка. В нашей анимации показан именно этот метод. Бывают и другие стратегии пробирования
(квадратичное, двойное хеширование) для борьбы с кластеризацией.
Как считаются пробы. Ячейка, в которую ключ ведет напрямую по хешу, называется домашней, и она же считается пробой номер один: мы в нее заглянули, чтобы понять, свободна она или занята. Поэтому ключ, найденный сразу на своем месте, стоит одну пробу, а ключ, до которого пришлось шагнуть на две ячейки вперед, - три. Счетчик "Проб" под визуализацией считает именно так, как урок курса.
Коэффициент загрузки (Load Factor). В открытой адресации он никогда не может превысить 1 (100%), так как в каждой ячейке хранится максимум один элемент. Обычно таблицу пересоздают (перехешируют), когда она заполняется на 70%, чтобы избежать длинных серий проб.
Удаление и надгробия (Tombstones). Нельзя просто удалить элемент из массива, сделав слот пустым. Иначе мы разорвем цепочку проб, и поиск других элементов может ошибочно остановиться слишком рано. Вместо этого в слот записывают специальный маркер "удалено" (надгробие), который при вставке считается свободным, а при поиске означает "иди дальше".
Другой путь. Альтернатива пробированию - метод цепочек: там ключи с одинаковым хешем связываются в список внутри своей корзины, зато появляются отдельные узлы и указатели. Сравните две анимации на одних и тех же коллизиях.
Синонимы названия: Линейное пробирование, open addressing.
Сложность
Сложность - это оценка того, как быстро растет потребление ресурса при росте числа элементов n. Ресурса у структуры два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.
Производительность сильно зависит от коэффициента загрузки. Чем плотнее заполнен массив, тем длиннее будут пробы.
По времени
| Операция | В среднем | В худшем случае |
|---|---|---|
| Поиск ключа | O(1) | O(n) - поиск нужного ключа в длинном кластере |
| Вставка | O(1) | O(n) - долгий поиск свободного слота |
| Удаление | O(1) | O(n) - долгий поиск удаляемого слота |
По памяти
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Затраты по памяти | O(K) | Выделяется только один массив размера K. Никаких указателей, как в методе цепочек. |
Свойства
| Свойство | Значение | Комментарий |
|---|---|---|
| Разрешение коллизий | Открытая адресация | При коллизии выполняется поиск следующей свободной ячейки (линейное пробирование). |
| Локальность кэша | Высокая | Все элементы хранятся в едином сплошном массиве слотов без выделения отдельных узлов. |
| Предел заполнения | α < 1.0 | Таблица не может вместить больше элементов, чем слотов в массиве (требуется своевременный resize). |
Примеры реализации: Хеш-таблица с открытой адресацией (Open Addressing)
Код на C
#include <stdio.h>
#include <stdbool.h>
#define TABLE_SIZE 8
#define EMPTY -1
#define DELETED -2 // Надгробие (Tombstone) для удаленных элементов
int hashTable[TABLE_SIZE];
// Инициализация пустой таблицы
void init() {
for (int i = 0; i < TABLE_SIZE; i++) {
hashTable[i] = EMPTY;
}
}
// Вставка ключа с линейным пробированием
bool insert(int key) {
int idx = key % TABLE_SIZE;
int startIdx = idx;
// Ищем пустой слот или надгробие
while (hashTable[idx] != EMPTY && hashTable[idx] != DELETED) {
// Если такой ключ уже есть - не вставляем дубликат
if (hashTable[idx] == key) return true;
// Линейное пробирование: шаг + 1
idx = (idx + 1) % TABLE_SIZE;
// Защита от бесконечного цикла, если таблица полна
if (idx == startIdx) return false;
}
hashTable[idx] = key;
return true;
}
// Поиск ключа
bool search(int key) {
int idx = key % TABLE_SIZE;
int startIdx = idx;
// Идем по цепочке проб, игнорируя надгробия
while (hashTable[idx] != EMPTY) {
if (hashTable[idx] == key) return true; // Нашли
idx = (idx + 1) % TABLE_SIZE;
if (idx == startIdx) break; // Обошли всю таблицу
}
return false; // Не нашли
}
// Удаление ключа
void delete(int key) {
int idx = key % TABLE_SIZE;
int startIdx = idx;
while (hashTable[idx] != EMPTY) {
if (hashTable[idx] == key) {
// Ставим надгробие, чтобы не порвать цепь проб для других ключей
hashTable[idx] = DELETED;
return;
}
idx = (idx + 1) % TABLE_SIZE;
if (idx == startIdx) return;
}
}Код на Python
# Для упрощения будем использовать специальные константы
EMPTY = None
DELETED = "DELETED" # Надгробие (Tombstone)
class OpenAddressingTable:
def __init__(self, size=8):
self.size = size
# Массив корзин
self.table = [EMPTY] * size
def hash_func(self, key):
return key % self.size
def insert(self, key):
idx = self.hash_func(key)
start_idx = idx
# Линейное пробирование: ищем EMPTY или DELETED
while self.table[idx] is not EMPTY and self.table[idx] is not DELETED:
if self.table[idx] == key:
return # Ключ уже есть
idx = (idx + 1) % self.size
if idx == start_idx:
raise Exception("Хеш-таблица переполнена!")
self.table[idx] = key
def search(self, key):
idx = self.hash_func(key)
start_idx = idx
# Перебираем слоты. Надгробия (DELETED) пропускаем.
# Останавливаемся только встретив EMPTY.
while self.table[idx] is not EMPTY:
if self.table[idx] == key:
return True
idx = (idx + 1) % self.size
if idx == start_idx:
break
return False
def delete(self, key):
idx = self.hash_func(key)
start_idx = idx
while self.table[idx] is not EMPTY:
if self.table[idx] == key:
self.table[idx] = DELETED # Оставляем надгробие
return
idx = (idx + 1) % self.size
if idx == start_idx:
breakКод на JavaScript
const EMPTY = null;
const DELETED = Symbol('DELETED'); // Уникальный маркер-надгробие
class OpenAddressingTable {
constructor(size = 8) {
this.size = size;
this.table = new Array(size).fill(EMPTY);
}
hash(key) {
return key % this.size;
}
insert(key) {
let idx = this.hash(key);
const startIdx = idx;
// Линейное пробирование (шаг 1)
while (this.table[idx] !== EMPTY && this.table[idx] !== DELETED) {
if (this.table[idx] === key) return; // Дубликаты не нужны
idx = (idx + 1) % this.size;
if (idx === startIdx) throw new Error('Таблица переполнена');
}
this.table[idx] = key;
}
search(key) {
let idx = this.hash(key);
const startIdx = idx;
while (this.table[idx] !== EMPTY) {
if (this.table[idx] === key) return true;
idx = (idx + 1) % this.size;
if (idx === startIdx) break; // Прошли полный круг
}
return false;
}
deleteKey(key) {
let idx = this.hash(key);
const startIdx = idx;
while (this.table[idx] !== EMPTY) {
if (this.table[idx] === key) {
// Если просто записать EMPTY, то мы оборвем цепочку
// поиска для других элементов, хеш которых совпадает!
// Поэтому ставим специальную метку DELETED.
this.table[idx] = DELETED;
return true;
}
idx = (idx + 1) % this.size;
if (idx === startIdx) break;
}
return false;
}
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про методы рехеширования - с подробной теорией, задачами и проверочными вопросами.