Хеш-таблицы

Функция преобразования ключа в индекс массива. Свойства: детерминированность, равномерность распределения, быстрое вычисление. Примеры: деление по модулю, умножение, универсальное хеширование.

Методы обработки одинаковых хешей: метод цепочек (chaining, список в ячейке), открытая адресация (linear probing, quadratic, double hashing). Цепочки: O(1) средний случай, O(n) худший.

Отношение числа элементов к размеру таблицы: α = n/m. При α > 0.7 производительность падает, требуется rehashing (увеличение таблицы в 2 раза, перехеширование всех элементов). Java HashMap: порог 0.75.

Хеш-функция без коллизий для заданного набора ключей. Минимальное идеальное хеширование: m = n. Используется для статических словарей (ключевые слова языка). Построение: универсальное хеширование + двухуровневая схема.

Хеш-таблицы в стандартных библиотеках: Python dict (open addressing с рандомизацией), Java HashMap (цепочки), C++ unordered_map (цепочки). Rehashing при load factor > 0.75. Benchmarks показывают O(1) среднее.

Разрешение коллизий связными списками в ячейках. Простая реализация, работает при любом заполнении. Среднее O(1+α) где α — коэффициент заполнения.

При коллизии ищет свободную ячейку (линейное/квадратичное пробирование). Лучше кэшируется. Удаление требует меток. Применяется в Python dict.