大家一看到这两个类就能想到HashMap不是线程安全的,ConcurrentHashMap是线程安全的。除了这些,还知道什么呢?
先看一下简单的类图:
从类图中可以看出来在存储结构中ConcurrentHashMap比HashMap多出了一个类Segment,而Segment是一个可重入锁。
ConcurrentHashMap是使用了锁分段技术技术来保证线程安全的。
锁分段技术:首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。
属性说明:
我们会发现HashMap和Segment里的属性值基本是一样的,因为Segment的本质上就是一个加锁的HashMap,下面是每个属性的意义:
table:数据存储区
size,count: 已存数据的大小
threshold:table需要扩容的临界值,等于table的大小*loadFactor
loadFactor: 装载因子
modCount: table结构别修改的次数
hash算法和table数组长度:
仔细阅读HashMap的构造方法的话,会发现他做了一个操作保证table数组的大小是2的n次方。
如果使用new HashMap(10)新建一个HashMap,你会发现这个HashMap中table数组实际的大小是16,并不是10.
为什么要这么做呢?这就要从HashMap里的hash和indexFor方法开始说了。
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
HashMap里的put和get方法都使用了这两个方法将key散列到table数组上去。
indexFor方法是通过hash值和table数组的长度-1进行于操作,来确定具体的位置。
为什么要减1呢?因为数组的长度是2的n次方,减1以后就变成低位的二进制码都是1,和hash值做与运算的话,就能得到一个小于数组长度的数了。
那为什么对hashCode还要做一次hash操作呢?因为如果不做hash操作的话,只有低位的值参与了hash的运算,而高位的值没有参加运算。hash方法是让高位的数字也参加hash运算。
假如:数组的长度是16 我们会发现hashcode为5和53的散列到同一个位置.
hashcode:53 00000000 00000000 00000000 00110101
hashcode:5 00000000 00000000 00000000 00000101
length-1:15 00000000 00000000 00000000 00001111
只要hashcode值的最后4位是一样的,那么他们就会散列到同一个位置。
hash方法是通过一些位运算符,让高位的数值也尽可能的参加到运算中,让它尽可能的散列到table数组上,减少hash冲突。
ConcurrentHashMap的初始化:
仔细阅读ConcurrentHashMap的构造方法的话,会发现是由initialCapacity,loadFactor, concurrencyLevel几个参数来初始化segments数组的。
segmentShift和segmentMask是在定位segment时的哈希算法里需要使用的,让其能够尽可能的散列开。
initialCapacity:ConcurrentHashMap的初始大小
loadFactor:装载因子
concurrencyLevel:预想的并发级别,为了能够更好的hash,也保证了concurrencyLevel的值是2的n次方
segements数组的大小为concurrencyLevel,每个Segement内table的大小为initialCapacity/ concurrencyLevel
ConcurrentHashMap的put和get
int hash = hash(key.hashCode());
return segmentFor(hash).get(key, hash);
可以发现ConcurrentHashMap通过一次hash,两次定位来找到具体的值的。
先通过segmentFor方法定位到具体的Segment,再在Segment内部定位到具体的HashEntry,而第二次在Segment内部定位的时候是加锁的。
ConcurrentHashMap的hash算法比HashMap的hash算法更复杂,应该是想让他能够更好的散列到数组上,减少hash冲突。
HashMap和Segment里modCount的区别:
modCount都是记录table结构被修改的次数,但是对这个次数的处理上,HashMap和Segment是不一样的。
HashMap在遍历数据的时候,会判断modCount是否被修改了,如果被修改的话会抛出ConcurrentModificationException异常。
Segment的modCount在ConcurrentHashMap的containsValue、isEmpty、size方法中用到,ConcurrentHashMap先在不加锁的情况下去做这些计算,如果发现有Segment的modCount被修改了,会再重新获取锁计算。
HashMap和ConcurrentHashMap的区别:
如果仔细阅读他们的源码,就会发现HashMap是允许插入key和value是null的数据的,而ConcurrentHashMap是不允许key和value是null的。这个是为什么呢?ConcurrentHashMap的作者是这么说的:
The main reason that nulls aren't allowed in ConcurrentMaps (ConcurrentHashMaps, ConcurrentSkipListMaps) is that ambiguities that may be just barely tolerable in non-concurrent maps can't be accommodated. The main one is that if map.get(key) returns null, you can't detect whether the key explicitly maps to null vs the key isn't mapped. In a non-concurrent map, you can check this via map.contains(key), but in a concurrent one, the map might have changed between calls.
为什么重写了equals方法就必须重写hashCode方法呢?
绝大多数人都知道如果要把一个对象当作key使用的话,就需要重写equals方法。重写了equals方法的话,就必须重写hashCode方法,否则会出现不正确的结果。那么为什么不重写hashCode方法就会出现不正确结果了呢?这个问题只要仔细阅读一下HashMap的put方法,看看它是如何确定一个key是否已存在的就明白了。关键代码:
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
首先通过key的hashCode来确定具体散列到table的位置,如果这个位置已经有值的话,再通过equals方法判断key是否相等。
如果只重写equals方法而不重写hashCode方法的话,即使这两个对象通过equals方法判断是相等的,但是因为没有重写hashCode方法,他们的hashCode是不一样的,这样就会被散列到不同的位置去,变成错误的结果了。所以hashCode和equals方法必须一起重写。
- 大小: 80.7 KB
分享到:
相关推荐
java7-8中的 HashMap和ConcurrentHashMap全解析
java7-8中的 HashMap和ConcurrentHashMap全解析 如果你想了解底层的逻辑就来看看吧
HashMap& ConcurrentHashMap 深度解析
涵盖绝大部分HashMap与ConcurrentHashMap的面试题 附带答案
下面小编就为大家带来一篇详谈HashMap和ConcurrentHashMap的区别(HashMap的底层源码)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
源码分析见我博文:http://blog.csdn.net/wabiaozia/article/details/50684556
本文详述Java语言中的hashmap与concurrenthashmap,使用其他语言的朋友可做参考 首先我们先来看一下这几个类原码开头的部分 public class HashMap extends AbstractMap implements Map, Cloneable, Serializable ...
1.说一下 HashMap 的实现原理? 2.HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现? 3.HashMap的put方法的具体流程...17.HashMap 和 ConcurrentHashMap 的区别? 18.ConcurrentHashMap 和 Hashtable 的区别?
HashMap,HashTable,ConcurrentHashMap之关联.docx
HashMap、ConcurrentHashMap源码级解读,并且对比了JDK7和8实现的不同,进行了大量的解释,结合了多个学习视频
hashmap和hashtable的区别 HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有:线程安全性,同步(synchronization),以及速度。 1. HashMap几乎可以等价于Hashtable,...
朋友准备3个月以上的的真实面试分享,绝对值; ... 3> HashMap和ConcurrentHashMap的区别,以及两者的优缺点。。。。。。。。 。。。。。。。。。。。。。。。。。。。。。。。。。(详见完整版)
Java利用ConcurrentHashMap实现本地缓存demo; 基本功能有缓存有效期、缓存最大数、缓存存入记录、清理线程、过期算法删除缓存、LRU算法删除、获取缓存值等功能。 复制到本地项目的时候,记得改包路径哦~
比较Java原生的 3种Map的效率。 1. TreeMap 2. HashMap 3. ConcurrentSkipListMap 本测试查找方法使用Map的get方法,循环、离散获取。... SkipListMap的范围查询效率比HashMap和TreeMap效率都要高。
本篇主要想讨论ConcurrentHashMap这样一个并发容器,在正式开始之前我觉得有必要谈谈HashMap,没有它就不会有后面的ConcurrentHashMap。众所周知HashMap底层是基于数组+链表组成的,不过在jdk1.7和1.8中具体实现稍有...
上图中,每个绿色的实体是嵌套类 Entry 的实例,Entry 包含四个属性:key, value, hash 值和用于单向链表的capacity:当前数组容量
HashMap总结、面试资料!!(2020下半年) 包含:HashMap线程安全 + ConcurrentHashMap + HashMap + 源码分析 + jdk1.8的HashMap和ConcurrentHashMap。 欢迎下载学习
java多线程文档,锁,并发锁,hashmap,concurrenthashmap
本文将结合Java内存模型,分析JDK源代码,探索ConcurrentHashMap高并发的具体实现机制,包括其在JDK中的定义和结构、并发存取、重哈希和跨段操作,并着重剖析了ConcurrentHashMap读操作不需要加锁和分段锁机制的内在...
ConcurrentHashMap源码剖析