#hash #hashtable
#хэш #хеш-таблица
Вопрос:
Насколько я знаю, цель хеш-функции — распределить данные как можно более равномерно, когда у вас возникает коллизия, у вас есть несколько вариантов:
- Ищите следующий пустой слот
- Создайте другой хэш и попытайтесь вставить его куда-нибудь еще
- Поместите его в переполняемый контейнер (может быть список, другая хеш-таблица или что-то еще)
- Поместите его в следующий свободный слот для сегментов
Последнее меня беспокоит, потому что, если вы собираетесь создать хэш-таблицу, скажем, с 2 слотами для каждого адреса, почему бы просто не создать хэш-таблицу вдвое большего размера? Это если только сегменты не распределяются динамически. В моем случае, когда данные таблицы находятся на диске, это означало бы другой доступ к диску управление данными переменной длины. Мне кажется, что сегменты по-прежнему являются наиболее предпочтительным вариантом, почему это так? Чего мне не хватает?
Комментарии:
1. «Мне кажется, что сегменты по-прежнему являются наиболее предпочтительным вариантом» почему? Первый вариант, который называется линейным хешированием, является самым простым и (что немного удивительно) по-прежнему наиболее эффективным в большинстве случаев.
2. Чем «1. Найдите следующий пустой слот» должен отличаться от «4. Поместите его в следующий свободный слот для сегментов»? Это терминология, к которой вы привыкли, с фиксированным количеством «слотов» на сегмент? Вы говорите «2 слота для каждого адреса » — вы имеете в виду для каждого сегмента? «сегменты распределяются динамически» — вы снова ссылаетесь на «3». — поскольку динамические сегменты звучат так, как будто они являются списками / векторами для меня.
3. В любом случае, для дисковых таблиц загрузка области диска обходится дорого, поэтому лучше использовать любую свободную область, прежде чем прибегать к поиску в другой области диска. Я не рекомендую использовать несколько «слотов» на сегмент — просто попробуйте другой сегмент. Хорошая идея — использовать «список перемещений», который перемещает несколько сегментов (возможно, перенос на несколько попыток в пределах загруженной области диска, затем выполните поиск методом перебора, затем перейдите в другую область диска или перефразируйте). Списки смещений должны избегать запусков, сумма которых повторяется: например, 1 3 6 в порядке (3-1 ! = 6-3, n*(3-1) != 6-1), 11 тогда плохо: 6-1 == 11-6, 13 ок….
4. @TonyD первый комментарий: он отличается тем, что в # 4 у вас будет несколько предварительно выделенных пробелов для kvp на хэш. Да, да. Нет, я подразумеваю, что единственный способ, которым сегменты имеют смысл для меня, — это если они были динамически выделены для экономии памяти, да. второй комментарий: Да, это в значительной степени ставит точку на # 2. И да, это звучит как отличная идея.
5. @KarliRaudsepp: идея нескольких предварительно выделенных пробелов для каждого хэш-значения бесполезна… учитывая дополнительное использование памяти, вам лучше распределить хэши по всей доступной памяти, чтобы для начала было меньше коллизий, а затем обрабатывать коллизии с использованием любого из рассмотренных методов цепочки / перефразирования / списка смещений.
Ответ №1:
Как, вероятно, видно из обсуждения в комментариях к этому вопросу, существует много разных способов реализации хэш-таблицы. У каждого есть свои компромиссы.
Ваш вопрос заключается в том, почему вы хотели бы использовать систему группирования (замкнутая адресация или хеширование с цепочкой), а не просто перенос объекта в следующий свободный слот (линейное зондирование). Вы указываете, что для хранения сегментов во внешней памяти требуется поиск в другом месте памяти, что не очень хорошая идея, если вы храните данные на диске. Все это обоснованные опасения. Тем не менее, вот несколько вещей, которые следует иметь в виду.
Во-первых, если вы используете систему группирования (каждый слот хэш-таблицы представляет собой сегмент, и все объекты с одинаковым хэш-кодом попадают в один и тот же сегмент), у вас есть одно преимущество перед такими системами, как линейное зондирование, которые используют открытую адресацию: вам нужно беспокоиться только о коллизиях для объектов сидентичные хэш-коды. В качестве примера предположим, что вы вставляете три элемента в хеш-таблицу, а их хеш-коды равны 1, 1 и 2. При закрытой адресации (сегментах) всякий раз, когда вы выполняете поиск для 1, вам нужно будет проверять оба объекта с помощью хэш-кода 1, но если вы ищете объект 2, вам вообще не нужно выполнять какое-либо разрешение конфликтов. С другой стороны, если вы используете линейное зондирование, у вас могут возникнуть коллизии при поиске любого из трех элементов. Допустим, что объект A имеет хэш-код 1, объект B имеет хэш-код 2, а объект C также имеет хэш-код 1. Вставка объектов в порядке A, C, B даст эту таблицу:
[ A ] [ C ] [ B ] [ ] [ ]
1 2 3
Теперь для выполнения поиска для C или B потребуется выполнить линейное сканирование таблицы, даже если B не сталкивается с объектами A или C. В зависимости от вашего приложения это может стать реальной проблемой.
С другой стороны, если вы используете пакетирование, как вы уже упоминали, вам нужно выполнить какой-то доступ к внешней памяти, который будет несколько медленным в основной памяти (из-за локальности ссылок) и ледяным на диске. Это довольно хороший аргумент, объясняющий, почему хеширование с цепочкой не было бы хорошей идеей для хеш-таблицы на диске, в то время как линейное зондирование, вероятно, было бы разумным компромиссом.
Надеюсь, это поможет!