文档章节

HashMap深度解析(二)

宇哥v587
 宇哥v587
发布于 2017/07/18 15:54
字数 2490
阅读 1
收藏 0

 上一篇 比较深入的分析了 HashMap 在 put 元素时的整体过程,Java Collections Framework中实际操作的都是数组或者链表,而我们通常不需要显示的维护集合的大小,而是集合类框架中内部维护,方便的同时,也带来了性能的问题。
       HashMap 有两个参数影响其性能:初始容量加载因子。默认初始容量是 16,加载因子是 0.75。容量是哈希表中桶 ( Entry 数组 ) 的数量,初始容量只是哈希表在创建时的容量加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,通过调用 rehash 方法将容量翻倍。
       HashMap中定义的成员变量如下:

  1. static final int DEFAULT_INITIAL_CAPACITY = 16;   // 默认初始容量为16,必须为2的幂  
  2.  
  3. static final int MAXIMUM_CAPACITY = 1 << 30;    // 最大容量为2的30次方  
  4.  
  5. static final float DEFAULT_LOAD_FACTOR = 0.75f;  // 默认加载因子0.75  
  6.   
  7. transient Entry<K,V>[] table;  // Entry数组,哈希表,长度必须为2的幂  
  8.   
  9. transient int size;  // 已存元素的个数  
  10.   
  11. int threshold;  // 下次扩容的临界值,size>=threshold就会扩容  
  12.   
  13. final float loadFactor;  // 加载因子  

       我们看字段名称大概就能知道其含义,看 Doc 描述就能知道其详细要求,这也是我们日常编码中特别需要注意的地方,不要写让别人看不懂的代码,除非你写的代码是一次性的。需要注意的是,HashMap 中的容量 MUST be a power of two,翻译过来就是必须为2的幂,这里的原因稍后再说。再来看一下HashMap初始化,HashMap一共重载了4个构造方法,分别为:

构造方法摘要
HashMap()
          构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)
          构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)
          构造一个带指定初始容量和加载因子的空 HashMap。
HashMap(Map<? extendsK,? extendsV> m)
          构造一个映射关系与指定 Map 相同的 HashMap。

       看一下第三个构造方法源码,其它构造方法最终调用的都是它。

  1. public HashMap(int initialCapacity, float loadFactor) {  
  2.     // 参数判断,不合法抛出运行时异常  
  3.     if (initialCapacity < 0)  
  4.         throw new IllegalArgumentException("Illegal initial capacity: " +  
  5.                                            initialCapacity);  
  6.     if (initialCapacity > MAXIMUM_CAPACITY)  
  7.         initialCapacity = MAXIMUM_CAPACITY;  
  8.     if (loadFactor <= 0 || Float.isNaN(loadFactor))  
  9.         throw new IllegalArgumentException("Illegal load factor: " +  
  10.                                            loadFactor);  
  11.   
  12.     // Find a power of 2 >= initialCapacity  
  13.     // 这里需要注意一下  
  14.     int capacity = 1;  
  15.     while (capacity < initialCapacity)  
  16.         capacity <<= 1;  
  17.   
  18.     // 设置加载因子  
  19.     this.loadFactor = loadFactor;  
  20.     // 设置下次扩容临界值  
  21.     threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);  
  22.     // 初始化哈希表  
  23.     table = new Entry[capacity];  
  24.     useAltHashing = sun.misc.VM.isBooted() &&  
  25.             (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);  
  26.     init();  
  27. }  

       我们在日常做 底层开发 时,必须要严格控制入参,可以参考一下 Java 源码及各种开源项目源码,如果参数不合法,适时的抛出一些运行时异常,最后到应用层捕获。看第14-16行代码,这里做了一个移位运算,保证了初始容量一定为2的幂,假如你传的是5,那么最终的初始容量为8。源码中的位运算随处可见啊=。=!


       到现在为止,我们有一个很强烈的问题,为什么 HashMap 容量一定要为 2 的幂呢?HashMap 中的 数据结构 是 数组+单链表 的组合,我们希望的是元素存放的更均匀,最理想的效果是,Entry 数组中每个位置都只有一个元素,这样,查询的时候效率最高,不需要遍历单链表,也不需要通过 equals 去比较 K,而且空间利用率最大。那如何计算才会分布最均匀呢?我们首先想到的就是 % 运算,哈希值 % 容量=bucketIndex,SUN的大师们是否也是如此做的呢?我们阅读一下这段源码:

  1. static int indexFor(int h, int length) {  
  2.     return h & (length-1);  
  3. }  

 

       又是位运算,高帅富啊!这里 h 是通过 K 的 hashCode 最终计算出来的哈希值,并不是 hashCode 本身,而是在 hashCode 之上又经过一层运算的 hash 值,length 是目前容量。这块的处理很有玄机,与容量一定为2的幂环环相扣,当容量一定是2^n时,h & (length - 1) == h % length,它俩是等价不等效的,位运算效率非常高,实际开发中,很多的数值运算以及逻辑判断都可以转换成位运算,但是位运算通常是难以理解的,因为其本身就是给电脑运算的,运算的是二进制,而不是给人类运算的,人类运算的是十进制,这也是位运算在普遍的开发者中间不太流行的原因(门槛太高)。这个等式实际上可以推理出来,2^n 转换成二进制就是 1+n 个 0,减 1 之后就是 0+n 个 1,如 16 -> 10000,15 -> 01111,那根据 & 位运算的规则,都为 1(真) 时,才为 1,那 0≤ 运算后的结果 ≤15,假设 h <= 15,那么运算后的结果就是 h 本身,h >15,运算后的结果就是最后三位二进制做 & 运算后的值,最终,就是 % 运算后的余数,我想,这就是容量必须为 2 的幂的原因。HashTable 中的实现对容量的大小没有规定,最终的 bucketIndex 是通过取余来运算的。

注:我在考虑这样做是否真的是最好,规定容量大小一定为 2 的幂会浪费许多空间成本,而时间上的优化针对当今越来越牛逼的 CPU 是否还提升了许多,有些资料上说,CPU 处理除法和取余运算是最慢的,这个应该取决于语言调用 CPU 指令的顺序和 CPU 底层实现的架构,也是有待验证,可以用 Java 写段程序测试一下,不过我想,CPU 也是通过人来实现,人脑运算的速度应该是加法 > 减法 > 乘法 > 除法 > 取模(这里指的是正常的算法,不包括速算),CPU 也应是如此。


       通常,默认加载因子 (0.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数  HashMap  类的操作中,包括  get  和  put  操作,都反映了这一点,可以想想为什么)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地降低 rehash 操作次数。如果初始容量 > ( 最大条目数 / 加载因子 ) (实际上就是最大条目数小于初始容量*加载因子),则不会发生 rehash 操作。 


       如果很多映射关系要存储在 HashMap 实例中,则相对于按需执行自动的 rehash 操作以增大表的容量来说,使用足够大的初始容量创建它将使得映射关系能更有效地存储。 当 HashMap 存放的元素越来越多,到达临界值(阀值) threshold 时,就要对 Entry 数组扩容,这是 Java 集合类框架最大的魅力,HashMap 在扩容时,新数组的容量将是原来的 2 倍,由于容量发生变化,原有的每个元素需要重新计算bucketIndex,再存放到新数组中去,也就是所谓的 rehash。HashMap 默认初始容量 16,加载因子0.75,也就是说最多能放 16*0.75=12 个元素,当 put 第 13 个时,HashMap 将发生 rehash,rehash 的一系列处理比较影响性能,所以当我们需要向 HashMap 存放较多元素时,最好指定合适的初始容量和加载因子,否则HashMap默认只能存 12 个元素,将会发生多次 rehash 操作。


       HashMap 所有集合类视图所返回迭代器都是快速失败的 ( fail-fast ),在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器自身的 remove 或 add 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败。注意,迭代器的快速失败行为不能得到保证,一般来说,存在不同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。至于为什么通过迭代器自身的remove 或 add 方法就不会出现这个问题,可以参考我之前的文章List比较好玩的操作中第三个和第四个示例。


       HashMap 是线程不安全的实现,而 HashTable 是线程安全的实现,关于线程安全与不安全可以参考我之前的文章Java线程(一):线程安全与不安全,所谓线程不安全,就是在多线程情况下直接使用 HashMap 会出现一些莫名其妙不可预知的问题,多线程和单线程的区别:单线程只有一条执行路径,而多线程是并发执行(非并行),会有多条执行路径。如果 HashMap 是只读的(加载一次,以后只有读取,不会发生结构上的修改),那使用没有问题。那如果 HashMap 是可写的(会发生结构上的修改),则会引发诸多问题,如上面的 fail-fast,也可以看下这里,这里就不去研究了。
        那在多线程下使用 HashMap 我们需要怎么做,几种方案:

  • 在外部包装HashMap,实现同步机制
  • 使用 Map m = Collections.synchronizedMap(new HashMap(...)); 这里就是对 HashMap 做了一次包装
  • 使用java.util.HashTable,效率最低
  • 使用java.util.concurrent.ConcurrentHashMap,相对安全,效率较高

       (完)

本文转载自:http://blog.csdn.net/ghsau/article/details/16890151

宇哥v587
粉丝 1
博文 47
码字总数 20855
作品 0
南京
程序员
私信 提问
HashMap深度解析(二)

本文来自:高爽|Coder,原文地址:http://blog.csdn.net/ghsau/article/details/16890151,转载请注明。 上一篇比较深入的分析了HashMap在put元素时的整体过程,Java Collections Framework中...

无信不立
2016/03/23
0
0
java HashMap源码深度解析

一、HashMap是什么 HashMap是基于哈希表的Map接口的实现,提供所有的映射的操作,允许null值和null键,存储的是一个键值对对象Entry<K,V>。 是基于数组+链表的结构实现的,在内部维护一个tab...

yangyangyyyy
01/02
30
0
容器类源码解析系列(三)—— HashMap 源码分析(最新版)

容器类源码解析系列(三)—— HashMap 源码分析(最新版) 前言 本篇文章是《Java容器类源码解析》系列的第三篇文章,主要是对HashMap的源码实现进行分析。强烈建议阅读本文之前,先看看该系列...

MRYangY
04/21
0
0
面试高频问题:HashMap实现原理

今天给同学们讲讲一个面试经常遇到的高频问题,HashMap实现原理,希望在金三银四的季节对同学们有帮助。 HashMap结构图目录 一、唠叨 二、解析思路 三、get方法 四、put方法 五、resize方法 ...

骚年锦时
05/27
25
0
Java集合 --- HashSet底层实现和原理(源码解析)

概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会进行说明。 HashSet是Set接口...

起个名忒难
2017/08/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

浅谈prototype原型模式

一、原型模式简介 原型(Prototype)模式是一种对象创建型模式,他采取复制原型对象的方法来创建对象的实例。使用原型模式创建的实例,具有与原型一样的数据。 原型模式的特点: 1、由原型对...

青衣霓裳
6分钟前
1
0
shell mysql 备份

#!/bin/bash time2=$(date "+%Y-%m-%d-%H:%M:%S") /usr/local/mysql/bin/mysqldump -uroot -p ad > /usr/local/mysql/backup/"$time2".sql 变量引用原来是这么用的。......

奋斗的小牛
14分钟前
2
0
Jmeter监控Linux服务器操作

系统:Win7 64位 工具:Jmeter 4.0 要准备好的插件:JMeterPlugins-Standard-1.4.0,ServerAgent-2.2.1 解压JMeterPlugins-Standard-1.4.0.zip,将其中\lib\ext\JMeterPlugins-Standard.jar......

魔鬼妹子
14分钟前
3
0
系列文章:云原生Kubernetes日志落地方案

在Logging这块做了几年,最近1年来越来越多的同学来咨询如何为Kubernetes构建一个日志系统或者是来求助在这过程中遇到一系列问题如何解决,授人以鱼不如授人以渔,于是想把我们这些年积累的经...

Mr_zebra
15分钟前
2
0
入门必备!快速学会用Aspose.Words在表格中插入和删除列!

Aspose.Words For .Net(点击下载)是一种高级Word文档处理API,用于执行各种文档管理和操作任务。API支持生成,修改,转换,呈现和打印文档,而无需在跨平台应用程序中直接使用Microsoft W...

mnrssj
20分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部