Hashtable、HashMap、TreeMap 的区别

Hashtable、HashMap、TreeMap 的区别

Hashtable 的特点

Hashtable 早期使用比较普遍的 key-value 结构的数据类，内部也是基于哈希表实现的，内部通过单链表解决冲突问题，当容量不足时，会进行自动扩容，并且是线程安全的类。

也正是因为线程安全，常见的问题就是效率会相对低一些。

另外，Hashtable 内部还实现了序列化接口和克隆接口。

HashMap 的特点

HashMap 和 Hashtable 一样是基于哈希表实现的，每个元素和 HashTable 一样，也都是 key-value 结构，并且容量不足时会自动扩容。主要行为和 HashTable 大致一致。

主要的区别在于 HashMap 不是线程安全的，而且 HashMap 支持 null 键和值。一般情况下，HashMap 调用 put 或者 get 方法，时间复杂度可以达到 O(1)，所以在不需要线程安全的场景下，HashMap 是绝大部分利用键值对存储和拿取数据的首选。

TreeMap 特点

TreeMap 和 HashTable 和 HashMap 有相同之处，同为 key-value 结构存取数据，也支持序列化。

但是其内部实现不同，不再是使用哈希表实现，而是基于红黑树实现的、且提供顺序访问，和 HashMap 不同，TreeMap 的 get、put、remove 等方法的时间复杂度都是 O（log(n)）。 且 TreeMap 不支持存在 null 值的 key。

既然是有序，则其元素的顺序可以指定 Comparator 来实现，或者根据键的自然顺序来判断。

总结

从实现基础结构来说，Hashtable 和 HashMap 都是哈希表实现，而 TreeMap 是由红黑树实现

从元素顺序来说，除了 TreeMap 外，Hashtable 和 HashMap 的元素都是无序的。

从键值来说，除了 HashMap 外，Hashtable 和 TreeMap 都不支持 null 值作为 key。

从线程安全来说，除了 Hashtable 外，HashMap 和 TreeMap 都是线程不安全的。