Почему TreeMap Java не позволяет получить начальный размер?

Question

Загрузка 1 000 000 номеров занимает 2 секунды для загрузки в treemap (двоичное дерево поиска), но для загрузки в хэш-карту (в java) требуется миллисекунды.
Единственное различие между ними заключается в том, что я могу установить начальный размер hashmap, поэтому он не нуждается в повторном размере.

Неправильно ли предположить, что начальный размер массива TreeMap должен быть установлен? Есть ли другая причина, почему это так медленно?
Есть ли логическая причина того, почему нельзя установить TreeMap или любое дерево двоичного дерева поиска, размер или это неправильно?

Answer 1

В отличие от HashMap, который переназначает его внутренности, поскольку новые вставлены, TreeMap обычно не перераспределяет свои узлы при добавлении новых. Разницу можно легко проиллюстрировать так же, как между ArrayList и LinkedList: первый перераспределяет для изменения размера, а второй - нет. Поэтому установка начального размера TreeMap примерно такая же бессмысленная, как попытка установить начальный размер LinkedList.

разница в скорости происходит из-за различную временную сложность два контейнеров: вставки N узлов в HashMap является O(n), в то время как для TreeMap это O(N*LogN), который для узлов 1000000 примерно в 20 раз асимптотической разница. Хотя разница в асимптотической сложности не переводится непосредственно в разницу во времени из-за разных констант, продиктованных отдельными алгоритмами, она служит хорошим способом решить, какой алгоритм будет быстрее на очень больших входах.

Answer 2

Карта всегда сбалансирована. Каждый раз, когда вы добавляете узел в дерево, он должен убедиться, что все узлы находятся в порядке предоставленным компаратором. У вас нет определенного размера, потому что treemap предназначен для гладкой сортированной группы узлов и легко проходит через узлы.

Hashmap должен иметь размер свободного места для вещей, которые вы храните в нем. Мой профессор всегда говорил мне, что ему нужно в 5 раз больше пространства, чем объекты или все, что вы храните в этой хэш-карте. Таким образом, указание размера от первоначального создания Hashmap улучшает скорость вашего хэшмапа. В противном случае, если у вас больше объектов, попадающих в хэш-карту, чем вы планировали, хэш-карта должна «масштабироваться».

(отредактированный орфографии)

Answer 3

ли я неправильно считать начальный размер массива это TreeMap должен быть в состоянии установить?

Да. A TreeMap не имеет массива. A TreeMap использует двоичные узлы с 2 детьми.

Если вы указываете, что количество детей в узле дерева должно быть параметром, вам необходимо выяснить, как это влияет на время поиска. И я думаю, что это время поиска от O(log2N) до O(log2M * log2(N/M)), где N - числовые элементы, а M - среднее число дочерних узлов. (И я делаю некоторые оптимистические предположения ...) Это не «победа».

Есть ли другая причина, что это так медленно?

Да. Причина, по которой a (большой) TreeMap является медленной относительно (большой) HashMap при оптимальных обстоятельствах, заключается в том, что поиск с использованием сбалансированного двоичного дерева требует поиска узлов дерева log2N. По контрасту, в оптимальном HashMap (хороший коэффициент загрузки и отсутствие горячих точек коллизии) поиск включает в себя 1 расчет хэш-кода и просмотр O(1) узлов хеш-цепей.

Примечание:

1. TreeMap использует двоичную организацию дерева, что дает сбалансированные дерева, так O(log2N) наихудшее время поиску.
2. HashMap Производительность зависит от скорости столкновения хеш-функции и пространства ключа. В худшем случае, когда все ключи попадают в одну и ту же цепочку хэширования, HashMap имеет O(N).

Answer 4

Неправильно ли предположить, что начальный размер массива TreeMap должен быть установлен?

Да. Он не имеет массив. У него есть дерево.