1、散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式,链表是单向链表,因此在删除过程中要自己维持prev节点,我想不采用双向链表是从节省空间考虑。一个典型的查找过程:
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
HashMap采用链表法而不是开放地址法,猜想可能的原因是从实用角度出发,对空间和时间效率做出的折中选择。采用开放地址法,无论是线性探测或者二次探测都可能造成群集现象,而双重散列会要求散列表的装填程度比较低的情况下会有比较好的查找效率,容易造成空间的浪费。
2、什么是负载因子?负载因子a定义为
a=散列表的实际元素数目(n)/ 散列表的容量(m)
负载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均次数是 (1+a)次,因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。
回到HashMap的实现,HashMap中的loadFactor其实定义的就是该map对象允许的最大的负载因子,如果超过这个系数将重新resize。这个是通过threshold字段来判断,看threshold的计算:
threshold = (int)(capacity * loadFactor);
结合上面的负载因子的定义公式可知,threshold就是在此loadFactor和capacity对应下允许的最大元素数目,超过这个数目就重新resize,以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。注意到的一点是resize的规模是现有 capacity的两倍:
if (size++ >= threshold)
resize(2 * table.length);
3、可能你也注意到了,java.util.HashMap对key的hash值多做了一步处理,而不是直接使用hashCode:
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
这个处理的原因在于HashMap的容量总是采用2的p次幂,而取index(槽位)的方法是
static int indexFor(int h, int length) {
return h & (length-1);
}
这一运算等价于对length取模,也就是
h % 2^p
返回的将是h的p个最低位组成的数字,我们假设hash输入是符合简单一致散列,然而这一假设并不能推论出hash的p个最低位也会符合简单一致散列,也许h的这p个最低位相同的几率很大,那么冲突的几率就非常大了。优秀的散列函数应该需要考虑所有的位。
因此为了防止这些“坏”的散列函数造成效率的降低,HashMap预先对hash值做了处理以考虑到所有的位,根据注释也可以知道。这个处理我看不懂,留待高人解释,也许来自于某本算法书也不一定。
4、我们知道java.util.HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略(速错),这一策略在源码中的实现是通过 modCount域,modCount顾名思义就是修改次数,对HashMap内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount,
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了map
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
注意到modCount声明为volatile,保证线程之间修改的可见性。
分享到:
相关推荐
1.面试必考之HashMap源码分析与实现 伸缩性角度看HashMap的不足
HashMap源码分析系列-第四弹:HashMap多线程解决方案.docx
面试必考之HashMap源码分析与实现....................................................................
首先,我们了解一下HashMap的底层结构历史,在JDK1.8之前采用的是数组+链表的数据结构来存储数据,是不是觉得很熟悉,没错这玩意在1.8之前的结构就和HashTable一样都是采用数组+链表,同样也是通过链地址法(这里简称...
hashmap的原理啊思想。
微信小程序详细图文教程 泉州大白网络科技 目录 一.微信小程序申请 二....1.申请服务器 2.部署服务器 3.域名申请和配置 三....一....申请,并认证(未认证不能发布,认证需要300元,目前只支持企业认证)详细见官网说明。...
hashmap的底层及源码解析,很适合大家的学习,不要积分。
JAVA之hashmap源码分析 Mobile-Dev-Analysis Analysis of android or java 红岩网校工作站移动开发部学员分组学习 为了让大家学的更加坚固,采取小组学习的方式帮助大家学习,同时在学习研究的过程中需要不断的做...
HashMap数据结构,HashMap的构造方法,HashMap的put,HashMap的get
JAVA之hashmap源码分析 无头Android堆分析器 “哈哈!” -纳尔逊 此存储库已弃用 创建该项目的目的是通过重新打包其他存储库中的堆转储解析器来提供堆转储解析器。 LeakCanary现在有它自己的。 该解析器在Maven ...
JAVA之hashmap源码分析Superword是Java开源项目,致力于研究英语单词分析和辅助阅读,包括但不限于拼写相似度,定义相似度,发音相似度,拼写转换规则,前缀和动态前缀,后缀以及动态后缀,词根,复合词,文本辅助...
主要为大家详细介绍了Java集合系列之HashMap源码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
面试必考之HashMap源码分析与实现 ,微服务架构之Spring Cloud Eureka 场景分析与实战,高性能必学之Mysql主从架构实践 ,架构师不得不知道的Spring事物不能回滚的深层次原因 ,分库分表之后分布式下如何保证ID全局...
Java开发工程师必看面试必备知识技能总结视频合集,视频讲解知识内容包括:HashMap源码分析与实现、JVM底层奥秘ClassLoader源码分析与案例讲解、大型网站数据库瓶颈之数据库分库分表方案实践、Spring Cloud Eureka...
博客地址 http://blog.csdn.net/sbsujjbcy/article/details/47396659
HashMap 1.7源码分析HashMap 1.7源码分析HashMap 1.7源码分析HashMap 1.7源码分析HashMap 1.7源码分析
java学习笔记,包括JVM,并发,JDK一些工具的源码,spring,hashMap实现源码分析