обычная реализация хеш-таблицы по сравнению с деревом

Question

Обычно (как в C ++) хеш-функция возвращает любое значение size_t - таким образом, возможно много разных хеш-значений (2 ^ 32).

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

Кажется, что фактическая реализация сложнее, чем я думал.То, что я всегда имел в виду, что такое наивная реализация, выглядит примерно так:

typedef list< pair<Key,Value> > Bucket;
typedef map< size_t, Bucket > Hashtable;

Теперь мой вопрос: чем эта наивная реализация отличается от реальных реализаций в практике с точки зрения сложности (времени выполнения ипамять)

Answer 1

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

Предполагается, что вы говорите о сложности времени.

Ожидается, что хеш-таблицы будут иметь O (1) доступ в лучшем случае.Ваше предложение по реализации в этом вопросе использует map<size_t,Bucket> для доступа к сегментам, что приведет к O (log n) временной сложности.Вам нужно что-то с O (1) сложностью времени доступа, например vector<Bucket>, чтобы соответствовать ожидаемой сложности времени хеш-таблицы.

Подробнее

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

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

В худшем случае каждый ключ имеет одинаковое хеш-значение, и доступ по ключу фактически выполняет поиск в списке, что приводит к поведению O (n).

Реальное использование обычно находится где-то между этими крайностями, возможно, ближе к O (1).

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

Answer 2

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

typedef list< pair<Key,Value> > Bucket;
const int HashSize = 511;
Bucket[HashSize] Hashtable;
inline size_t HashIndex(Key k) { return hash(k) % HashSize; }

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

Answer 3

Это зависит. Если хеш-функция хорошо выполняет равномерное распределение хеш-ключей и таблица не слишком полная, вы получите примерно O (1). Хэш-таблица получит правильное попадание с относительно небольшим количеством коллизий.

Если таблица экстенсивно связана (т. Е. Заполнена), то процесс исследования будет тратить больше времени на разрешение коллизий. В теоретическом наихудшем случае все значения будут отображаться на один и тот же хеш-ключ, и хеш-функция будет тратить все свое время на трассировку вниз по цепочке, что равно O (n).

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

Дерево будет O (log n), а не O (1), хотя, если дерево не сбалансировано, поиск также может превратиться в эффективно линейную операцию. Обратите внимание, что это проблема в некоторых распространенных сценариях, например, когда узлы вставляются в порядке ключей (представьте себе операцию поверхностного копирования в коллекции на основе дерева). Как правило, алгоритмы сбалансированного дерева, такие как красно-черные деревья, используются для поддержания эффективности дерева. Другое преимущество деревьев состоит в том, что можно обходить дерево по порядку и создавать упорядоченный список ключей без необходимости их явной сортировки.

1. Пример операции хеширования с относительно дешевыми затратами на расширение см. Таблица линейного хеширования (wi.ipedia.org).

Answer 4

Сама проблема с вашим вопросом, Альберт, заключается в том, что не существует ОДНОЙ хеш-таблицы, их много.

Суть проблемы здесь заключается в сложности big-O, данной для некоторых операций.В среднем хеш-таблица должна давать O (1) сложность для поиска элемента.Бинарное дерево дает в среднем O (log N).

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

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

• Хеш-таблицы могут быть или не быть реализованы в терминах сегментов: реализация без сегментов включает схемы с открытой адресацией (которые, кстати, более дружественны к кешу).
• Контейнеры могут быть или не быть реализованы в терминах связанного списка.Другие схемы включают использование другой хеш-функции (каждое ведро является самой хеш-таблицей) или двоичного дерева (карты), хотя последнее требует некоторого упорядочения.
• Перераспределение может быть выполнено сразу: т.е. как только вы превыситеЧтобы разместить новую (большую) хеш-таблицу и скопировать весь контент или использовать линейную схему перераспределения, чтобы сгладить затраты на перераспределение и время от времени избегать большого успеха.

Прочитать статьюв Википедии он обращается к этим и другим пунктам.