Как работают хеш-таблицы?

Question

Я знаю о создании хеш-кодов, коллизиях, отношениях между .GetHashCode и .Equals и т. Д.

Что я не совсем понимаю, так это как 32-битное число хеш-кодов используется для получения ~ O (1) поиск.Если у вас есть достаточно большой массив для размещения всех возможностей в 32-битном числе, то вы получите ~ O (1), но это будет пустой тратой памяти.

Я предполагаю, что внутренне класс Hashtable создает небольшой массив (например, 1K-элементы), а затем перефразирует 32-битное число в 3-значное число и использует его в качестве поиска.Когда количество элементов достигает определенного порогового значения (скажем, 75%), оно расширяет массив до чего-то вроде 10K-элементов и пересчитывает внутренние хэш-числа в 4-значные числа, конечно же, на основе 32-битного хеша.

Кстати, здесь я использую ~ O (1) для учета возможных коллизий и их разрешений.

Правильно ли я понял суть или я совершенно не в курсе?

Answer 1

Я предполагаю, что класс Hashtable внутри себя создает небольшой массив (например, 1 КБ элементов), а затем перефразирует 32-битное число в 3-значное число и использует его для поиска.

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

Когда количество элементов достигает определенного порога (скажем, 75%)

Если вы имеете в виду реализацию Java Hashtable, тогда да. Это называется коэффициентом загрузки. Другие реализации могут использовать 2/3 вместо 3 / 4.

это расширило бы массив до чего-то вроде 10K элементов

В большинстве реализаций емкость не будет увеличена в десять раз, а увеличена вдвое (для хеш-таблиц степени двух) или умножена примерно на 1,5 + расстояние до следующего простого числа.

Answer 2

В хеш-таблице есть несколько ячеек, содержащих элементы.Количество корзин довольно мало для начала.Учитывая хеш-код, он просто использует хеш-код по модулю bincount, чтобы найти корзину, в которой должен находиться элемент.Это дает быстрый поиск (Найти корзину для элемента: Взять по модулю хеш-кода, готово).

Или в (псевдо) коде:

int hash = obj.GetHashCode();
int binIndex = hash % binCount;
// The item is in bin #binIndex. Go get the items there and find the one that matches.

Очевидно, как вы выяснилисами, в какой-то момент стол должен будет расти.Когда это происходит, создается новый массив корзин, а элементы в таблице перераспределяются в новые корзины.Это также означает, что рост хеш-таблицы может быть медленным.(Таким образом, в большинстве случаев прибл. O (1), если только вставка не вызывает внутреннее изменение размера. Поиски всегда должны быть ~ O (1)).

Answer 3

В целом, существует несколько вариантов того, как хеш-таблицы обрабатывают переполнение.

Многие (включая Java, если память служит) изменяют размер, когда коэффициент загрузки (процент используемых корзин) превышает определенный процент,Недостатком этого является то, что скорость является ненадежной - большинство вставок будет O (1), но некоторые будут O (N).

Чтобы смягчить эту проблему, некоторые вместо этого постепенно изменяют размер: когда нагрузкакоэффициент превышает магическое число, они:

1. Создать вторую (большую) хеш-таблицу.
2. Вставьте новый элемент в новую хеш-таблицу.
3. Переместите немногоэлементы из существующей хеш-таблицы в новую.

Затем каждая последующая вставка перемещает другой кусок из старой хеш-таблицы в новую.Это сохраняет O (1) среднюю сложность и может быть записано так, чтобы сложность для каждой вставки была практически постоянной: когда хеш-таблица становится «полной» (т. Е. Коэффициент загрузки превышает вашу точку запуска), вы удваиваете размер таблицы.Затем в каждую вставку вы вставляете новый элемент и перемещаете один элемент из старой таблицы в новую.Старая таблица будет очищаться в точности по мере заполнения новой, поэтому каждая вставка будет включать в себя ровно две операции: вставка одного нового элемента и перемещение одного старого, поэтому скорость вставки остается практически постоянной.

Есть и другие стратегии.Одна из них, которая мне особенно нравится - это сделать хеш-таблицу таблицей сбалансированных деревьев.При этом вы обычно полностью игнорируете переполнение.Когда хеш-таблица заполняется, вы просто получаете больше элементов в каждом дереве.Теоретически это означает, что сложность равна O (log N), но для любого практического размера она пропорциональна log N/M, где M = количество сегментов.Для практических диапазонов размеров (например, до нескольких миллиардов элементов) это по существу постоянно (log N растет очень медленно), и это часто немного быстрее для самой большой таблицы, которую вы можете поместить в память, и потерянбыстрее для меньших размеров.Недостатком является то, что это действительно практично, когда объекты, которые вы храните, достаточно велики - если вы сохраняете (например) один символ на узел, накладные расходы от двух указателей (плюс, как правило, информация о балансе) на узел будут чрезвычайновысокий.