Разница между HashMap, LinkedHashMap и TreeMap

В чем разница между HashMap , LinkedHashMap и TreeMap в Java? Я не вижу разницы в выходе, поскольку все три имеют keySet и values . Что такое Hashtable ?

 Map m1 = new HashMap(); m1.put("map", "HashMap"); m1.put("schildt", "java2"); m1.put("mathew", "Hyden"); m1.put("schildt", "java2s"); print(m1.keySet()); print(m1.values()); SortedMap sm = new TreeMap(); sm.put("map", "TreeMap"); sm.put("schildt", "java2"); sm.put("mathew", "Hyden"); sm.put("schildt", "java2s"); print(sm.keySet()); print(sm.values()); LinkedHashMap lm = new LinkedHashMap(); lm.put("map", "LinkedHashMap"); lm.put("schildt", "java2"); lm.put("mathew", "Hyden"); lm.put("schildt", "java2s"); print(lm.keySet()); print(lm.values()); 

16 Solutions collect form web for “Разница между HashMap, LinkedHashMap и TreeMap”

Все три classа реализуют интерфейс Map и предлагают в основном те же функции. Самое важное отличие – порядок, в котором происходит итерация через записи:

  • HashMap дает никаких гарантий относительно порядка итераций. Он может (и будет) даже полностью меняться при добавлении новых элементов.
  • TreeMap будет выполнять итерацию в соответствии с «естественным порядком» ключей в соответствии с методом compareTo() (или с помощью поставляемого снаружи Comparator ). Кроме того, он реализует интерфейс SortedMap , который содержит методы, которые зависят от этого порядка сортировки.
  • LinkedHashMap будет выполнять итерацию в том порядке, в котором записи были помещены в карту

«Hashtable» – это общее имя для hash-карт. В контексте API Java Hashtable является устаревшим classом со времен Java 1.1 до того, как существовала структура коллекций. Его больше не следует использовать, поскольку его API загроможден устаревшими методами, которые дублируют функциональность, а его методы синхронизируются (что может снизить производительность и, как правило, бесполезно). Вместо Hashtable используйте ConcurrentHashMap .

Я предпочитаю визуальное представление:

 ╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗ ║ Property ║ HashMap ║ TreeMap ║ LinkedHashMap ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ Iteration ║ no guarantee order ║ sorted according ║ ║ ║ Order ║ will remain constant║ to the natural ║ insertion-order ║ ║ ║ over time ║ ordering ║ ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ Get/put ║ ║ ║ ║ ║ remove ║ O(1) ║ O(log(n)) ║ O(1) ║ ║ containsKey ║ ║ ║ ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ ║ ║ NavigableMap ║ ║ ║ Interfaces ║ Map ║ Map ║ Map ║ ║ ║ ║ SortedMap ║ ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ ║ ║ ║ ║ ║ Null ║ allowed ║ only values ║ allowed ║ ║ values/keys ║ ║ ║ ║ ╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣ ║ ║ Fail-fast behavior of an iterator cannot be guaranteed ║ ║ Fail-fast ║ impossible to make any hard guarantees in the presence of ║ ║ behavior ║ unsynchronized concurrent modification ║ ╠══════════════╬═════════════════════╦═══════════════════╦═════════════════════╣ ║ ║ ║ ║ ║ ║Implementation║ buckets ║ Red-Black Tree ║ double-linked ║ ║ ║ ║ ║ buckets ║ ╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣ ║ Is ║ ║ ║ synchronized ║ implementation is not synchronized ║ ╚══════════════╩═══════════════════════════════════════════════════════════════╝ 

Все три представляют собой сопоставление от уникальных ключей к значениям и, следовательно, реализуют интерфейс Map .

  1. HashMap – это карта, основанная на hashировании ключей. Он поддерживает операции O (1) get / put. Ключи должны иметь последовательные реализации hashCode() и equals() чтобы это работало.

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

  3. TreeMap – это отображение на основе дерева. Его операции put / get принимают время O (log n). Для этого требуется, чтобы элементы имели некоторый механизм сравнения, либо со сравнением, либо с компаратором. Порядок итераций определяется этим механизмом.

Посмотрите, где каждый class находится в иерархии classов на следующей диаграмме ( больше ). TreeMap реализует SortedMap и SortedMap а HashMap – нет.

HashTable устарел и должен использоваться соответствующий class ConcurrentHashMap . введите описание изображения здесь

Просто еще один вклад от моего собственного опыта работы с картами, когда я буду использовать каждый из них:

  • HashMap – наиболее полезно при поиске оптимальной (быстрой) реализации.
  • TreeMap (интерфейс SortedMap) – наиболее полезно, когда я заинтересован в том, чтобы сортировать или перебирать ключи в определенном порядке, который я определяю.
  • LinkedHashMap – объединяет преимущества гарантированного заказа от TreeMap без увеличения стоимости поддержки TreeMap. (Это почти так же быстро, как HashMap). В частности, LinkedHashMap также обеспечивает отличную отправную точку для создания объекта Cache, переопределяя метод removeEldestEntry() . Это позволяет создать объект Cache, который может истекать с использованием определенных критериев.

HashMap

  • Он имеет пары значений (ключи, значения)
  • НЕТ значений ключа дублирования
  • неупорядоченный несортированный
  • он допускает один нулевой ключ и более чем одно нулевое значение

Хеш-таблица

  • так же, как hash-карта
  • он не разрешает нулевые ключи и нулевые значения

LinkedHashMap

  • Это упорядоченная версия реализации карты
  • На основе связанных списков и хеширующих структур данных

TreeMap

  • Упорядоченная и сортированная версия
  • основанный на hash-структурах данных

Все три classа HashMap , TreeMap и LinkedHashMap реализуют интерфейс java.util.Map и представляют собой сопоставление от уникального ключа к значениям.

HashMap

  1. HashMap содержит значения, основанные на ключе.

  2. Он содержит только уникальные элементы.

  3. Он может иметь один нулевой ключ и несколько нулевых значений.

  4. Он не поддерживает порядок .

    public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

LinkedHashMap

  1. LinkedHashMap содержит значения, основанные на ключе.
  2. Он содержит только уникальные элементы.
  3. Он может иметь один нулевой ключ и несколько нулевых значений.
  4. Это то же самое, что и HashMap, поддерживает порядок вставки . // См. Замедление classа ниже.

    public class LinkedHashMap extends HashMap implements Map

TreeMap

  1. TreeMap содержит значения на основе ключа. Он реализует интерфейс NavigableMap и расширяет class AbstractMap.
  2. Он содержит только уникальные элементы.
  3. Он не может иметь нулевой ключ, но может иметь несколько нулевых значений.
  4. Это то же самое, что HashMap вместо этого поддерживает восходящий порядок (Сортируется с использованием естественного порядка его ключа.).

    public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, Serializable

Хеш-таблица

  1. Hashtable – это массив списка. Каждый список известен как ведро. Положение ведра идентифицируется вызовом метода hashcode (). Hashtable содержит значения, основанные на ключе.
  2. Он содержит только уникальные элементы.
  3. Возможно, у него нет нулевого ключа или значения.
  4. Он синхронизирован .
  5. Это унаследованный class.

    public class Hashtable extends Dictionary implements Map, Cloneable, Serializable

Ссылка: http://javarevisited.blogspot.in/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html

HashMap абсолютно не гарантирует порядок итерации. Он может (и будет) даже полностью меняться при добавлении новых элементов. TreeMap будет выполнять итерацию в соответствии с «естественным порядком» ключей в соответствии с методом compareTo () (или с помощью поставляемого снаружи компаратора). Кроме того, он реализует интерфейс SortedMap, который содержит методы, которые зависят от этого порядка сортировки. LinkedHashMap будет выполнять итерацию в том порядке, в котором записи были помещены в карту

Посмотрите, как меняется производительность. введите описание изображения здесь

Карта дерева, которая представляет собой реализацию Сортированной карты. Сложность операции put, get и containsKey – это O (log n) из-за естественного упорядочения

Позвольте мне сказать просто:

  • HashMap реализован как хеш-таблица, и нет никаких заказов на ключи или значения.
  • TreeMap реализуется на основе красно-черной древовидной структуры и упорядочивается ключом.
  • LinkedHashMap сохраняет порядок вставки
  • Hashtable синхронизируется, в отличие от HashMap. Он имеет накладные расходы для синхронизации. Именно поэтому HashMap следует использовать, если программа является streamобезопасной.

@Amit: SortedMap – это интерфейс, тогда как TreeMap – это class, который реализует интерфейс SortedMap . Это означает, что если следует протокол, который SortedMap просит своих исполнителей сделать. Дерево, если оно не реализовано как дерево поиска, не может дать вам упорядоченные данные, потому что дерево может быть любым деревом. Поэтому, чтобы заставить TreeMap работать как Sorted order, он реализует SortedMap (например, Binary Search Tree – BST, сбалансированный BST, такой как AVL и дерево RB, даже Tree Tree Tree), в основном используется для итеративных поисков упорядоченным способом).

 public class TreeMap extends AbstractMap implements SortedMap, Cloneable, Serializable 

В NUT-SHELL HashMap : дает данные в O (1), без упорядочения

TreeMap : дает данные в O (log N), база 2. с упорядоченными ключами

LinkedHashMap : есть таблица Hash со связанным списком (подумайте об индексированном-SkipList), чтобы хранить данные так, как они вставлены в дерево. Лучше всего подходит для реализации LRU (в последнее время используется).

Ниже приведены основные различия между HashMap и TreeMap

  1. HashMap не поддерживает какой-либо заказ. Другими словами, HashMap не дает никакой гарантии, что сначала будет напечатан элемент, вставленный первым, где так же, как TreeSet, элементы TreeMap также сортируются в соответствии с естественным упорядочением его элементов

  2. Внутренняя реализация HashMap использует Hashing и TreeMap внутренне использует реализацию Red-Black tree.

  3. HashMap может хранить один нулевой ключ и множество нулевых значений. TreeMap не может содержать нулевые ключи, но может содержать много нулевых значений.

  4. HashMap обеспечивает постоянную производительность по времени для основных операций, таких как get и put, т.е. O (1). Согласно документам Oracle, TreeMap обеспечивает гарантированную log (n) временную стоимость метода get и put.

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

  6. HashMap использует метод equals () в сравнении, в то время как TreeMap использует метод compareTo () для поддержания порядка.

  7. HashMap реализует интерфейс карты, а TreeMap реализует интерфейс NavigableMap.

Это разные реализации одного и того же интерфейса. Каждая реализация имеет некоторые преимущества и некоторые недостатки (быстрая вставка, медленный поиск) или наоборот.

Подробнее см. Javadoc TreeMap , HashMap , LinkedHashMap .

Карта hashа не сохраняет порядок вставки.
Пример. Hashmap Если вы вставляете ключи как

 1 3 5 9 4 6 7 15 3 10 

Он может хранить его как

 4 6 5 9 3 10 1 3 7 15 

Связанный Hashmap сохраняет порядок вставки.

Пример.
Если вы вставляете ключи

 1 3 5 9 4 6 7 15 3 10 

Он сохранит его как

 1 3 5 9 4 6 7 15 3 10 

такой же, как мы вставляем.

Карта деревьев хранит значения в увеличении порядка ключей. Пример.
Если вы вставляете ключи

 1 3 5 9 4 6 7 15 3 10 

Он сохранит его как

 1 3 3 10 4 6 5 9 7 15 

Все предлагают карту ключа -> значение и способ итерации через клавиши. Наиболее важным различием между этими classами являются гарантии времени и порядок ключей.

  1. HashMap предлагает 0 (1) поиск и вставку. Однако, если вы перебираете ключи, упорядочение ключей по существу произвольно. Он реализуется массивом связанных списков.
  2. TreeMap предлагает O (log N) поиск и вставку. Ключи упорядочены, поэтому, если вам нужно перебирать ключи в отсортированном порядке, вы можете. Это означает, что ключи должны реализовывать интерфейс Comparable. TreeMap реализуется красно-черным деревом.
  3. LinkedHashMap предлагает 0 (1) поиск и вставку. Ключи упорядочиваются по порядку вставки. Он реализуется двусвязными ведрами.

Представьте, что вы передали пустой TreeMap, HashMap и LinkedHashMap в следующую функцию:

 void insertAndPrint(AbstractMap map) { int[] array= {1, -1, 0}; for (int x : array) { map.put(x, Integer.toString(x)); } for (int k: map.keySet()) { System.out.print(k + ", "); } } 

Результат для каждого будет выглядеть следующим образом.

Для HashMap вывод был в моих собственных тестах {0, 1, -1}, но это может быть любой порядок. При заказе нет гарантии.
Treemap, выход был, {-1, 0, 1}
LinkedList, результат был, {1, -1, 0}

  • HashMap:

    • Заказ не поддерживается
    • Быстрее, чем HashMap и LinkedHashMap
    • Используется для хранения кучи объектов
  • LinkedHashMap:

    • Порядок добавления ссылок LinkedHashMap будет сохранен
    • Медленнее, чем HashMap и быстрее, чем TreeMap
    • Если вы хотите сохранить порядок вставки, используйте это.
  • TreeMap:

    • TreeMap – это отображение на основе дерева
    • TreeMap будет следовать естественному порядку ключа
    • Медленнее, чем HashMap и LinkedHashMap
    • Используйте TreeMap, когда вам нужно поддерживать естественный (по умолчанию) порядок

HashMap
может содержать один нулевой ключ.

HashMap не поддерживает порядок.

TreeMap

TreeMap не может содержать нулевой ключ.

TreeMap поддерживает восходящий порядок.

LinkedHashMap

LinkedHashMap может использоваться для поддержания порядка вставки, по которому ключи вставляются в Карту, или также может использоваться для поддержания порядка доступа, по которым осуществляется доступ к ключам.

Примеры ::

1) HashMap map = new HashMap ();

  map.put(null, "Kamran"); map.put(2, "Ali"); map.put(5, "From"); map.put(4, "Dir");`enter code here` map.put(3, "Lower"); for (Map.Entry m : map.entrySet()) { System.out.println(m.getKey() + " " + m.getValue()); } 

2) TreeMap map = new TreeMap ();

  map.put(1, "Kamran"); map.put(2, "Ali"); map.put(5, "From"); map.put(4, "Dir"); map.put(3, "Lower"); for (Map.Entry m : map.entrySet()) { System.out.println(m.getKey() + " " + m.getValue()); } 

3) LinkedHashMap map = new LinkedHashMap ();

  map.put(1, "Kamran"); map.put(2, "Ali"); map.put(5, "From"); map.put(4, "Dir"); map.put(3, "Lower"); for (Map.Entry m : map.entrySet()) { System.out.println(m.getKey() + " " + m.getValue()); } 
Давайте будем гением компьютера.