Hashtable、HashMap、TreeMap都是常见的一些Map实现，是以键值对的形式存储和操作数据的容器类型。

Hashtable是早期Java类库提供的一个哈希表实现，本身是同步的，不支持null键和值，由于同步导致的性能开销，所以很少被推荐使用。

HashMap是应用更加广泛的哈希表实现，行为上大致与Hashtable一致，主要区别在于HashMap不是同步的，支持null键和值等。通常情况下，HashMap进行put或者get操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选，比如，实现一个用户ID和用户信息对应的运行时存储结构。

TreeMap则是基于红黑树的一种提供顺序访问的Map，和HashMap不同，它的get、put、remove之类操作都是O(log(n))的时间复杂度，具体顺序可以由指定的Comparator来决定，或者根据键的自然顺序来判断。

知识扩展

  • Map虽然通常被包括在Java集合框架里，但是其本身并不是狭义上的集合类型（Collection）。简单类图如下：

image.png

  • 有序的Map有：LinkedHashMap、TreeMap。其他类型的Map都是无序的。

  • HashMap解读：其内部结构如下图所示，它可以看作是数组和链表的复合结构（又叫散列表），数组被分为一个个桶（bucket），通过哈希值决定了键值对在这个数组的寻址；哈希值相同的键值对，则以链表形式存储。如果链表大小超过阈值（MIN_TREEIFY_CAPACITY），链表就会被改造为树形结构，此过程被称为树化。存储键值对时，散列函数会将其均匀分配到桶数组中，以此来保证不会所有的键值对都存在一个桶中而导致扩容。扩容是指增加桶数组的个数。扩容会重新计算每个元素在新数组中的位置，然后再进行存储。这是一个十分消耗性能的操作。容量是指桶的个数。

image.png

  • 为什么要进行树化呢？本质上是一个安全问题。因为在元素放置过程中，如果一个对象哈希冲突，都被放置到一个桶里，则会形成一个链表，我们知道链表查询是线性的，会严重影响存取的性能。而在现实世界，构造哈希冲突的数据并不是非常复杂的事情，恶意代码就可以利用这些数据大量与服务器端交互，导致服务器端CPU大量占用，这就构成了哈希碰撞拒绝服务攻击。

  • HashMap扩容的的条件是：元素数量 >= 容量 负载因子。负载因子默认是0.75，也可以自由设置。设置的过大则空间利用率高，但查询效率会变低；设置的过小，则空间利用率低，查询效率会变高。每次扩容，桶数量都增加一倍。扩容后，需要将老的数组中的元素重新计算并放到新的数组，这是扩容的一个主要开销来源。为了避免扩容的影响，我们可以简单预估并设置合适的容量大小。预估方法：因为当满足公式 负载因子 容量 > 元素数量 时不会扩容，等同于当 容量 > 元素数量 / 负载因子 时不会扩容。而容量又是 2 的幂数，容量就会轻易的得出，最后在初始化时设置即可。