Java中的HashMap和TreeMap-yiteyi-C++库

HashMap和TreeMap是收集框架 .

null

哈希图

 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中，以便更快地检索与用户名对应的用户数据。

树图红黑树

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

下面是同样问题的基于树映射的实现。与之前的解决方案相比，该解决方案的时间复杂度为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（logn），其中n是树映射中存在的元素数。
TreeMap始终保持元素的排序（递增）顺序，而HashMap中的元素没有顺序。TreeMap还为第一、最后、地板和天花板键提供了一些很酷的方法。

概述：

HashMap实现Map接口，TreeMap实现SortedMap接口。排序后的地图界面是地图的子界面。
HashMap实现了哈希，而TreeMap实现了红黑树（一种自平衡的二进制搜索树）。因此所有哈希和平衡二叉搜索树的区别在这里申请。
HashMap和TreeMap都有对应的HashSet和TreeSet。HashSet和TreeSet实现设置接口 .在HashSet和TreeSet中，我们只有键，没有值，它们主要用于查看集合中的存在/不存在。对于上述问题，我们不能使用HashSet（或TreeSet），因为我们不能存储计数。我们更喜欢HashSet（或TreeSet）而不是HashMap（或TreeMap）的一个示例问题是打印数组中所有不同的元素。

collection_interfaces

本文由 希拉格·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

Java