Nano Hash - криптовалюты, майнинг, программирование

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

Это спорная строка из Cracking the Coding Interview о хеш-таблицах.

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

Я знаю, что этот вопрос задавали раньше ... это так сбивает с толку, потому что все дают два разных ответа. Например

Зачем реализовывать хеш-таблицу с двоичным деревом поиска?

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

С другой стороны, другие говорят

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

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

Таким образом, каждый слот в массиве будет указателем на BST, который содержит элементы с одинаковым значением хеш-функции.

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

Но для второго поста, если у нас есть несколько элементов, которые получают одно и то же хеш-значение и помещаются в BST, я не уверен, как эти элементы упорядочены (как их можно сравнивать друг с другом?)

Пожалуйста, помогите мне раз и навсегда положить конец этому вопросу!

hash hashtable binary-search-tree
20.06.2017

Ответы:


1

первый пост на самом деле не объясняет, как такая реализация хеш-таблицы может справляться с коллизиями

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

если у нас есть несколько элементов, которые получают одно и то же хеш-значение и помещаются в BST, я не уверен, как эти элементы упорядочены (как их можно сравнивать друг с другом?)

Перепиши с другой функцией.

В конце концов, все зависит от того, для чего используется ваша структура данных (важнее ли память или скорость? Важнее ли амортизированная производительность или производительность в худшем случае? И т. Д.)

20.06.2017
  • О ваших комментариях к первой цитате ... хеш-функция, которая не производит повторяющихся значений, - это идеальная хеш-функция, верно? Если мы используем для этой реализации PHF и BST, каковы некоторые недостатки? в этом должен быть какой-то недостаток 21.06.2017
  • Можете ли вы также объяснить, почему реализация BST + PHF вызвала бы время изменения размера O (n)? 21.06.2017
  • PHF + BST имеет недостаток в том, что он медленнее, поскольку вставка и поиск будут O (log n) по сравнению с хеш-таблицей на основе массива, которая имеет O (1). В C ++ std :: map использует BST с реализацией PHF, тогда как std :: unordered_map использует массив, а std :: map почти всегда медленнее, чем std :: unordered_map (за исключением случая, когда std :: map пусто). BST + PHF не имеет изменения размера O (n), это массив + BST в каждом сегменте для обработки коллизий, размер которых должен изменяться за O (n), обычно, когда количество сегментов в массиве достигает 50%. 21.06.2017
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..