文档章节

hashmap和hash算法研究

令飞
 令飞
发布于 2015/04/17 17:53
字数 1310
阅读 933
收藏 23

  总述

  hashmap作为java中非常重要的数据结构,对于key-value类型的存储(缓存,临时映射表,。。。)等不可或缺,hashmap本身是非线程安全的,对于多线程条件下需要做竞争条件处理,可以通过Collections和ConcurrentHashmap来替代。

  Hashmap源码探究

  数据结构

  hashmap存储数据主要是通过数组+链表实现的,通过将key的hashcode映射到数组的不同元素(桶,hash中的叫法),然后冲突的元素放入链表中。

  

  链表结构(Entry)

  

  采用静态内部类

  存储操作

  

  当存入的值为null的时候,操作会找到table[0],set key为null的值为新值

  若果不是空值,则进行hash,

  hash算法

  

  可以看到,算法进行了二次hash,使高位也参与到计算中,防止低位不变造成的hash冲突

  注:这一切的目的实际上都是为了使value尽量分布到不同的

  对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash(int h) 方法所计算得到的 hash 码值总是相同的。我们首先想到的就是把 hash 值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,在 HashMap 中是这样做的:调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下:

  

  这又要牵扯到hashmap的另外一个问题,关于length长度的定义

  在put操作的开始,有判断table是否为空,如果为空则会初始化table,初始化的代码如下:

  

private void inflateTable(int toSize) {
  // Find a power of 2 >= toSize
  int capacity = roundUpToPowerOf2(toSize);
  threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  table = new Entry[capacity];
  initHashSeedAsNeeded(capacity);
}

  容量的提升都是以2的幂的方式

  这段代码保证初始化时 HashMap 的容量总是 2 的 n 次方,即底层数组的长度总是为 2的 n 次方。当 length 总是 2 的 n 次方时,h& (length-1)运算等价于对 length 取模,也就是h%length,但是&比%具有更高的效率。

  这看上去很简单,其实比较有玄机的,我们举个例子来说明:

  假设数组长度分别为 15 和 16,优化后的 hash 码分别为 8 和 9,那么&运算后的结果如下:

  

  读操作:

  

  读操作通过hash后的值,一样是调用indexFor方法找到对应的序号,然后遍历链表找到对应的value返回

  resize操作

  resize只有在hashmap中元素的大小达到临界值的时候才会进行,而临界值和loadFactor 参数有关,只有数量达到loadFactor *table.length才会重新分配table,元素也将重新映射,这是非常耗性能的操作,所以最好一开始能确定元素的大概范围

  HashMap 的性能参数(这段直接从参考文章引来):

  HashMap 包含如下几个构造器:

  HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。

  HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子

  为 0.75 的 HashMap。

  HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。HashMap 的基础构造器 HashMap(int initialCapacity, float loadFactor)带有两个参数,它们是初始容量 initialCapacity 和加载因子 loadFactor。

  initialCapacity:HashMap 的最大容量,即为底层数组的长度。

  loadFactor:负载因子 loadFactor 定义为:散列表的实际元素数目(n)/ 散列表的容量(m)。负载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是 O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。

  HashMap 的实现中,通过 threshold 字段来判断 HashMap 的最大容量:

  Java 代码

 
  threshold = (int)(capacity * loadFactor);

  结合负载因子的定义公式可知, threshold 就是在此 loadFactor 和 capacity 对应下允许的最大元素数目,超过这个数目就重新 resize,以降低实际的负载因子。默认的的负载因子0.75 是对空间和时间效率的一个平衡选择。当容量超出此最大容量时,  resize 后的 HashMap容量是容量的两倍:

  if (size++ >= threshold)

  resize(2 * table.length);

  快速失败

  我们知道 java.util.HashMap 不是线程安全的,因此如果在使用迭代器的过程中有其他

  线程修改了 map,那么将抛出 ConcurrentModificationException,这就是所谓 fail-fast 策略。

  这一策略在源码中的实现是通过 modCount 域, modCount 顾名思义就是修改次数,对HashMap 内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。

 

© 著作权归作者所有

共有 人打赏支持
令飞
粉丝 46
博文 21
码字总数 14127
作品 0
杭州
程序员
加载中

评论(1)

karen368
karen368
很详细
Java7 HashMap全面解读!

曾几何时,自己开始研究jdk源码,许久之后又记忆模糊,所以还是决定写个博客记录一下学习过程。为什么标题要写着java7呢?因为J8的Hashmap改动不小,所以先从自己稍微熟悉点的J7源码开始,废...

写PHP的JAVA猿
2016/09/27
1K
3
hashmap和hash算法研究

总述   hashmap作为java中非常重要的数据结构,对于key-value类型的存储(缓存,临时映射表,。。。)等不可或缺,hashmap本身是非线程安全的,对于多线程条件下需要做竞争条件处理,可以通...

浮躁的码农
2015/04/17
0
0
Java HashMap 分析之一:基本结构

Java的HashMap非常的常用,本篇研究它的实现算法,最后希望计算出内存占用,性能的量化数据,然后得出什么时候使用HashMap,什么时候不能滥用的结论。 HashMap实际上是一个数组,数组里面的每...

长平狐
2012/08/28
159
0
Java中对HashMap的深度分析与比较

HashMap可谓JDK的一大实用工具,把各个Object映射起来,实现了“键--值”对应的快速存取。但实际里面做了些什么呢? 在这之前,先介绍一下负载因子和容量的属性。大家都知道其实一个 Hash...

青夜之衫
2017/12/08
0
0
Java中对HashMap的深度分析与比较(转载初学者笔记)

HashMap可谓JDK的一大实用工具,把各个Object映射起来,实现了“键--值”对应的快速存取。但实际里面做了些什么呢? 在这之前,先介绍一下负载因子和容量的属性。大家都知道其实一个 Hash...

唐玄奘
2017/12/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

配置Spring的注解支持

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 配置Spring的注解支持 以上也提到了使用注解来配...

凯哥学堂
34分钟前
0
0
关于Spring Aop存在的一点问题的思考

在本人前面的文章Spring Aop原理之切点表达式解析中讲解了Spring是如何解析切点表达式的,在分析源码的时候,出现了如下将要讲述的问题,我认为是不合理的,后来本人单纯使用aspectj进行试验...

爱宝贝丶
36分钟前
0
0
JavaScript 概述

JavaScript是面向Web的编程语言。绝大多数现代网站都使用了JavaScript,并且所有的现代Web浏览器——基于桌面系统、游戏机、平板电脑和智能手机的浏览器——均包含了JavaScript解释器。这使得...

Mr_ET
今天
0
0
Java Run-Time Data Areas(Java运行时数据区/内存分配)

Java运行时数据区(内存分配) 本文转载官网 更多相关内容可查看官网 中文翻译可参考 2.5. Run-Time Data Areas The Java Virtual Machine defines various run-time data areas that are use...

lichuangnk
今天
0
0
docker learn :services docker-compose.yml

docker-compose.yml定义了服务的运行参数 version: "3" services: web: # replace username/repo:tag with your name and image details image: hub.c.163.com/dog948453219/friendlyhello d......

writeademo
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部