Разница между HashMap, LinkedHashMap и TreeMap
Проблема с различиями между HashMap, LinkedHashMap и TreeMap в Java
Я изучаю коллекции в Java и у меня возник вопрос о различиях между HashMap, LinkedHashMap и TreeMap. В коде ниже я не вижу никакой разницы в выводе, так как все три класса имеют методы keySet() и values(), которые возвращают ключи и значения соответственно.
Вот пример кода:
Map<String, String> 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<String, String> 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<String, String> 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());
Также, хотел бы узнать, что такое Hashtable и чем он отличается от вышеперечисленных классов.
Буду признателен за разъяснения!
5 ответ(ов)
Вот сводная таблица, которая демонстрирует ключевые различия между HashMap, TreeMap и LinkedHashMap в Java:
| Свойство | HashMap | TreeMap | LinkedHashMap |
|---|---|---|---|
| Порядок итерации | Нет гарантированного порядка; может изменяться со временем | Отсортирован по естественному порядку | Порядок вставки |
| Временная сложность операций (get/put/remove/containsKey) | O(1) | O(log(n)) | O(1) |
| Интерфейсы | Map | NavigableMap, Map, SortedMap | Map |
| Null-значения/ключи | Позволены | Только значения | Позволены |
| Поведение при сбое (fail-fast) | Поведение итератора не гарантировано, невозможно предоставить жесткие гарантии при несинхронизированном одновременном изменении | Поведение итератора не гарантировано, невозможно предоставить жесткие гарантии при несинхронизированном одновременном изменении | Поведение итератора не гарантировано, невозможно предоставить жесткие гарантии при несинхронизированном одновременном изменении |
| Реализация | Корзины (buckets) | Красно-черное дерево | Двусвязные корзины |
| Синхронизирован ли? | Реализация не синхронизирована | Реализация не синхронизирована | Реализация не синхронизирована |
Исходя из этой таблицы, вы можете выбрать между этими структурами данных в зависимости от ваших потребностей в хранении и сортировке данных.
HashMap
- Содержит пары значений (ключи, значения).
- Не допускает дублирования ключей.
- Неупорядочен и неотсортирован.
- Позволяет использовать один null в качестве ключа и множество null в качестве значений.
HashTable
- В целом аналогичен HashMap.
- Не допускает использования null в качестве ключей и значений.
LinkedHashMap
- Это упорядоченная версия реализации карты.
- Основан на связном списке и хэшировании как структурах данных.
TreeMap
- Упорядоченная и отсортированная версия.
- Основан на структурировании данных с использованием дерева.
@Amit: SortedMap — это интерфейс, в то время как TreeMap — это класс, который реализует интерфейс SortedMap. Это означает, что TreeMap следует протоколу, который SortedMap ожидает от своих реализаций. Дерево, если не реализовано как дерево поиска, не может гарантировать упорядоченные данные, так как дерево может быть любым типом дерева. Поэтому для того, чтобы TreeMap работал с отсортированными данными, он реализует SortedMap (например, бинарное дерево поиска - BST, сбалансированные BST, такие как AVL и R-B дерево, даже тернарное дерево поиска - обычно используемое для итеративных поисков в упорядоченном виде).
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable
В КРАТЦЕ:
HashMap: обеспечивает доступ к данным за O(1), без упорядочивания.TreeMap: обеспечивает доступ к данным за O(log N) (по основанию 2) с упорядоченными ключами.LinkedHashMap: это хеш-таблица с возможностями связного списка (представьте себе индексированный SkipList), которая позволяет хранить данные в порядке их вставки в структуру. Лучше всего подходит для реализации алгоритма LRU (наименее недавно использованный).
В HashMap порядок вставки не сохраняется.
Пример. Если вы вставляете ключи в следующем порядке:
1 3
5 9
4 6
7 15
3 10
HashMap может сохранить их в другом порядке, например:
4 6
5 9
3 10
1 3
7 15
В отличие от этого, LinkedHashMap сохраняет порядок вставки.
Пример. Если вы вставляете ключи:
1 3
5 9
4 6
7 15
3 10
LinkedHashMap сохранит их так же, как вы их вставили:
1 3
5 9
4 6
7 15
3 10
Что касается TreeMap, он хранит значения в порядке возрастания ключей.
Пример. Если вы вставляете ключи:
1 3
5 9
4 6
7 15
3 10
TreeMap сохранит их в следующем порядке:
1 3
3 10
4 6
5 9
7 15
Таким образом, выбор между этими структурами данных зависит от ваших требований к порядку хранения элементов.
Хэш-таблица (HashMap):
- Не сохраняет порядок элементов.
- Быстрее, чем LinkedHashMap.
- Используется для хранения большего количества объектов.
Связная хэш-таблица (LinkedHashMap):
- Поддерживает порядок вставки.
- Медленнее, чем HashMap, но быстрее, чем TreeMap.
- Используйте, если нужно сохранить порядок вставки элементов.
Древовидная карта (TreeMap):
- Основана на структуре дерева.
- Поддерживает естественный порядок ключей.
- Медленнее, чем HashMap и LinkedHashMap.
- Используйте TreeMap, когда нужно сохранить естественный (по умолчанию) порядок.
Эффективный способ итерации по каждой записи в Java Map?
Как инициализировать статическую Map?
Сортировка Map<Key, Value> по значениям
Как напрямую инициализировать HashMap (в литеральном виде)?
Что значит "Не удалось найти или загрузить основной класс"?