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

В чем разница между HashMap, LinkedHashMap а также TreeMap на яве? Я не вижу никакой разницы в выходе, так как все три имеют keySet а также values, Что Hashtables?

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());
Источник

15 ответов

Решение

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

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

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

Источник

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

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   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 - это карта, основанная на хешировании ключей. Он поддерживает O(1) операции get/put. Ключи должны иметь последовательную реализацию hashCode() а также equals() чтобы это работало.

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

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

Источник

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

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

Источник

HashMap

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

Хеш-таблица

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

LinkedHashMap

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

TreeMap

  • Заказанная и отсортированная версия
  • основанный на хешировании структур данных
Источник

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

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

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

HashMap

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

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

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

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

    public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

LinkedHashMap

  1. LinkedHashMap содержит значения на основе ключа.
  2. Он содержит только уникальные элементы.
  3. Может иметь один нулевой ключ и несколько нулевых значений.

  4. Это то же самое, что HashMap, вместо этого поддерживает порядок вставки. // См. Замедление класса ниже

    public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

TreeMap

  1. TreeMap содержит значения на основе ключа. Он реализует интерфейс NavigableMap и расширяет класс AbstractMap.
  2. Он содержит только уникальные элементы.
  3. Он не может иметь нулевой ключ, но может иметь несколько нулевых значений.

  4. Это так же, как HashMap вместо этого поддерживает восходящий порядок(сортируется с использованием естественного порядка его ключа.).

    public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable

Хеш-таблица

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

  5. Это унаследованный класс.

    public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, 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, если программа является поточно-ориентированной.
Источник

@Amit: SortedMap это интерфейс, тогда как TreeMap это класс, который реализует SortedMap интерфейс. Это означает, что если следует протокол, который SortedMap просит его исполнителей сделать. Дерево, если оно не реализовано как дерево поиска, не может дать вам упорядоченные данные, потому что дерево может быть любым видом дерева. Таким образом, чтобы заставить TreeMap работать как порядок сортировки, он реализует SortedMap (например, дерево двоичного поиска - BST, сбалансированное BST, такое как AVL и дерево RB, даже дерево троичного поиска - в основном используется для итеративного поиска в упорядоченном виде).

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable

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

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

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

Источник

Хэш-карта не сохраняет порядок вставки.
Пример. Hash map Если вы вставляете ключи как

1  3
5  9
4   6
7   15
3   10

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

4  6
5  9
3  10
1  3
7  15

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

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

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
Источник

  • HashMap:

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

  • LinkedHashMap:

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

  • TreeMap:

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

Ниже приведены основные различия между 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 реализует интерфейс Map, а TreeMap реализует интерфейс NavigableMap.

Источник

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

Для получения дополнительной информации посмотрите на Javadoc TreeMap, HashMap, LinkedHashMap.

Источник

Хотя здесь есть множество отличных ответов, я хотел бы представить свою собственную таблицу с описанием различных Map реализации в комплекте с Java 11.

Мы можем видеть эти различия, перечисленные на графике таблицы:

  • HashMap является универсальным Map обычно используется, когда у вас нет особых потребностей.
  • LinkedHashMap расширяет HashMap, добавляя следующее поведение: Поддерживает порядок, в котором записи были изначально добавлены. Изменение значения записи "ключ-значение" не меняет ее места в порядке.
  • TreeMap тоже поддерживает порядок, но использует либо (а) "естественный" порядок, то есть значение compareTo метод для ключевых объектов, определенных в Comparable интерфейс, или (б) вызывает Comparator реализация, которую вы предоставляете.
    • TreeMap реализует как SortedMap интерфейс, и его преемник, NavigableMap интерфейс.
  • NULLs:TreeMapэто не позволяют NULL в качестве ключа, в то время какHashMap & LinkedHashMap делать.
    • Все три допускают NULL в качестве значения.
  • HashTable это наследие, от Java 1. На смену ConcurrentHashMap учебный класс. Цитата из Javadoc:ConcurrentHashMap подчиняется той же функциональной спецификации, что и Hashtable, и включает версии методов, соответствующие каждому методу Hashtable.

Источник

Самым важным из всех трех является то, как они сохраняют порядок записей.

HashMap- Не сохраняет порядок записей. например.

public static void main(String[] args){
        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("First",1);// First ---> 1 is put first in the map
        hashMap.put("Second",2);//Second ---> 2 is put second in the map
        hashMap.put("Third",3); // Third--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : hashMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

LinkedHashMap: Сохраняет порядок, в котором были сделаны записи. например:

public static void main(String[] args){
        LinkedHashMap<String,Integer> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("First",1);// First ---> 1 is put first in the map
        linkedHashMap.put("Second",2);//Second ---> 2 is put second in the map
        linkedHashMap.put("Third",3); // Third--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : linkedHashMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

TreeMap: Сохраняет записи в порядке возрастания ключей. например:

public static void main(String[] args) throws IOException {
        TreeMap<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("A",1);// A---> 1 is put first in the map
        treeMap.put("C",2);//C---> 2 is put second in the map
        treeMap.put("B",3); //B--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : treeMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

Источник

Все предлагают карту key->value и способ перебирать ключи. Самое важное различие между этими классами - это временные гарантии и порядок ключей.

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

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

void insertAndPrint(AbstractMap<Integer, String> 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}, но это мог быть любой порядок. Там нет никакой гарантии на заказ.
Древовидная карта, результат был, {-1, 0, 1}
LinkedList, результат был,{ 1, -1, 0}

Источник

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

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

TreeMap

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

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

LinkedHashMap

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

Примеры::

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 = новая 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());
    }
Источник
Другие вопросы по тегам