Ответ 1
Вы можете обращаться к элементам только по их первичному ключу в хеш-таблице.
Это быстрее, чем с помощью алгоритма дерева (O(1) вместо log(n)), но вы не можете выбирать диапазоны (все между x и y).
Алгоритмы дерева поддерживают это в log(n), где в качестве хеш-индекса может быть выполнено полное сканирование таблицы O(n).
Также постоянные накладные расходы хэш-индексов обычно больше (что не является фактором в обозначениях тета, но оно все еще существует).
Кроме того, алгоритмы дерева обычно легче поддерживать, расти с данными, масштабами и т.д.
Индексы хэша работают с заранее определенными размерами хэша, поэтому вы получаете некоторые "ведра", в которых хранятся объекты. Эти объекты снова зацикливаются, чтобы действительно найти правильный внутри этого раздела.
Итак, если у вас небольшие размеры, у вас много накладных расходов для небольших элементов, большие размеры приводят к дальнейшему сканированию.
Современные алгоритмы хеш-таблиц обычно масштабируются, но масштабирование может быть неэффективным.
Существуют действительно масштабируемые алгоритмы хеширования. Не спрашивайте меня, как это работает - это тоже для меня. AFAIK они эволюционировали от масштабируемой репликации, где повторное хеширование непросто.
Его называют RUSH - R. <, и эти алгоритмы называются алгоритмами RUSH.
Однако может быть точка, в которой ваш индекс превышает допустимый размер по сравнению с вашими размерами хэша, и весь ваш индекс необходимо перестроить. Обычно это не проблема, но для огромных огромных баз данных это может занять несколько дней.
Компиляция для алгоритмов дерева небольшая, и они подходят практически для каждого варианта использования и, следовательно, по умолчанию.
Однако, если у вас очень точный вариант использования, и вы точно знаете, что и только что понадобится, вы можете воспользоваться индексами хеширования.