Java中的HashMap和TreeMap

作者: Arvin Chen 分类: Java 来源: Break易站(www.breakyizhan.com)

HashMap和TreeMap是集合框架的一部分。

Java中的HashMap

java.util.HashMap类是基于Hashing的实现。在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 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);
    }
}

输出:

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。例如,在Web应用程序中,用户名存储为密钥,用户数据作为值存储在HashMap中,以便更快地检索与用户名对应的用户数据。

 

Java中的TreeMap

当我们只需要按排序顺序存储唯一元素时,TreeMap可能会有点方便。Java.util.TreeMap 在后台使用红黑树,确保没有重复项; 此外,它还按排序顺序维护元素。

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

下面是基于TreeMap的相同问题的实现。与具有O(n)的先前的解决方案相比,该解决方案具有更多的时间复杂度O(nLogn)。这种方法的优点是,我们按排序顺序获取元素。

/* 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);
    }
}

输出:

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

关键点

  • 对于add,remove,containsKey等操作,时间复杂度为O(log n,其中n是TreeMap中存在的元素数。
  • TreeMap始终以有序(递增)顺序保留元素,而HashMap中的元素没有顺序。TreeMap还为键的第一个,最后一个,地板和天花板提供了一些很酷的方法。

Java中的HashMap和TreeMap概述

  1. 当TreeMap实现SortedMap接口时,HashMap实现了Map接口。Sorted Map接口是Map的子级。
  2. HashMap实现Hashing,而TreeMap实现Red-Black Tree(自平衡二进制搜索树)。因此,哈希和平衡二进制搜索树之间的所有差异都适用于此处。
  3. HashMap和TreeMap都有对应的HashSet和TreeSet。HashSet和TreeSet实现Set接口。在HashSet和TreeSet中,我们只有key,没有值,这些主要用于查看集合中的存在/不存在。打印数组中的所有不同元素,对于上述问题,我们不能使用HashSet(或TreeSet),因为我们无法存储计数。我们更喜欢HashSet(或TreeSet)而不是HashMap(或TreeMap)的示例。

Java中的HashMap和TreeMap

  •   本文标题:Java中的HashMap和TreeMap - Break易站
    转载请保留页面地址:https://www.breakyizhan.com/java/5329.html
    扫描二维码添加微信 
  • ,领取淘宝优惠券,淘宝购物更优惠。现在添加微信,还可以领取机械键盘优惠券!添加微信后,分享淘宝选中的机械键盘给淘宝机器人即可领取!
    支持我们,就用微信淘宝!

    发表笔记

    电子邮件地址不会被公开。 必填项已用*标注

    更多阅读