TreeMap или HashMap? [дубликат]

этот вопрос уже есть ответ здесь:

когда использовать hashmaps или treemaps?

Я знаю, что могу использовать TreeMap для итерации по элементам, когда мне нужно их отсортировать. Но так ли это? Там нет оптимизации, когда я просто хочу проконсультироваться с картами, или некоторые оптимальные конкретные виды использования?

5 72
javascript data-structures

5 ответов:

Hashtables (обычно) выполняют операции поиска (look up), ограниченные сложностью O(n)<=T(n)<=O(1), со средней сложностью случая O(1 + n/k); однако бинарные деревья поиска (BST) выполняют операции поиска (lookup), ограниченные сложностью O(n)<=T(n)<=O(log_2(n)), со средней сложностью случая O(log_2(n)). Реализация для каждой (и каждой) структуры данных должна быть известна (вами), чтобы понять преимущества, недостатки, временную сложность операций и сложность кода.

например, число записей в хэш-таблице часто имеет некоторое фиксированное число записей (некоторая часть которых может вообще не заполняться) со списками коллизий. Деревья, с другой стороны, обычно имеют два указателя (ссылки) на узел, но это может быть больше, если реализация позволяет более двух дочерних узлов на узел, и это позволяет дереву расти по мере добавления узлов, но может не допускать дубликатов. (Реализация Java TreeMap по умолчанию не позволяет дубликаты)

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

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

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

это только в общем случае, однако, (нет информации). Вы должны понимать процесс это происходит так, как они делают правильный выбор при принятии решения о том, какую структуру данных использовать.

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

49

TreeMap обеспечивает гарантированное время поиска O(log n) (и вставки и т. д.), Тогда как HashMap обеспечивает O (1) время поиска, если хэш-код рассеивает ключи соответствующим образом.

Если вам не нужно сортировать записи, я бы придерживался HashMap. Или есть ConcurrentHashMap конечно. Я не могу вспомнить детали различий между ними всеми, но HashMap является вполне разумным вариантом "по умолчанию":)

для полноты картины, я должен отметить, что была дискуссия о переполнении стека месяц или около того назад о внутренностях различных карт. Смотрите комментарии в этом вопросе, который я скопирую в этот ответ, если bestsss будет счастлив для меня сделать это.

53

наибольшая разница между ними заключается в базовой структуре, используемой в реализации.

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

TreeMaps хранить данные в отсортированной древовидной структуре. Хотя это означает, что им никогда не придется выделять больше места и копировать его, операции требуют, чтобы часть уже сохраненных данных была повторена. Иногда меняется большое количество структуры.

из двух хэш-карт, как правило, имеют лучшую производительность, когда вам не нужна сортировка.

11

Не забывайте, что есть также LinkedHashMap почти так же быстро, как HashMap для операций добавить / содержит / удалить, но также поддерживает порядок вставки.

4

вставка новых элементов в хэш-карту будет, в среднем, намного быстрее, чем вставка элементов в карту дерева. Если вам не нужны ваши элементы отсортированы, я бы пошел с HashMap.

3