Хэш-таблица против хэш-списка против хэш-дерева?
Какое свойство отличает хеш-таблицу, хеш-список и хеш-дерево друг от друга? Какой используется когда? Когда таблица выше, чем дерево.
1 ответ
Решение
- Хеш-таблица: это структура данных, в которую можно вставить пары (ключ, значение), в которых ключ используется для вычисления хэш-кода, необходимого для определения места хранения значения, связанного с его ключом. Такая структура полезна, поскольку для вычисления хеш-кода используется O(1), поэтому вы можете найти или поместить элемент в постоянное время. (Имейте в виду, что есть предостережения и различные реализации, которые слегка изменяют эту производительность)
- Hashlist: это просто список хеш-кодов, рассчитанный на различные фрагменты данных. Например: вы разбиваете файл на несколько частей и вычисляете хеш-код для каждой части, а затем сохраняете все из них в списке. Затем вы можете использовать этот список для проверки целостности данных.
- Hashtree: он похож на хеш-лист, но вместо того, чтобы иметь список хэшей, у вас есть дерево, поэтому каждый узел в дереве - это хеш-код, который рассчитывается на его дочерние элементы. Конечно, листья будут данными, из которых вы начнете вычислять хеш-коды.
Hashtable часто полезен (их также называют hashmaps), в то время как hashlists и hashtrees несколько более конкретны и полезны для точных целей.