文档章节

Java集合框架之Map

士别三日
 士别三日
发布于 05/26 17:48
字数 2908
阅读 5
收藏 0

Java集合框架之Map

1. Map的类结构

输入图片说明

首先了解一些概念,Map里面包含的元素叫做Entry,Entry包含了Key和Value,即Entry<K,V>。Entry<K,V>是Map接口的一个内部接口。在AbstractMap这个抽象类里面,抽象出了一个Entry的集合:Set<Entry<K,V>>。这个集合包含了Map里面所有的元素,怎么生成这个集合就由子类来实现。而每个集合都有一个迭代器,通过迭代器,AbstractMap就可以实现Map中定义的大部分行为,比如get、contains等方法。但是put方法必须由具体实现类实现,因为put方法才能完成对Set<Entry<K,V>>的构建。

Map接口里面定义了所有的行为,AbstractMap也通过抽象出Set<Entry<K,V>>,实现了Map的大多数行为。当然子类可以选择重新实现,事实上,它的所有实现类现在都没有用AbstractMap的实现,我猜想以前的版本肯定是用过的,只不过现在被弃用了,不做深究。至于为啥会被弃用,很大一部分原因应该是外部迭代是单核机器时代的产物,现在放在多核环境下,是非常低效的。现在流行的内部迭代用抽象的方法就行不通了,所以AbstractMap才会一直没有改进。AbstractMap现在基本上没啥用了,不去掉是为了兼容老旧应用代码。

然后再看看几个常用的Map实现:HashTable、HashMap、LinkedHashMap和TreeMap。下面一一进行分析。


2. HashTable

HashTable从Java 1.0版本就有了,而AbstractMap和HashMap是Java 1.2才开始有的。所以它没有继承AbstractMap。但是它的实现确实和HashMap类似,它也有一个内部静态类叫Entry,实现了Map.Entry。HashTable不仅实现了Map接口,还继承了Dictionary这个抽象类(里面全是抽象方法)。但是Dictionary有的方法,在Map接口里面基本都有类似的方法。不知道这样设计是出于什么原因考虑。反正系统都是迭代开发出来的,Java平台本身也一样,为了向前兼容,会选择不去改动原有设计,而加上新的设计。不做深究。

另外要提的是,HashTable是线程安全的,也就是每个公开的方法都是同步方法。因为同步带来效率低下,所以HashTable使用的场景很少(设计HashMap就是为了在大多数场景下替换它)。但是注意看,它有一个子类Properties。顾名思义,它可以读写*.properties配置文件。这也算是HashTable的一个主要应用场景了。HashTable的key和value都不能为null。初始容量为11,不要求数组长度一定要是2的整数次幂。扩容之后为原来的2倍加1。

HashTable的实现这里就不讲了,因为原理和HashMap类似。


3.HashMap

整个Map体系中,HashMap使用场景是最多的。原因很简单,因为它是效率最高的实现。它没有做线程同步,所以一般放在方法内部作为局部变量使用,如果确定不存在竞争的情况,也可以作为全局变量。

先看一下HashMap内部的数据结构示意图。

输入图片说明

  • HashMap维护了一个桶数组,数组长度capacity可以在实例化的时候指定,默认长度是16。capacity总是2的整数次幂,如果你指定的capacity不是2的整数次幂,就会帮你自动调整为2的整数次幂,比如你指定5,就会给你调整为8,你指定9,就会帮你调整为16。capacity不能小于0,最大为2的30次方。
  • 在实例化的时候,还有一个参数叫做负载因子loadFactor。当Entry的个数 > capacity*loadFactor的时候,数组就会进行扩容resize,capacity变为原来的两倍。loadFactor默认值为0.75。
  • 在把元素放入Map的时候,首先会对元素的Key进行Hash处理,映射到某个桶。如果两个不同的Key Hash映射到了同一个桶,就发生了Hash碰撞。
  • 桶内部用一个双向链表数据结构来处理Hash碰撞问题。桶中每进入一个新元素,都会把它放在链表的头部。在Java 8以后,当链表的长度达到一定程度后,就会树化,链表就会变成一个红黑树。查询链表的时间复杂度是O(n),查询红黑树的时间复杂度是O(logn)。当桶中的元素很大时,红黑树的性能优势就很明显了。

以上就是HashMap的主要设计特性。我们可以再反过来思考一下为什么要这么设计?

首先,负载因子默认0.75,所以正常情况下发生hash碰撞的概率其实非常小(数组还没填满就扩容了)。而且HashMap采用的哈希算法也在尽量避免Hash碰撞。也就是说,HashMap最理想的状态就是每个桶只有一个元素,这时整个HashMap是用一个数组结构支撑的,这时查询性能最优。但是为啥不直接用一个数组来实现呢?其实是为了查询,单纯用数组就必须遍历整个数组才能找出想要找的元素。用Hash算法把key和数组下标对应起来,就不用遍历了。所以,负载因子不能设置的很大,不然就偏离设计初衷了。但是负载因子也不能设置的很小,因为每一次扩容resize,里面的元素都要重新分配桶,产生不必要的开销。负载因子默认值0.75通常不需要改动。Hash算法在这里是一种用空间换时间的算法。

然后,Hash碰撞本质上是一个人们不想遇到的问题,但是肯定会遇到。遇到问题以后,需要解决问题。在Java 8以前,都是用双向链表来解决hash碰撞问题。每次新元素都放在链表头部。先通过Key的Hash映射找到桶中的链表,再遍历链表找到要找的元素。

最后,后来Java8为啥要加入树化呢?因为有一种攻击叫Hash碰撞拒绝服务攻击。就是有人故意构造具有Hash冲突的数据,然后跟服务器进行交互,导致查询性能下降(链表查询性能是O(n)),占用服务器CPU,最终导致服务不可用。所以引入树化,把链表结构替换成红黑树,缓解这种攻击问题。为什么不直接只用红黑树,丢弃链表呢?因为当元素数量小的时候,链表性能要优于红黑树,想象一下f(n)=n和f(n)=log10n的坐标图。

我们再总结一下HashMap的最佳实践:

  • 尽量把HashMap当做局部变量,避免多线程竞争
  • 负载因子loadFactor一般不用变,这是数学家们算好的一个数字
  • 根据业务情况确定初始容量capacity,减少扩容带来的开销

HashTable内部实现也差不多,不过每个公开方法都是同步的。还有一种同步方案是使用同步包装器,Collections.synchronizedMap(Map<K,V> map)。但是,这两种方案都不适用于高并发情况。java.concurrent包里面有个ConcurrentHashMap,适用于高并发情况,后面专门讲。


4.TreeMap

TreeMap实现了SortedMap和NavigableMap。说明TreeMap里面的元素是有顺序的,并且元素具有导航能力(自迭代)。它们的顺序是由key的顺序关系决定的,通过Comparator或Comparable(自然顺序)来决定。TreeMap由红黑树数据结构来实现,红黑树的查询时间复杂度为O(logn),而链表结构的查询时间复杂度为O(n),所以它的查询性能要好于链表结构,而且数据量越大优势越明显。但是插入数据的时间复杂度要比链表高。


5.LinkedHashMap

LinkedHashMap是HashMap的子类,它是按访问顺序排序的,这里的访问包括对元素的所有操作(增删改查)。很容易用LinkedHashMap实现一个LRU缓存。


6.ConcurrentHashMap

在Java 8以前,ConcurrentHashMap的实现是基于分离锁。也就是将内部进行分段(Segment),里面则是 HashEntry 的数组,和 HashMap 类似,哈希相同的条目也是以链表形式存放。下图是它的数据结构示意图:

输入图片说明

在每个Segment上加一把锁,这样有多少个Segment,就可以有多少条线程同时操作这个Map,而不会发生竞争。这样在多线程环境下,就不用像HashTable一样锁定整个Map了。

Segment的数量是由concurrentcyLevel决定,默认值是16,可以在实例化的时候指定。这个数值也要求必须是2的整数次幂,如果你指定的不是2的整数次幂,就会帮你自动调整到2的整数次幂。这个值是不可变的。Segment是基于ReentrantLock的扩展实现,本身是同步的。ConcurrentHashMap也有扩容,但是它是针对Segment进行扩容,而不是整体扩容,有一个Segment达到扩容条件了,不会影响其他Segment。

分离锁也有它的局限性,它能保证每个Segment都是线程安全的,但是每个Segment都线程安全等于整个Map都线程安全吗?不是的,比如ConcurrentHashMap的size方法,它是计算整个Map有多少个元素的方法,如果不进行同步处理,size方法得到的数字可能就是错的。如果对size进行同步处理,就需要锁定所有的Segment,开销是很大的。所以ConcurrentHashMap的实现是在锁定之前,通过重试机制监控各个Segment数量有没有发生变化,如果没有变化,直接返回计算值,如果有变化才锁定。

Java8的实现是怎样的呢?

首先,它弃用了Segment。不再使用分段的思想做并发了。可想而知,concurrentcyLevel这个参数也没用了。但是Segment和concurrentcyLevel的定义都还保留着,但仅仅是为了保证序列化时的兼容性而已,不再有任何结构上的用处。

那它怎么保证线程安全呢?一、数据存储利用 volatile 来保证可见性; 二、使用 CAS 等操作,在特定场景进行无锁并发操作;三、使用 Unsafe、LongAdder 之类底层手段,进行极端情况的优化。这些知识本文不做探究。

我们再总结一下ConcurrentHashMap的最佳实践:

  • 没有多线程竞争的情况下,不要用ConcurrentHashMap,因为没有任何同步机制的HashMap性能才是最好的。
  • 在有多线程竞争的情况下,尽量使用ConcurrentHashMap。参数设置原则同HashMap。

本文是基于Java 8做的总结,以后Map框架的设计一定会继续演化。本文也提到一些演化的蛛丝马迹,帮助大家理解Map框架为什么会是现在这个样子。技术会演化,演化会有原因,找出这些原因其乐无穷。

理解本文的扩展知识:

  1. 外部迭代和内部迭代是什么?有什么区别?
  2. Hash算法是什么?它有什么用途?
  3. CAS是什么?和锁比起来有什么优势劣势?

© 著作权归作者所有

共有 人打赏支持
士别三日

士别三日

粉丝 35
博文 30
码字总数 43081
作品 0
深圳
程序员
[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

吾生也有涯,而知也无涯。———《庄子》 通过上一篇文章,我们已经知道设计一个线程安全类的原则和步骤,以及在设计过程中我们应当注意的细节。实际上,Java 的集合库包含了线程安全集合和非...

seaicelin
05/25
0
0
HashMap和Hashtable的区别

HashMap和Hashtable的比较是Java面试中的常见问题,用来考验程序员是否能够正确使用集合类以及是否可以随机应变使用多种思路解决问题。HashMap的工作原理、ArrayList与Vector的比较以及这个问...

LCZ777
2014/03/29
0
0
【JAVA集合框架二 】java集合框架容器 java框架层级 继承图结构 集合框架的抽象类 集合框架主要实现类

本文关键词: java集合框架 框架设计理念 容器 继承层级结构 继承图 集合框架中的抽象类 主要的实现类 实现类特性 集合框架分类 集合框架并发包 并发实现类 什么是容器? 由一个或多个确定的元...

noteless
07/09
0
0
day14_DBUtils学习笔记

一、DBUtils介绍 Apache公司开发的框架。   DBUtils是java编程中的数据库操作实用工具,小巧简单实用。   DBUtils封装了对JDBC的操作,简化了JDBC操作。可以少写代码。 commons-dbutils 是...

黑泽明军
05/20
0
0
Java编程学习:集合框架详解

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰
05/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

day63-20180821-流利阅读笔记-待学习

性别歧视在日本:“我是女生,所以社会不让我学医” 毛西 2018-08-21 1.今日导读 大家在看病的时候,有留意过女医生的比例吗?在性别歧视现象十分严重的日本,男医生和女医生的比例达到了惊人...

aibinxiao
42分钟前
2
0
Ubuntu18.04 显卡GF-940MX安装NVIDIA-390.77

解决办法: 下面就给大家一个正确的姿势在Ubuntu上安装Nvidia驱动: (a)首先去N卡官网下载自己显卡对应的驱动:www.geforce.cn/drivers (b)下载后好放在英文路径的目录下,怎么简单怎么来...

AI_SKI
今天
4
0
深夜胡思乱想

魔兽世界 最近魔兽世界出了新版本, 周末两天升到了满级,比之前的版本体验好很多,做任务不用抢怪了,不用组队打怪也是共享拾取的。技能简化了很多,哪个亮按哪个。 运维 服务器 产品 之间的...

Firxiao
今天
1
0
MySQL 8 在 Windows 下安装及使用

MySQL 8 带来了全新的体验,比如支持 NoSQL、JSON 等,拥有比 MySQL 5.7 两倍以上的性能提升。本文讲解如何在 Windows 下安装 MySQL 8,以及基本的 MySQL 用法。 下载 下载地址 https://dev....

waylau
今天
1
0
微信第三方平台 access_token is invalid or not latest

微信第三方开发平台code换session_key说的特别容易,但是我一使用就带来无穷无尽的烦恼,搞了一整天也无济于事. 现在记录一下解决问题的过程,方便后来人参考. 我遇到的这个问题搜索了整个网络也...

自由的开源
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部