Решения хэш-таблиц возьмут хеш объектов, хранящихся в них (важно отметить, что хеш-код является примитивом, часто целым или длинным), и используют этот хэш в качестве индекса массива и сохраняют ссылку на объект вэтот индекс в массиве.Чтобы решить проблему коллизий, индексы в этом массиве часто будут содержать узлы связанного списка, которые содержат фактические ссылки.
Проверка наличия объекта в массиве так же проста, как его хеширование, поиск индекса, на который ссылается хеш, и сравнение равенства с каждым имеющимся объектом, операция, которая выполняется в амортизированном постоянном времени, потому чтохеш-таблица может увеличиваться, если начинают накапливаться коллизии.
Теперь к вашим вопросам.
Вопрос 1
Должны ли мы использовать простое двоичное дерево илиBST?
BST обозначает дерево двоичного поиска.Разница между ним и «простым» двоичным деревом состоит в том, что оно строго упорядочено.Оптимальные реализации также попытаются сохранить дерево сбалансированным.Поиск в сбалансированном упорядоченном дереве намного проще, чем в неупорядоченном, потому что некоторые предположения о расположении целевого элемента не могут быть сделаны в неупорядоченном дереве.Вы должны использовать BST, если это возможно.
Вопрос 2
Как мы представляем ключи в дереве?Рассчитываем ли мы хеш-функцию на ключе и вставляем (ключ, значение) на основе целочисленного хеш-значения?
Это будет то, что делает хеш-таблица.Даже хеш-таблицы должны хранить ключи по значению для проверки на равенство из-за возможности коллизий.BST вообще не будет хранить хэши, потому что при всех непростых обстоятельствах определение порядка сортировки по значениям хэшей будет очень трудным.Вы должны использовать пары (ключ, значение) без хеширования.
Вопрос 3
Если мы предположим, что мы вычисляем значение хеша и вставляем в дерево, почему люди говорят, что деревья или упорядочены?Какой порядок он сохраняет и как?Что нам дает этот заказ?
Как вы заметили, это не работает таким образом.Таким образом, мы храним значение ключа вместо хеша.Упорядочение дерева (в отличие от неупорядоченного дерева) дает нам огромное преимущество при поиске (O (log (N)) вместо O (N)).В неупорядоченной структуре необходимо тщательно искать какой-то конкретный элемент, поскольку он может находиться где угодно в структуре.В упорядоченной структуре он будет существовать только над ключами, значения которых меньше его, и под ключами, значения которых больше.Рассмотрим учебник.Вам было бы проще или труднее перейти на определенную страницу, если бы страницы были в случайном порядке?
Вопрос 4
Если наш ключ - строка, то нам нужнопосетите все символы строки, чтобы найти хэш-значение.Итак, для поиска элемента, не потребуется ли O (n) + O (1) времени?
Я задавал себе тот же вопрос раньше, и на самом деле это зависит от хеш-функции,Наихудшее время поиска «Амортизированная константа»:
O(H) + O(C)
O (H) - сложность хэш-функции в худшем случае.Интеллектуальная хеш-функция может просматривать только первые несколько десятков символов строки, либо последние несколько символов, либо некоторые в середине, либо что-то еще.Не обязательно, чтобы хеш-функция была безопасной, она должна быть детерминированной (то есть возвращать одинаковое значение для идентичных объектов).Независимо от того, насколько хороша ваша функция, в любом случае вы будете сталкиваться с коллизиями, поэтому, если вы можете отыграть огромную дополнительную работу для немного более коллизируемой функции, это часто стоит.
O (C) - сложность сравнения ключей в худшем случае.Неудачный поиск знает, что нет совпадений, потому что в его хэш-значении нет записи в таблице.Однако успешный поиск всегда должен сравнивать предоставленный ключ с ключами в таблице, в противном случае существует вероятность того, что ключ на самом деле не совпадение, а просто столкновение.В худшем случае, если для одного хэш-значения существует несколько коллизий, предоставленный ключ должен сравниваться со всеми сохраненными коллизионными ключами один за другим до тех пор, пока не будет найдено совпадение или все сравнения не пройдут.Вот почему, потому что амортизируется только постоянное время, а не постоянное время: по мере роста таблицы вероятность возникновения коллизий уменьшается, так что это происходит реже, а среднее время, необходимое для поиска некоторого набора элементов, всегда будет стремиться к постоянной.