Хэш-таблица-реализация с бинарным деревом поиска

Из взлом интервью с кодировщиком , стр. 71:

Альтернативно, мы можем реализовать хэш-таблицу с BST. Тогда мы сможем гарантируйте время поиска O(log n), так как мы можем сохранить дерево сбалансированный. Кроме того, мы можем использовать меньше места, так как большой массив нет больше нужно выделять в самом начале.

Я знаю основы связанных списков, хэш-таблиц и BST, но я не могу понять эти строки. Что это на самом деле означает? Будет ли это окончательная структура данных будет Трие?

3 3
data-structures hashtable binary-search-tree

3 ответа:

Полныйтекст этого раздела гласит, что последний абзац является тем, о котором вы спрашивали:

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

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

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

Альтернативно, мы можем реализовать хэш-таблицу с бинарным деревом поиска. Тогда мы сможем гарантируйте время поиска 0 (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).

Единственная вещь, которая первоначально беспокоила меня в этой теории, - это то, что они также обсуждают тот факт, что большое распределение больше не является необходимым. Если это общая комбинация hash/BST, вам все равно нужно выделить всю хэш-таблицу так, чтобы она казалась неуместной.

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

5

Вы путаете здесь несколько терминов.

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

  • A trie - это нечто совершенно иное; в зависимости от того, что вы пытались сохранить, вы не сможете применить его к a функция хеширования.

1

Привязка O(logN) будет наихудшим сценарием в случае дерева.Давайте посмотрим на это с другой стороны. Мы вставляем 45, 33, 55,66,22, и тогда у нас будет 45 в качестве корневого узла, 33 и 55 на уровне 1, 22 и 66 на уровне 2..

Так что, если вы были для хэш-значение 45, он все равно будет O(1) операция...Только когда вы смотрите на узлы в Level2 бы это количество близко к O(Фремонт, Калифорния)....Дерево может быть деревом RB / AVL, чтобы оно не вырождалось в связанный список....Вы теряете некоторую эффективность тиэм, но компенсируйте это космической эффективностью..

Еще одним преимуществом было бы то, что вам не нужно беспокоиться о столкновениях в хэш-таблице. http://www.cs.rit.edu/~ib / Classes / CS233_Spring08-09 / Slids / Week9_Hashing. pdf

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

1