本文共 3661 字，大约阅读时间需要 12 分钟。

原文地址：

HashMap与TreeMap是中的一部分。

java.util.HashMap类是一种基于哈希的实现。在HashMap中，我们有一个key和一个value，pair <Key,Value> <script type="math/tex" id="MathJax-Element-1"> </script>。

HashMap
   
     hmap = new HashMap
    
     ();
    
   

我们考虑下面的例子，我们需要对已知整型数组中的每个整数计算出现的次数。

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
   
     hmap =                      new HashMap
    
     ();        // 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 1Frequency of 3 is 1Frequency of 5 is 2Frequency of 10 is 3

重点：

• HashMap不会用key或者value维持某种顺序，如果我们想用key进行排序，我们需要用TreeMap。
• 复杂度：get/put/containsKey()操作在平均情况下是O(1)，但是我们不能保证，因为这得看花费多长时间计算hash

应用：

HashMap是哈希算法的一个基本实现。所以无论啥时候我们需要用键值对计算哈希值，我们可以用HashMap。例如，在Web应用中，username保存在HashMap的key中，用户数据保存在value中，为的是根据用户名能够更快地检索出用户数据。

当我们只需要有序地存储唯一元素的时候，TreeMap就比较方便啦。Java.util.TreeMap底层用的是红黑树，它可以确保没有重复元素；另外它可以保证元素是排过序的。

TreeMap
   
     hmap = new TreeMap
    
     ();
    
   

下面是基于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
   
     tmap =                     new TreeMap
    
     ();        // 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 1Frequency of 5 is 2Frequency of 10 is 3Frequency of 34 is 1

重点：

• 像add, remove, containsKey这样的操作时间复杂度是O(log n），这里的n是TreeMap中元素的个数。
• TreeMap总是保持元素是（递增）有序的，但是HashMap中的元素是无序的。TreeMap也提供了一些很酷的方法，比如first，last，floor与key的上取整。

1. HashMap实现的是Map接口，然而TreeMap实现的是SortedMap接口。SortedMap接口是Map接口的孩子。

2. HashMap实现了Hashing，TreeMap实现的是红黑树（一种自平衡的二叉树）。因此所有 应用于此。

3. HashMap与TreeMap都有它们对应的类HashSet与TreeSet。 HashSet与TreeSet实现的都是Set接口。在 HashSet与TreeSet中，我们只有key，没有value，它们主要用于查看元素在set中是否存在。对于上面的问题，我们不能用HashSet (或者TreeSet)，因为我们不能存储计数。一个打印数组中不同元素的例子问题就是，相比较HashMap (或者TreeMap)，我们更倾向于使用HashSet (或者TreeSet)。

   

图片链接：

也可以看看

参考文献：