Map的整体结构
先来回顾下Map的整体结构。
层次结构图
Map是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。 Map没有继承Collection接口。
- AbstractMap：实现了Map接口的抽象类。Map的基本实现，其他Map的实现类可以通过继承AbstractMap来减少编码量。
- SortedMap：继承Map。保证按照键的升序排列的映射，对entrySet、keySet和values方法返回的结果进行迭代时，顺序就会反映出来。
- NavigableMap：继承SortedMap，含有返回特定条件最近匹配的导航方法。
- HashMap：Map接口基于哈希表的实现，是使用频率最高的用于键值对处理的数据类型。它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，特点是访问速度快，遍历顺序不确定，线程不安全，最多允许一个key为null，允许多个value为null。可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap类。
- HashTable：Hashtable和HashMap从存储结构和实现来讲有很多相似之处，不同的是它承自Dictionary类，而且是线程安全的，另外Hashtable不允许key和value为null。并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以使用HashMap，需要线程安全的场合可以使用ConcurrentHashMap。
- LinkedHashMap： LinkedHashMap继承了HashMap，是Map接口的哈希表和链接列表实现。它维护着一个双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
- WeakedHashMap： 以弱键实现的基于哈希表的Map。在WeakHashMap中，当某个键不再正常使用时，将自动移除其条目。
- TreeMap ： Map接口基于红黑树的实现。
实现类比较
| 实现类 | 数据结构 | 是否线程安全 | key是否可为null | 是否有序 |
|---|---|---|---|---|
| HashMap | 数组+链表+红黑树（sinceJDK1.8） | 否 | 是 | 否 |
| Hashtable | 数组+链表 | 是 | 否 | 否 |
| LinkedHashMap | 数组+链表+红黑树（sinceJDK1.8）+双重链接列表 | 否 | 是 | 是 |
| WeakedHashMap | 数组+链表+队列 | 否 | 是 | 否 |
| TreeMap | 红黑树 | 否 | 否 | 是 |
HashMap与Hashtable
不同点
| 不同点 | HashMap | Hashtable |
|---|---|---|
| 数据结构 | 数组+链表+红黑树 | |
| 继承的类不同 | 继承AbstractMap | 继承Dictionary |
| 是否线程安全 | 否 | 是 |
| 性能高低 | 高 | 低 |
| 默认初始化容量 | 16 | 11 |
| 扩容方式不同 | 原始容量x2 | 原始容量x2+1 |
| 底层数组的容量为2的整数次幂 | 要求一定为2的整数次幂 | 不要求 |
| 确认key在数组中的索引的方法不同 | i=(n-1)&hash; | index=(hash&0x7FFFFFFF)%tab.length; |
| 遍历方式 | Iterator(迭代器) | Iterator(迭代器)和Enumeration(枚举器) |
| Iterator遍历数组顺序 | 索引从小到大 | 索引从大到小 |
Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
相同点
- 都实现了Map、Cloneable、java.io.Serializable接口。
- 数据结构中都存在数组+链表。
HashMap与LinkedHashMap
不同点
| 不同点 | HashMap | LinkedHashMap |
|---|---|---|
| 数据结构 | 数组+链表+红黑树 | 数组+链表+红黑树+双向循环链表 |
| 是否有序 | 无序 | 有序 |
| 性能高低 | 高 | 低 |
| 随机访问速度 | 快 | 慢 |
| 插入速度 | 慢 | 快 |
相同点
- 都是基于哈希表的实现。
- 存储的是键值对映射。
- 都继承了AbstractMap，实现了Map、Cloneable、Serializable。
- 它们的构造函数都一样。
- 默认的容量大小是16，默认的加载因子是0.75。
- 都允许key和value为null。
- 都是线程不安全的。
HashMap与WeakHashMap
不同点
| 不同点 | HashMap | WeakHashMap |
|---|---|---|
| 数据结构 | 数组+链表+红黑树 | 数组+链表+队列 |
| 键 | 强引用 | 弱引用 |
| 是否实现Cloneable和Serializable | 是 | 否 |
相同点
- 都是基于哈希表的实现。
- 都以键值对的形式存储数据。
- 都继承了AbstractMap，实现了Map接口。
- 都支持key和value为null。
- 都是非同步的。
- 都是无序的。
HashMap与TreeMap
不同点
| 不同点 | HashMap | TreeMap |
|---|---|---|
| 数据结构 | 数组+链表+红黑树 | 红黑树 |
| 是否有序 | 否 | 是 |
| 是否实现NavigableMap | 否 | 是 |
| 是否允许key为null | 是 | 否 |
| 增删改查操作的时间复杂度 | O(1) | log(n) |
相同点
- 都以键值对的形式存储数据。
- 都继承了AbstractMap，实现了Map、Cloneable、Serializable。
- 都是非同步的。
