2022-08-18
原文作者:潘威威 原文地址:https://blog.csdn.net/panweiwei1994

Map的整体结构

先来回顾下Map的整体结构。

层次结构图

202202131622426971.png

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。
  • 都是非同步的。
阅读全文