Когда использовать hashmaps или treemaps?
Я знаю, что я могу использовать TreeMap для перебора элементов, когда мне нужно их сортировать. Но так ли это? Нет оптимизации, когда я просто хочу проконсультироваться с картами или использовать некоторые оптимальные конкретные приложения?
Hashtables (обычно) выполняют поисковые операции (поиск), ограниченные в сложности O(n)<=T(n)<=O(1), со средней сложностью случая O(1 + n/k); однако бинарные деревья поиска (BST) выполняют операции поиска (поиска), ограниченные в сложности O(n)<=T(n)<=O(log_2(n)), со средней сложностью случая O(log_2(n)). Реализация для каждой (и каждой) структуры данных должна быть известна (вами), чтобы понять преимущества, недостатки, сложность времени операций и сложность кода.
Например, количество записей в хэш-таблице часто имеет некоторое фиксированное количество записей (некоторые из которых могут вообще не заполняться) списками коллизий. С другой стороны, деревья, как правило, имеют два указателя (ссылки) на node, но это может быть больше, если реализация допускает более двух дочерних узлов на node, и это позволяет дереву расти по мере добавления узлов, но может не допускать дубликатов. (По умолчанию реализация Java TreeMap не допускает дубликатов)
Есть также особые случаи, например, что, если количество элементов в конкретной структуре данных неограниченно возрастает или приближается к пределу базовой части структуры данных? Как насчет амортизированных операций, которые выполняют некоторую операцию перебалансировки или очистки?
Например, в хэш-таблице, когда количество элементов в таблице становится достаточно большим и может происходить произвольное число столкновений. С другой стороны, деревья обычно требуют процедуры повторной балансировки после вставки (или удаления).
Итак, если у вас есть что-то вроде кеша (например, количество ограниченных элементов или размер известен), то хэш-таблица, вероятно, лучше всего; однако, если у вас есть что-то более похожее на словарь (например, один раз и много раз искал много раз), я бы использовал дерево.
Это только в общем случае, однако (информация не была дана). Вы должны понимать процесс, который случается так, как они делают правильный выбор при выборе структуры данных.
Когда мне нужна мульти-карта (поиск по диапазону) или отсортированное сглаживание коллекции, то она не может быть хэш-таблицей.
TreeMap обеспечивает гарантированное время поиска O (log n) (и вставка и т.д.), тогда как HashMap обеспечивает O (1) время поиска, если хеш-код соответствующим образом распределяет ключи.
Если вам не нужны записи для сортировки, я придерживаюсь HashMap. Или там ConcurrentHashMap, конечно. Я не помню подробностей различий между ними, но HashMap - вполне разумная опция по умолчанию:)
Для полноты я должен отметить, что около месяца назад было обсуждено "Переполнение стека" о внутренних картах различных карт. См. комментарии в этом вопросе, которые я буду копировать в этот ответ, если bestsss будет рад за меня сделать это.
Самое большое различие между ними - это базовая структура, используемая в реализации.
HashMaps использует массив и функцию хеширования для хранения элементов. Когда вы пытаетесь вставить или удалить элемент в массиве, хеширующая функция преобразует ключ в индекс в массиве, где объект должен/должен храниться (игнорируя конфликты). Хотя hashmaps, как правило, очень быстрые, потому что им не нужно перебирать большие объемы данных, они замедляются, когда они заполняются, потому что им нужно скопировать все ключи/значения в новый массив.
TreeMaps хранит данные в сортированной древовидной структуре. Хотя это означает, что им никогда не придется выделять больше места и копировать на него, операции требуют, чтобы часть уже сохраненных данных была переименована. Иногда меняется большое количество структуры.
Из двух Hashmaps обычно будет лучше работать, когда вам не нужна сортировка.
Не забывайте, что есть также LinkedHashMap, который почти так же быстро, как HashMap для добавления/содержит/удаления операций, но также поддерживает порядок вставки.
Вставка новых элементов в HashMap будет, в среднем, намного быстрее, чем вставка элементов в TreeMap. Если вам не нужны ваши элементы отсортированы, я бы пошел с HashMap.