文档章节

hashmap和hash算法研究

令飞
 令飞
发布于 2015/04/17 17:53
字数 1310
阅读 954
收藏 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源码学习笔记

数组虽然可以随机访问,但插入和删除效率较低,链表虽然插入和删除效率较高,查找却只能通过遍历,而HashMap则基于数组加链表,完美结合了二者的优点,查找,更新,插入,删除几乎都可以达到O...

单线程程序员
2018/12/07
0
0
Java中对HashMap的深度分析与比较

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

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

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

唐玄奘
2017/12/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

解决各浏览器向url中传中问参数的问题

https://www.cnblogs.com/godtrue/p/4333262.html 后台的处理代码 public static String getUrlnewName( String oldName) {String newName = "";try {String agent = inv.get......

踏破铁鞋无觅处
11分钟前
1
0
微信支付携带证书请求

package utils.wechat; import java.io.File;import java.io.FileInputStream;import java.io.IOException;import java.security.KeyStore; import javax.net.ssl.SSLContext;......

猿神出窍
19分钟前
1
0
1093 - You can't specify target table 'xxx' for update in FROM clause, Time: 0.002000s

1093 - You can't specify target table 'xxx' for update in FROM clause, Time: 0.002000s 根据结果集在b_order_copy1 表中删除 DELETE FROM b_order_copy1 WHERE Id in ( SELECT Id FRO......

lwenhao
19分钟前
1
0
JavaScriptCore全面解析

本文由云+社区发表 作者:殷源,专注移动客户端开发,微软Imagine Cup中国区特等奖获得者 JavaScript越来越多地出现在我们客户端开发的视野中,从ReactNative到JSpatch,JavaScript与客户端相...

腾讯云加社区
23分钟前
1
0
Jmeter参数的AES加密使用

在Jmeter日常实践中,大家应该都遇到过接口传参需要加密的情况。以登陆为例,用户名和密码一般都需要进行加密传输,在服务端再进行解密,这样安全系数会更高,但在使用jmeter进行接口测试的时...

程序猿拿Q
34分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部