文档章节

hashmap和hash算法研究

令飞
 令飞
发布于 2015/04/17 17:53
字数 1310
阅读 946
收藏 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。

 

© 著作权归作者所有

共有 人打赏支持
令飞
粉丝 47
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

MySQL面试题集锦

什么是数据库索引?索引有哪几种类型?什么是最左前缀原则?索引算法有哪些?有什么区别? 索引是对数据库表中一列或多列的值进行排序的一种结构。一个非常恰当的比喻就是书的目录页与书的正...

老道士
15分钟前
0
0
使用 LogStash 归集日志

elastic 官网: https://www.elastic.co/ 为了便于集中查看多台主机的业务日志,使用 Filebeat, Redis, Logstash的方式进行收集: (1) Filebeat 监控日志文件的变化, 将新增部分写入redis中, 每...

ouhoo
18分钟前
0
0
java序列化(六) - protostuff序列化

添加依赖 <dependency> <groupId>io.protostuff</groupId> <artifactId>protostuff-core</artifactId> <version>1.5.9</version> </de......

晨猫
25分钟前
0
0
Ceph学习笔记1-Mimic版本多节点部署

特别说明: 本方法也可以用于单节点部署,只部署一个Monitor(只是会形成单点故障而已),最低要求是使用两个分区创建2个OSD(因为默认最小副本是2);如果不需要使用CephFS,则可以不部署M...

LastRitter
27分钟前
0
0
923. 3Sum With Multiplicity - LeetCode

Question 923. 3Sum With Multiplicity Solution 题目大意: 给一个int数组A和一个目标值target,求满足下面两个条件的组合个数,其中i,j,k分别为数组的索引 i<j<k target = A[i] + A[j] + A[k...

yysue
29分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部