Java面试题：如何决定使用 HashMap 还是 TreeMap？

如果需要对 Map 执行插入、删除和定位元素这类操作，HashMap 是最好的选择。如果需要对一个有序的 key 集合进行遍历，TreeMap 是更好的选择。

HashMap 和 TreeMap 是 Map 家族中非常常用的两个类，两个类在使用上和本质上有什么区别呢？本文将从这两个方面进行深入的探讨，希望能揭露其本质。

HashMap 和 TreeMap 本质区别

类定义的区别

先看HashMap的定义：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {}

再看TreeMap的定义：

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}

从类的定义来看，HashMap 和 TreeMap 都继承自 AbstractMap，不同的是 HashMap 实现的是 Map 接口，而 TreeMap 实现的是 NavigableMap 接口。NavigableMap 是 SortedMap 的一种，实现了对 Map 中 key 的排序。

这样两者的第一个区别就出来了，TreeMap 是排序的而 HashMap 不是。

面试题广告位

构造函数区别

先看 HashMap 的构造函数：

public HashMap(int initialCapacity, float loadFactor) {}

HashMap 除了默认的无参构造函数之外，还可以接受两个参数 initialCapacity（初始化容量）和 loadFactor（加载因子）。HashMap 的底层结构是 Node 的数组：

transient Node<K,V>[] table

initialCapacity 就是这个 table 数组的初始容量。如果不传 initialCapacity，HashMap 提供了一个默认的值：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

当 HashMap 中存储的数据过多的时候，table 数组就会被装满，这时候就需要扩容，HashMap 的扩容是以 2 的倍数来进行的。而 loadFactor 就指定了什么时候需要进行扩容操作。默认的 loadFactor 是 0.75（即达到容量的 75%，则进行扩容）。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

再来看几个非常有趣的变量：

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

上面的三个变量有什么用呢？在 java8 之前，HashMap 解决 hashcode 冲突的方法是采用链表的形式，为了提升效率，java8 将其转成了 TreeNode。什么时候会发送这个转换呢？

这时候就要看这两个变量 TREEIFY_THRESHOLD 和 UNTREEIFY_THRESHOLD。

有的同学可能发现了，TREEIFY_THRESHOLD 为什么比 UNTREEIFY_THRESHOLD 大 2 呢？其实这个问题我也不知道，但是你看源代码的话，用到 UNTREEIFY_THRESHOLD 时候，都用的是 <=, 而用到 TREEIFY_THRESHOLD 的时候，都用的是 >= TREEIFY_THRESHOLD - 1，所以这两个变量在本质上是一样的。

MIN_TREEIFY_CAPACITY 表示的是如果 table 转换 TreeNode 的最小容量，只有 capacity >= MIN_TREEIFY_CAPACITY 的时候才允许 TreeNode 的转换。

TreeMap 和 HashMap 不同的是，TreeMap 的底层是一个 Entry：

private transient Entry<K,V> root

他的实现是一个红黑树，方便用来遍历和搜索。TreeMap 的构造函数可以传入一个 Comparator，实现自定义的比较方法。

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

如果不提供自定义的比较方法，则使用的是 key 的 natural order。

排序区别

我们讲完两者的本质之后，现在举例说明，先看下两者对排序的区别，代码如下：

@Test
public void withOrderHashMap(){
    Map<String, String> books = new HashMap<String, String>();
    books.put("bob", "books");
    books.put("c", "concurrent");
    books.put("a", "a lock");
    System.out.println(books);
    // {a=a lock, c=concurrent, bob=books}
}

@Test
public void withOrderTreeMap(){
    Map<String, String> books = new TreeMap<String, String>();
    books.put("bob", "books");
    books.put("c", "concurrent");
    books.put("a", "a lock");
    System.out.println(books);
    // {a=a lock, bob=books, c=concurrent}
}

同样的代码，一个使用了 HashMap，一个使用了 TreeMap，我们会发现 TreeMap 输出的结果是排好序的，而 HashMap 的输出结果是不定的。

Null 值的区别

HashMap 可以允许一个 null key 和多个 null value。而 TreeMap 不允许 null key，但是可以允许多个 null value。代码如下：

@Test
public void withNullHashMap() {
    Map<String, String> hashmap = new HashMap<String, String>();
    hashmap.put(null, null);
    System.out.println(hashmap);
    // {null=null}
}

@Test
public void withNullTreeMap() {
    Map<String, String> treemap = new TreeMap<String, String>();
    treemap.put(null, null);
    System.out.println(treemap);
    // java.lang.NullPointerException
}

性能区别

（1）HashMap 的底层是 Array，所以 HashMap 在添加，查找，删除等方法上面速度会非常快。而 TreeMap 的底层是一个 Tree 结构，所以速度会比较慢。

（2）HashMap 因为要保存一个 Array，所以会造成空间的浪费，而 TreeMap 只保存要保持的节点，所以占用的空间比较小。

（3）HashMap 如果出现 hash 冲突的话，效率会变差，不过在 java8 进行 TreeNode 转换之后，效率有很大的提升。

（4）TreeMap 在添加和删除节点的时候会进行重排序，会对性能有所影响。

共同点

（1）两者均不允许 key 重复

（2）两则均不是线程安全的