Вы можете получить доступ к элементам только по их первичному ключу в хеш-таблице.
Это быстрее, чем с алгоритмом дерева (O(1) вместо log(n)), но вы не можете выбирать диапазоны ( все между x и y).
Древовидные алгоритмы поддерживают это в Log(n), тогда как хеш-индексы могут привести к полному сканированию таблицы O(n).
Также постоянные издержки хеш-индексов обычно больше (, что не является фактором в тета-нотации, но оно все еще существует ).
Кроме того, древовидные алгоритмы обычно проще поддерживать, расширять с помощью данных, масштабировать и т. Д.
Хеш-индексы работают с предопределенными размерами хэшей, так что в итоге вы получите несколько «корзин», в которых хранятся объекты. Эти объекты циклически повторяются, чтобы действительно найти нужный внутри этого раздела.
Так что, если у вас небольшие размеры, у вас много накладных расходов на маленькие элементы, большие размеры приводят к дальнейшему сканированию.
Сегодняшние алгоритмы хеш-таблиц обычно масштабируются, но масштабирование может быть неэффективным.
Есть действительно масштабируемые алгоритмы хеширования. Не спрашивайте меня, как это работает - для меня это тоже загадка. AFAIK они развились из масштабируемой репликации, где повторное хеширование не легко.
Это называется RUSH - R eplication U nder S calable H ashing, и эти алгоритмы так называемые алгоритмы RUSH.
Однако может быть момент, когда ваш индекс превышает допустимый размер по сравнению с вашими размерами хэша, и весь ваш индекс необходимо перестроить. Обычно это не проблема, но для баз данных «огромный-огромный-огромный» это может занять несколько дней.
Компромисс для древовидных алгоритмов невелик, и они подходят почти для каждого варианта использования и, таким образом, используются по умолчанию.
Однако, если у вас очень точный вариант использования и вы точно знаете, что и только то, что будет необходимо, вы можете воспользоваться индексами хеширования.