полный текст этого раздела государств, с последним пунктом является тот, который вы просили о:
Хэш таблица представляет собой структуру данных, которая отображает ключи к значениям для высокоэффективного поиска. В очень простая реализация хэш-таблицы, хэш-таблица имеет базовый массив и - хеш-функцию. Когда вы хотите вставить объект и его ключ, хэш-функция отображает ключ целого числа, который указывает индекс в массиве. Затем объект хранится в , что индекс.
Как правило, это не будет работать правильно. В приведенной выше реализации значение хеша должно быть уникальным, или мы можем случайно перезаписать данные. Массив должен быть чрезвычайно большим - размер всех возможных ключей - для предотвращения таких столкновений ".
Вместо того, чрезвычайно большой массив и хранения объектов в индексном хэш (ключ), мы можем сделать массив намного меньше и хранить объекты в связанном списке под индексом хэш (ключ)% array_length.To получить объект с определенным ключом, мы должны искать связанный список для этого ключа.
В качестве альтернативы мы можем реализовать хэш-таблицу с двоичным деревом поиска. Мы можем тогда гарантировать время поиска (log n), так как мы можем сохранить сбалансированное дерево. Кроме того, мы можем использовать меньше места, так как большой массив больше не нужно выделять в самом начале .
Таким образом, они говорят об использовании BST (двоичного дерева поиска) для обработки столкновений . Это не будет на самом деле имеет смысла использовать BST как единственной структура данных, так как весь смысл правильно настроенный хэш, что просмотровые на порядке O(1), гораздо лучше, чем O(log n) от BST , Кроме того, с использованием BST для полностью реализации хэш-таблицы означает, что это не на самом деле хэш-таблицу :-)
Однако, считают, что, когда у вас есть коллизий в хэш-таблице, частый способ обрабатывать их, чтобы каждый ковш содержал связанный список его элементов. В вырожденном случае (все элементы хеширования в том же ковше) вы получаете только связанный список, а O(1) превращается в O(n).
Таким образом, вместо связанного списка в каждом ведре у вас есть BST. Тогда у вас больше нет сложности поиска O(n) в тех случаях, когда одно ведро имеет много элементов (ранее упомянутые коллизии).
Вы используете хеш-функцию для поиска ведра в O(1), затем выполните поиск по BST в O(log n), если есть столкновения. В лучшем случае (по одному предмету на ведро) все равно O(1). В худшем случае становится O(log n), а не O(n).
Единственное, что изначально касалось меня в этой теории, заключается в том, что они также обсуждают тот факт, что большее выделение больше не требуется. Если это общая комбинация хеш/BST, вы должны еще нужно выделить всю таблицу хэша так, чтобы это казалось несоответствующим.
Однако из контекста («... так как большого массива больше не нужно выделять ...»), кажется, что они означают, что они могут сделать хэш-таблицу часть двойственных данных меньше, поскольку коллизии более эффективны для обработки. Другими словами, вместо хеш-таблицы из 1000 элементов со связанными списками для коллизий вы можете избавиться от хеш-таблицы из 100 элементов, потому что столкновение не так вредно для времени поиска, если вы используете BST.
Я бы предположил, что BST будет * только * быть для столкновений; у него есть аналогия, сходная с цепным хеш-подходом, который стоил бы O (N) для извлечения; в этом сценарии предпочтительнее BST. – Makoto
На самом деле, C++ std :: map реализуется с использованием BST в целом. Преимущества: 1. Больше не нужно беспокоиться о столкновениях 2. Ключи упорядочены так, чтобы вы могли совершать обход в порядке. Я думаю, что авторы на самом деле означали этот способ вместо того, чтобы использовать BST для обработки только столкновения. – SHH