Java中的HashMap和TreeMap

HashMap和TreeMap是集合框架中的一部分。 HashMap java.util.HashMap类是一种基于哈希表的实现。在HashMap中，我们有键和值对<键，值>。

 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 当我们只需要以排序的方式存储唯一元素时，TreeMap可以非常方便。Java.util.TreeMap在后台使用红黑树来确保没有重复项；此外，它还维护元素的排序顺序。

 TreeMap<K，V> hmap = new TreeMap<K，V>（）;

以下是基于TreeMap的同一问题的实现。该解决方案的时间复杂度比前一个解决方案的O(n)高O(nLogn)。这种方法的优点是，我们可以按排序顺序获得元素。

/* 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

要点

对于像添加、删除、containsKey这样的操作，时间复杂度为O(log n)，其中n为TreeMap中存在的元素数。
TreeMap始终以排序(递增)顺序来保存元素，而HashMap中的元素没有顺序。 TreeMap还提供了一些不错的方法，用于获取键的第一项、最后一项、floor和ceiling

HashMap和TreeMap之间的区别：

ID	HashMap	TreeMap
1.	它不提供元素的任何顺序。	它为元素提供了顺序。
2.	它的速度很快。	它的速度很慢。
3.	它允许一个键为空，并且还允许多个值。	它不允许键为空，但允许多个空值。
4.	它消耗更多的内存空间。	它消耗更少的内存空间。
5.	它只有基本功能。	它具有高级功能。
6.	用equals()比较键。	用compare或compareTo()比较键。
7.	它的复杂度为O(1)。	它的复杂度为O(log n)。

HashMap实现Map接口，而TreeMap实现SortedMap接口。SortedMap接口是Map接口的子类。
HashMap实现哈希，而TreeMap实现红黑树(一种自平衡二叉搜索树)。因此，哈希和平衡二叉搜索树之间的所有差异都适用于此处。
HashMap和TreeMap都有它们的对应物HashSet和TreeSet。HashSet和TreeSet实现Set接口。在HashSet和TreeSet中，我们只有键，没有值，这些主要用于查看集合中的存在/不存在。对于上述问题，我们不能使用HashSet(或TreeSet)，因为我们不能存储计数。我们优先选择HashSet(或TreeSet)而不是HashMap(或TreeMap)的示例问题是打印数组中的所有不同元素。

Java中的HashMap和TreeMap