ConcurrentHashMap和HashTable区别?(超详细解释)
为了完整理解这个问题,我们的学习顺序为:
1、什么是哈希表
2、HashMap为什么效率高于Hashtable?
3、HashMap和Hashtable的区别
4、ConcurrentHashMap和HashTable区别?(重点!)
5、面试总结(重点!)
一、什么是哈希表
01、基本概念
重点关注:槽位、哈希碰撞
哈希表或者散列表
给定表M,若存在函数h(key),使得对任意给定的关键字值key,代入函数后能得到包含该key的记录,这个记录指的是:在表中的地址,则称表M为哈希表或者散列表。函数h(key)为哈希函数或者散列函数。
哈希函数的好坏会直接影响哈希表的优劣。
槽位(slot)或者桶(bucket)
散列表是由哈希函数和数组共同构建的一种数据结构,元素由键和值组成。散列表中的一个位置称为槽位(slot)或者桶(bucket),用于保存键值对。
哈希碰撞(hash collision)
由哈希函数映射的数组下标(称为散列地址-桶号),决定了给定的键存于散列表的哪个桶中。如果不同的key映射到了相同的数组下标,则发生了哈希碰撞(hash collision)。
数组中的元素的数据结构可以是一个链表或者一棵红黑树,链表或者红黑树就是用来解决哈希碰撞的!
- 在Java1.7阶段,是不存在树的,即挂载到数组同一个位置的多个元素,通过next属性,构成了一个单向链表
-
- 数组中每一个元素是一个Node,有四个属性:
-
-
- hash:当前位置值的hash值
- key:当前位置的键
- value:当前位置存储的值
- next:下一个Node
-
- 在Java1.8中,当单向链表中的元素大于等于8时,单项链表会变成一棵树,该树为红黑树,而又当数量小于6时,则又转化为链表存储。该转换操作是由final void treeifyBin(Node<K,V>[] tab,int hash)函数实现的。
哈希表的容量
散列表所拥有的桶数被称为散列表的容量(capacity)
02、哈希表示例
我们要在哈希表中执行插入操作:
图中,0-5标记部分即代表哈希表,令关键字 key=kobe,则通过哈希函数f(key)得到其槽位为1,故把 kobe 放在数组下标为1的桶中。
如果不同的 key 映射到了同一数组下标,就将其放入对应数组下标的单链表中。
Java 的集合中给出了底层结构采用哈希表数据结构的实现类,按照时间顺序分别为第一代Hashtable、第二代 HashMap和第三代 ConcurrentHashMap。它们的相同点:底层结构都是哈希表,都是用来存储 key-value 映射,都实现了 Map 接口。
HashTable已经不建议使用了,因为有一种效率高一些,同时又线程安全的Map:ConcurrentHashMap!
二、HashMap为啥比Hashtable效率高?
01、HashTable有锁机制
HashTable线程安全,有锁机制
1、HashTable线程安全的策略实现代价太大了,简单粗暴。get/put所有相关操作都是synchronized的,这相当于个整个Hash表加了一把大锁。
2、当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程使用 put 添加元素,或者使用 get,会导致程序出现问题,相当于所有的操作串行化,竞争会越来越激烈效率越低。
package hashMapAndConcurrentHashMap;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.concurrent.ConcurrentHashMap;
public class test1 {
public static void main(String[] args) {
HashMap<Object, Object> hashMap = new HashMap<>();
// ConcurrentHashMap<Object, Object> hashMap = new ConcurrentHashMap<>();
// Hashtable<Object, Object> hashMap = new Hashtable<>();
new Thread(() -> {
for (int i = 1; i < 500000; i++) {
hashMap.put(new Integer(i),i);
}
System.out.println("t1 over");
}).start();
new Thread(() -> {
for (int i = 500001; i < 1000000; i++) {
hashMap.put(new Integer(i),i);
}
System.out.println("t2 over");
}).start();
new Thread(() -> {
for (int i = 500001; i < 1000000; i++) {
hashMap.put(new Integer(i),i);
}
System.out.println("t3 over");
}).start();
new Thread(() -> {
for (int i = 500001; i < 1000000; i++) {
hashMap.put(new Integer(i),i);
}
System.out.println("t4 over");
}).start();
new Thread(() -> {
for (int i = 0; i < 5000000; i++) {
Object o = hashMap.get(i);
System.out.println(o+":::hashtable111");
}
}).start();
}
}
可以发现,当使用HashMap的时候,可能会出现,get和put冲突!而Hashtable和ConcurrentHashMap由于锁的机制,所以不会冲突。
02、HashTable底层算法效率低
从两个方向说明这个观点
02-01、获取hash方式
其实就是获取槽位的方式
HashTable使用取模的方式获取槽位,HashMap使用位运行获取槽位
public synchronized V put(K key, V value) {
// 注意value不能为空值(HashMap的value可以放空值)
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 查找元素是否已经在table中,存在就返回原entry的value
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 不存在就去添加
addEntry(hash, key, value, index);
return null;
}
(hash & 0x7FFFFFFF) % tab.length,可以看出Hashtable也是通过取余方式确定key所在的槽,由于Hashtable数组长度不是2的N次幂所以只能使用%方式取余,并且Hashtable也没有使用扰动函数混合键hashCode高低位。addEntry 方法如下
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// 如果超过阈值,则重新刷新表
rehash();
tab = table;
// 通过key的hashcode计算位置
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// 创建新的entry并插入
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
HashTable遇到hash碰撞时使用链表解决,并没有红黑树
02-02、槽位冲突
HashTable使用链表数据结构来存储槽位相同的数据,HashMap同样也使用链表但在数据量多的情况下会升级成红黑树数据结构
- 因为链表的查找时间复杂度为O(N),而红黑树查找的时间复杂度为O(logN)
- 红黑树时间复杂度低
有了上面的基础知识,我们再来对比HashMap和Hashtable的区别!
三、HashMap和Hashtable的区别
首先需要了解两个前提:
HashMap、Hashtable其实都是一个可以扩容的动态数组。
HashMap和Hashtable的底层实现都是数组+链表结构实现
01、线程安全
两者最主要的区别在于Hashtable是 线程安全,而HashMap则非线程安全
Hashtable的实现方法里面都添加了synchronized关键字来确保 线程同步
我们平时使用时若无特殊需求建议使用HashMap,因为HahsMap效率高于Hashtable!
那么如何解决HashMap线程不安全的弊端呢?
在多线程环境下若使用HashMap,需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。
Map<Object, Object> synchronizedMap = Collections.synchronizedMap(new HashMap<>());
synchronizedMap.put("ceshi","111");
Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类,这个类实现了Map接口,在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例
简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步,类似的其它Collections.synchronizedXX方法也是类似原理
02、key是否允许为null
HashMap可以使用null作为key,而Hashtable则不允许null作为key
虽说HashMap支持null值作为key,不过建议还是尽量避免这样使用,因为一旦不小心使用了,若因此引发一些问题,排查起来很是费事
HashMap以null作为key时,总是存储在table数组的第一个节点上
03、实现的接口不同
HashMap是对Map接口的实现,HashTable实现了Map接口和Dictionary抽象类
04、初始容量不同
HashMap的初始容量为16,Hashtable初始容量为11,两者的填充因子默认都是0.75
HashMap扩容时是当前容量翻倍即:capacity2,Hashtable扩容时是容量翻倍+1即:capacity2+1
05、包含的contains方法不同
HashMap是没有contains方法的,而包括containsValue和containsKey方法;
hashtable则保留了contains方法,效果同containsValue,还包括containsValue和containsKey方法。
contains方法是查询当前集合中是否存在某个值,而不是某个键哦!
package com.zhangfushuai;
import java.util.*;
public class Demo {
public static void main(String[] args) {
Hashtable hashtable = new Hashtable();
hashtable.put("11","z");
hashtable.put("11","h"); //重复添加会覆盖
hashtable.put("12","h");
hashtable.put("13","x");
hashtable.put("13","x");
String s = hashtable.toString();
System.out.println(s); //打印Hashtable集合
boolean contains1 = hashtable.contains("z");
System.out.println(contains1);//查询哈希表中,键相同,值不相同的node的时候,会返回false
boolean contains2 = hashtable.contains("h");
System.out.println(contains2);//查询哈希表中,键不相同,值相同的node的时候,true
boolean x = hashtable.contains("x");
System.out.println(x);//查询哈希表中,键相同,值相同的node的时候,true
}
}
06、两者计算 hash的方法不同
这个其实就是获取槽位的方式不同,上文已经提到过了
为了得到元素的位置,首先需要根据元素的 KEY计算出一个hash值,然后再用这个hash值来计算得到最终的位置。
①:HashMap有个hash方法重新计算了key的hash值,因为hash冲突变高,所以通过一种方法重算hash值的方法:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
index = (n - 1) & hash
注意这里计算hash值的时候,先调用hashCode方法计算出来一个hash值,再将hash与右移16位后相异或,即取摸之后,从而得到新的hash值。
②:Hashtable通过计算key的hashCode()来得到hash值
int index = (hash & 0x7FFFFFFF) % tab.length;
& 0x7FFFFFFF的目的是为了将负的hash值转化为正值,因为hash值有可能为负数,而& 0x7FFFFFFF后,只有符号位改变,而后面的位都不变。
总结 - 分析利弊
取模时,不需要做除法,只需要做位运算。在计算机中,位运算比除法的效率要高很多。
四、扩展 - HashSet
除了HashMap和Hashtable外,还有一个hash集合HashSet!
有所区别的是HashSet不是key-value结构,而仅仅存储了不重复的元素,相当于简化版的HashMap,只是包含HashMap中的key,而不包含value而已。
通过查看源码也证实了这一点,HashSet内部就是使用HashMap实现,只不过HashSet里面的HashMap所有的value都是同一个Object而已
HashSet底层使用HashMap来保存所有元素,因此HashSet的实现比较简单,相关HashSet的操作,基本上都是直接调用底层 HashMap 的相关方法来完成,HashSet 不允许重复的值
因此HashSet也是非线程安全的,至于HashSet和Hashtable的区别,HashSet就是个简化的HashMap的,和Hashtable和HashMap的区别一样,不再赘述了!
五、ConcurrentHashMap与HashTable的区别
有了以上基础之后,我们开始学习:ConcurrentHashMap与HashTable的区别!
一句话:ConcurrentHashMap融合了hashtable和hashmap二者的优势。
集合诞生的先后顺序:HashTable-----HashMap-----ConcurrentHashMap
一个技术的出现,肯定是为了解决某个方案才诞生的,上文已经了解过,HashTable线程安全,但是效率慢,HashMap线程不安全,但是效率高,那么ConcurrentHashMap正是为了解决这个问题而诞生的。
JDK1.7的ConcurrentHashMap 底层和HashMap一样,仍然采用:分段的数组+链表 实现
JDK1.8的ConcurrentHashMap 底层和HashMap一样,仍然采用:数组+链表/红黑二叉树。
ConcurrentHashMap解决了HashMap的线程不安全的问题,让HashMap线程安全了,HashTable也是线程安全的,所以转换一下思路
ConcurrentHashMap与HashTable的区别!其实就是在问:ConcurrentHashMap与HashTable在实现线程安全的实现方式上有什么区别?
01、实现线程安全的方式
ConcurrentHashMap
在 JDK1.7 的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),相较于Hashtable的锁,更加的细粒度了,ConcurrentHashMap将hash表分为16个桶(默认值),诸如get、put、remove等常用操作只锁住当前需要用到的桶。
每一把锁只锁容器的其中一部分数据,这个时候当多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。试想,原来 只能一个线程进入,现在却能同时16个写线程进入,并发性的提升是显而易见的
ConcurrentHashMap在读取的大多数时候都没有用到锁定,所以读取操作几乎是完全的并发操作,而写操作锁定的粒度又非常细,比起之前又更加快速(这一点在桶更多时表现得更明显些)。只有在求size等操作时才需要锁定整个表。
到了JDK1.8 的时候已经摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6 以后 对 synchronized 锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;
HashTable
Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。
02、两者的对比图
首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁,扮演锁的角色。HashEntry 用于存储键值对数据。
static class Segment<K,V> extends ReentrantLock implements Serializable {
}
一个 ConcurrentHashMap里包含一个 Segment 数组。Segment的结构和 HashMap 类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个 HashEntry 数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 的锁。
JDK1.8 的 ConcurrentHashMap 不再是 Segment 数组 + HashEntry 数组 + 链表,而是 Node 数组 + 链表 / 红黑树。不过,Node 只能用于链表的情况,红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时,链表会转换成红黑树。
ConcurrentHashMap 取消了 Segment 分段锁,采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似,数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值(8)时将链表(寻址时间复杂度为 O(N))转换为红黑树(寻址时间复杂度为 O(log(N)))
synchronized 只锁定当前链表或红黑二叉树的首节点,这样只要 hash 不冲突,就不会产生并发,效率又提升 N 倍。
✨现在回答一下这个面试问题:
ConcurrentHashMap和HashTable区别?
ConcurrentHashMap:锁定map的一部分
遍历集合时候安全失败,在原有集合上拷贝一份,不会出现并发修改异常
HashTable : 锁定整个map
遍历集合快速失败,会出现并发修改异常
并发修改异常:集合在迭代时候,对集合进行修改,则会出现的异常
安皮卡: 大佬分享一下源码
m0_64812693: 讲的真的太好了
爱学习it小白白: 递归、搜索与回溯】综合练习二
鲸慕: 我想看看参考文献
鲸慕: 有文档没