HashMap и TreeMap в Java
HashMap и TreeMap являются частью структуры коллекции.
Класс java.util.HashMap - это реализация на основе хеширования. В HashMap у нас есть пара ключей и значений <Key, Value>.
HashMap <K, V> hmap = new HashMap <K, V> ();
Let us consider below example where we have to count occurrences of each integer in given array of integers.
Input: arr[] = {10, 3, 5, 10, 3, 5, 10};
Output: Frequency of 10 is 3
Frequency of 3 is 2
Frequency of 5 is 2
/* Java program to print frequencies of all elements using HashMap */import java.util.*; class Main{ // This function prints frequencies of all elements static void printFreq(int arr[]) { // Creates an empty HashMap HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>(); // Traverse through the given array for (int i = 0; i < arr.length; i++) { Integer c = hmap.get(arr[i]); // If this is first occurrence of element if (hmap.get(arr[i]) == null) hmap.put(arr[i], 1); // If elements already exists in hash map else hmap.put(arr[i], ++c); } // Print result for (Map.Entry m:hmap.entrySet()) System.out.println("Frequency of " + m.getKey() + " is " + m.getValue()); } // Driver method to test above method public static void main (String[] args) { int arr[] = {10, 34, 5, 10, 3, 5, 10}; printFreq(arr); }} |
Выход:
Частота 34 - 1 Частота 3 - 1 Частота 5 - 2 Частота 10 - 3
Ключевые моменты
- HashMap не поддерживает какой-либо порядок ни на основе ключа, ни на основе значения. Если мы хотим, чтобы ключи поддерживались в отсортированном порядке, нам нужно использовать TreeMap.
- Сложность : операции get / put / containsKey () в среднем равны O (1), но мы не можем гарантировать этого, поскольку все зависит от того, сколько времени требуется для вычисления хэша.
Заявка:
HashMap - это в основном реализация хеширования. Поэтому везде, где нам нужно хеширование с парами ключ-значение, мы можем использовать HashMap. Например, в веб-приложениях имя пользователя хранится как ключ, а данные пользователя хранятся как значение в HashMap для более быстрого извлечения пользовательских данных, соответствующих имени пользователя.
TreeMap может быть немного удобен, когда нам нужно хранить только уникальные элементы в отсортированном порядке. Java.util.TreeMap использует красно-черное дерево в фоновом режиме, что гарантирует отсутствие дубликатов; кроме того, он также поддерживает элементы в отсортированном порядке.
TreeMap <K, V> hmap = new TreeMap <K, V> ();
Below is TreeMap based implementation of same problem. This solution has more time complexity O(nLogn) compared to previous one which has O(n). The advantage of this method is, we get elements in sorted order.
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
/* Java program to print frequencies of all elements using TreeMap */import java.util.*; class Main{ // This function prints frequencies of all elements static void printFreq(int arr[]) { // Creates an empty TreeMap TreeMap<Integer, Integer> tmap = new TreeMap<Integer, Integer>(); // Traverse through the given array for (int i = 0; i < arr.length; i++) { Integer c = tmap.get(arr[i]); // If this is first occurrence of element if (tmap.get(arr[i]) == null) tmap.put(arr[i], 1); // If elements already exists in hash map else tmap.put(arr[i], ++c); } // Print result for (Map.Entry m:tmap.entrySet()) System.out.println("Frequency of " + m.getKey() + " is " + m.getValue()); } // Driver method to test above method public static void main (String[] args) { int arr[] = {10, 34, 5, 10, 3, 5, 10}; printFreq(arr); }} |
Выход:
Частота 3 - 1 Частота 5 - 2 Частота 10 - 3 Частота 34 - 1
Ключевые моменты
- Для таких операций, как добавление, удаление, containsKey, временная сложность равна O (log n, где n - количество элементов, присутствующих в TreeMap.
- TreeMap всегда хранит элементы в отсортированном (возрастающем) порядке, в то время как элементы в HashMap не имеют порядка. TreeMap также предоставляет несколько интересных методов для первого, последнего, пола и потолка ключей.
- HashMap реализует интерфейс карты, а TreeMap реализует интерфейс SortedMap. Интерфейс Sorted Map является дочерним по отношению к Map.
- HashMap реализует хеширование, а TreeMap реализует красно-черное дерево (самобалансирующееся двоичное дерево поиска). Поэтому здесь действуют все различия между хешированием и сбалансированным двоичным деревом поиска.
- И HashMap, и TreeMap имеют свои аналоги HashSet и TreeSet. HashSet и TreeSet реализуют интерфейс Set. В HashSet и TreeSet у нас есть только ключ, а не значение, они в основном используются для просмотра наличия / отсутствия в наборе. Для вышеуказанной проблемы мы не можем использовать HashSet (или TreeSet), поскольку мы не можем хранить счетчики. Пример проблемы, при которой мы предпочли бы HashSet (или TreeSet) HashMap (или TreeMap), - это распечатать все отдельные элементы в массиве.
Статьи по Теме
- LinkedHashmap в Java
- Различия между TreeMap, HashMap и LinkedHashMap в Java
- Различия между HashMap и HashTable в Java
Использованная литература :
https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html
Автор статьи: Чираг Агравал . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше
Вниманию читателя! Не переставай учиться сейчас. Ознакомьтесь со всеми важными концепциями Java Foundation и коллекций с помощью курса "Основы Java и Java Collections" по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .