Как устроены хэш-таблицы?

Question

[DarkByte2015]

Озадачился тут вопросом хэш-таблиц. Нашел вот такую статью. Не очень правда понял про закрытую адресацию (там еще и пример на паскале... и не полный). Но главное - правильно ли я понимаю что хэш-таблицы жестко ограничены размером? Т.е. хэш-таблица как статичный массив - на сколько элементов создашь столько и будет и увеличить в дальнейшем ее размер никак нельзя? Судя по тому алгоритму который там приводится это так...

P.S. Так кстати все-таки какой алгоритм лучше? С открытой или закрытой адресацией?

Answer 1

[Rsa97]

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

Очевидно, что открытый вариант несколько более сложен в реализации, но при этом гораздо более гибок и хорошо расширяем. Достоинством является то, что получив хэш простым перебором списка мы можем получить все значения, с таким хэшем.
Закрытый вариант имеет фиксированное потребление памяти и более простую реализацию, но при многочисленных коллизиях даёт низкую эффективность, поскольку надо перебирать ячейки в поисках значений с нужным хэшем.

Comments

[DarkByte2015]

А можете немного пояснить приведенный там алгоритм? Я все таки пока никак не пойму в чем смысл... Хэш-таблица это же как правильно там написано - реализация словаря. Т.е. по идее там должны быть не методы insert, find, delete, а get, set, remove (ну можно и delete назвать) принимающие ключ и само значение. А тут в этой реализации я так понимаю они принимают только значение и используют его как ключ почему-то... Очень странно как-то. Я даже не понимаю как это вообще использовать можно.

[Rsa97]

DarkByte2015: Ключ - это хэш, он вычисляется из самого значения. Например для строки хэшем может служить код первого символа.
Соответственно методы, которые там реализованы - добавление записи (скажем, слова), поиск такого слова и удаление слова из словаря.

[DarkByte2015]

Rsa97: Не, ну это же вообще не то... Классический пример для высокоуровневых языков (типа PHP или Python): get(key), set(key, value), remove(key). Ключ может быть любого типа, но обычно текстовый. То что вы говорите выглядит реально странно и не понятно. А что будет если я например еще одно такое же значение insert-ну? Возможно было бы логичнее переделать алгоритм таким образом чтобы p->data = KeyValuePair вместо просто data?

[Rsa97]

DarkByte2015: Ну и вставите такое же значение, возникнет коллизия, она решится одним из двух способов.
Представьте предельный случай - ключ равен данным, получите простейший словарь. В нём элемент либо присутствует в словаре, либо отсутствует.
Никто не мешает вставить и пару ключ/значение, при этом хэш будет браться от ключа, а значение пойдёт просто в нагрузку к ключу.

[DarkByte2015]

Rsa97: а вот еще вопрос возник: для хэш функции же требуется число, а что если брать просто указатель на ключ в качестве этого самого числа? Тогда можно будет использовать в качестве ключа void* и передавать туда что угодно. Указатель по идее будет уникальным. Или например еще для большей уникальности сложить hash((int)(&key + key)) (где void* key).

[DarkByte2015]

Хотя нет - бред. Как раз таки раз указатель уникальный - в следующий раз при get уже она его не найдет... Как же быть. :( Например в C# для этих целей наверняка используется GeHashCode. А что тут юзать я не знаю.

[Rsa97]

DarkByte2015: А какой будет размер таблицы при использовании в качестве ключа void*? А будет он 8*2⁶⁴ байт, или 128 эксабайт.
Хэш-функция берётся с таким расчётом, чтобы максимально равномерно разбить всё входное множество на небольшие группы, поиск в которых будет быстрее, чем поиск во всём множестве.
Например, если посмотрите на систему хранения файлов во WSUS, то увидите 256 каталогов, от 00 до FF - это один из примеров хэш-таблицы, где ключом являются последние два символа MD5 файла.

[Rsa97]

DarkByte2015: Что именно использовать - зависит от данных, которые будут храниться в словаре. Тут вопрос лишь в том, чтобы хэш-функция считалась быстрее, чем полный поиск по данным.
Для ASCII-строк, например, можно взять первый символ. Для строк utf-8 - перевести первый символ в ucs16 и сложить байты по модулю 256. Если много данных, отличающихся лишь несколькими байтами, можно взять CRC8 или CRC16.

[DarkByte2015]

Rsa97: первый символ это не уникально же вообще получится? Т.е. для строк "abc" и "acb" выдаст один и тот же хэш например. И в чем тогда смысл? Складывать символы тоже не надежно, т.к. нет гарантии что при каком то другом сочетании символов не получится та же самая сумма. Возможно и правда стоит посмотреть в сторону CRC. Только возникает вопрос - а есть ли вообще во всем этом смысл? Хэш таблица вместо обычного словаря на списках имеет смысл только из-за скорости. Но если тут еще будет хэширование, циклы... Не потеряется ли вообще этот самый бонус скорости?

[Rsa97]

DarkByte2015: А кто говорит, что хэш-таблицы всегда нужны? Зачастую гораздо эффективнее дерево или сортированный список.
Что касается уникальности - она для хэша невозможна в принципе. Если вам надо записать в словарь десять тысяч слов, а хэш даёт 256 значений, то уникальности не будет в принципе, но вместо поиска в 10000 записей искать придётся, в среднем, в 10000/256 = 39 элементах.

[DarkByte2015]

Rsa97: Ну вот например в реализациях json обычно что используется? Хэш-таблица или список из пар ключ-значение? И еще, тогда зачем вообще нужна эта структура данных если она такая не эффективная? :D Где ее можно использовать?

[Rsa97]

DarkByte2015: В основном хэш-таблицы как раз используются для ускорения поиска, особенно в случае медленного доступа к самим данным.
Пары ключ/значение - это ассоциативный массив. В его реализации хэш-таблица может использоваться для ускорения поиска ключа.
Хэш-таблица выгодна, когда затраты на расчёт хэша существенно ниже, чем на сравнение значений. Например, при поиске файла гораздо выгоднее посчитать хэш-сумму и сверять сначала по ней, а уже затем по содержимому, особенно если это однотипные файлы с одинаковыми заголовками. И, даже если несколько файлов будут иметь одинаковый хэш, сравнение по ним будет быстрее, чем прямой перебор по всем файлам.