В чем разница между HashMap и TreeMap?

Я начал изучать Java. Когда я буду использовать HashMap над TreeMap?

+121
источник поделиться
8 ответов

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

HashMap, с другой стороны, не дает такой гарантии. Поэтому при повторении по клавишам HashMap вы не можете быть уверены, в каком порядке они будут.

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

+193
источник

HashMap реализуется таблицей Hash, а TreeMap реализуется Red-Black tree. Основное различие между HashMap и TreeMap фактически отражает основное различие между a Hash и a Binary Tree, то есть при итерации гарантией TreeMap может быть порядок клавиш, который определяется методом elementElementTo() или компаратор установлен в конструкторе TreeMap.

Посмотрите следующую диаграмму.

enter image description here

+50
источник

Подводя итог:

  • HashMap: структура массива Lookup-массива, основанная на hashCode(), реализациях equals(), O (1) сложность выполнения для вставки и поиска, unsorted
  • TreeMap: структура дерева, основанная на реализации compareTo(), O (log (N)) сложность выполнения для вставки и поиска, отсортированная

Взято из: HashMap против TreeMap

+26
источник

Используйте HashMap большую часть времени, но используйте TreeMap, когда вам нужен ключ для сортировки (когда вам нужно итерировать ключи).

+20
источник

Я расскажу о реализации HashMap и TreeMap в Java:

  • HashMap - реализует базовый интерфейс карты

    • реализованный массивом ведер, каждый ведро представляет собой LinkedList записей
    • время выполнения основных операций: put(), среднее значение O (1), наихудший случай O (n), происходит при изменении размера таблицы; get(), remove(), средний O (1)
    • не синхронизирован, чтобы синхронизировать его: Map m = Collections.synchronizedMap(new HashMap(...));
    • Порядок итераций карты непредсказуем.
  • TreeMap - реализовать навигационный интерфейс карты

    • реализовано красно-черным деревом
    • время работы основных операций: put(), get(), remove(), наихудший случай O (lgn)
    • не синхронизирован, чтобы синхронизировать его: SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
    • предоставить упорядоченную итерацию. upperKey(), lowerKey() может использоваться для получения преемника и предшественника данного ключа.

Суммируя, наибольшая разница между HashMap и TreeMap заключается в том, что TreeMap реализует NavigableMap<K,V>, которые обеспечивают функцию упорядоченной итерации. Кроме того, HashMap и TreeMap являются членами среды Java Collection. Вы можете исследовать исходный код Java, чтобы узнать больше об их реализации.

+14
источник

Вы почти всегда используете HashMap, вы должны использовать только TreeMap, если вам нужны ваши ключи в определенном порядке.

+7
источник

HashMap используется для быстрого поиска, тогда как TreeMap используется для сортировки итераций по карте.

+7
источник

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

+5
источник

Посмотрите другие вопросы по метке или Задайте вопрос