Рубрики

HashMap и TreeMap в Java

HashMap и TreeMap являются частью структуры коллекции .

HashMap

Класс java.util.HashMap является реализацией на основе хеширования. В HashMap у нас есть пара ключ-значение <Key, Value>.

 HashMap<K, V> hmap = new HashMap<K, V>();

Давайте рассмотрим ниже пример, где мы должны подсчитать вхождения каждого целого в данном массиве целых чисел.

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-программа для печати частот всех элементов с использованием

   HashMap * /

import java.util.*;

  

class Main

{

    // Эта функция печатает частоты всех элементов

    static void printFreq(int arr[])

    {

        // Создаем пустой HashMap

        HashMap<Integer, Integer> hmap = 

                     new HashMap<Integer, Integer>();

  

        // Пройти через данный массив

        for (int i = 0; i < arr.length; i++)

        {

            Integer c = hmap.get(arr[i]);

  

            // Если это первое вхождение элемента

            if (hmap.get(arr[i]) == null)

               hmap.put(arr[i], 1);

  

            // Если элементы уже существуют в хэш-карте

            else 

              hmap.put(arr[i], ++c);

        }

  

        // Распечатать результат

        for (Map.Entry m:hmap.entrySet())

          System.out.println("Frequency of " + m.getKey() + 

                             " is " + m.getValue());

    }

  

    // Метод драйвера для проверки вышеуказанного метода

    public static void main (String[] args)

    {

        int arr[] = {10, 34, 5, 10, 3, 5, 10};

        printFreq(arr);

    }

}

Выход:

Frequency of 34 is 1
Frequency of 3 is 1
Frequency of 5 is 2
Frequency of 10 is 3

Ключевые моменты

  • HashMap не поддерживает какой-либо порядок ни на основе ключа, ни на основе значения. Если мы хотим, чтобы ключи сохранялись в отсортированном порядке, нам нужно использовать TreeMap.
  • Сложность : операции get / put / containsKey () в среднем имеют значение O (1), но мы не можем гарантировать, что все зависит от того, сколько времени потребуется для вычисления хэша.

Заявка:
HashMap — это в основном реализация хеширования . Поэтому, где бы нам ни понадобилось хеширование с парами ключ-значение, мы можем использовать HashMap. Например, в веб-приложениях имя пользователя хранится в виде ключа, а данные пользователя хранятся в виде значения в HashMap, для более быстрого поиска пользовательских данных, соответствующих имени пользователя.

TreeMap

TreeMap может быть немного удобен, когда нам нужно хранить уникальные элементы только в отсортированном порядке. Java.util.TreeMap использует красно-черное дерево на заднем плане, что гарантирует отсутствие дубликатов; кроме того, он также поддерживает элементы в отсортированном порядке.

 TreeMap<K, V> hmap = new TreeMap<K, V>();

Ниже приведена реализация той же проблемы на основе TreeMap. Это решение имеет большую временную сложность O (nLogn) по сравнению с предыдущим, которое имеет O (n). Преимущество этого метода в том, что мы получаем элементы в отсортированном порядке.

/ * Java-программа для печати частот всех элементов с использованием

   TreeMap * /

import java.util.*;

  

class Main

{

    // Эта функция печатает частоты всех элементов

    static void printFreq(int arr[])

    {

        // Создаем пустой TreeMap

        TreeMap<Integer, Integer> tmap =

                     new TreeMap<Integer, Integer>();

  

        // Пройти через данный массив

        for (int i = 0; i < arr.length; i++)

        {

            Integer c = tmap.get(arr[i]);

  

            // Если это первое вхождение элемента

            if (tmap.get(arr[i]) == null)

               tmap.put(arr[i], 1);

  

            // Если элементы уже существуют в хэш-карте

            else

              tmap.put(arr[i], ++c);

        }

  

        // Распечатать результат

        for (Map.Entry m:tmap.entrySet())

          System.out.println("Frequency of " + m.getKey() + 

                             " is " + m.getValue());

    }

  

    // Метод драйвера для проверки вышеуказанного метода

    public static void main (String[] args)

    {

        int arr[] = {10, 34, 5, 10, 3, 5, 10};

        printFreq(arr);

    }

}

Выход:

Frequency of 3 is 1
Frequency of 5 is 2
Frequency of 10 is 3
Frequency of 34 is 1

Ключевые моменты

  • Для таких операций, как добавление, удаление, содержит ключ, временная сложность равна O (log n, где n — количество элементов, присутствующих в TreeMap.
  • TreeMap всегда сохраняет элементы в отсортированном (возрастающем) порядке, в то время как элементы в HashMap не имеют порядка. TreeMap также предоставляет несколько интересных методов для первого, последнего, пола и потолка ключей.

Обзор:

  1. HashMap реализует интерфейс Map, а TreeMap реализует интерфейс SortedMap. Интерфейс Sorted Map является дочерним элементом Map.
  2. HashMap реализует хеширование, в то время как TreeMap реализует красно-черное дерево (самобалансирующееся дерево двоичного поиска). Поэтому все различия между хешированием и сбалансированным бинарным деревом поиска применимы здесь.
  3. И HashMap, и TreeMap имеют свои аналоги HashSet и TreeSet. HashSet и TreeSet реализуют интерфейс Set . В HashSet и TreeSet у нас есть только ключ, без значения, они в основном используются, чтобы увидеть наличие / отсутствие в наборе. Для решения вышеуказанной проблемы мы не можем использовать HashSet (или TreeSet), так как мы не можем хранить счетчики. Пример проблемы, когда мы предпочли бы HashSet (или TreeSet), а не HashMap (или TreeMap), состоит в печати всех отдельных элементов в массиве.

Статьи по Теме

Ссылки :
https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html

Эта статья предоставлена Чирагом Агравалом . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

HashMap и TreeMap в Java

0.00 (0%) 0 votes