大家好,今天为大家带来新的知识, HashTable, HashMap, ConcurrentHashMap 之间的区别
目录:
????1.回忆hashmap
???? 2.比较HashTable,ConcurrentHashMap
????3.总结HashTable, ConcurrentHashMap的区别
????4.一个历史小问题
????5.总结HashTable, HashMap, ConcurrentHashMap 之间的区别
1.回忆hashmap
我们之前学过了Hashmap,它的底层是数据结构加链表,这还是一个线程不安全的数据结构
画个图带大家回忆一下HashMap
在添加元素的时候,我们是把每个元素当做一个链表的头结点,然后插入元素.
下面让我们回忆一下以hashmap为基础实现的哈希桶
// 哈希桶的简单实现
// key-value 模型
public class HashBucket {
private static class Node {
private int key;
private int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private Node[] array;
private int size; // 当前的数据个数
private static final double LOAD_FACTOR = 0.75;
private static final int DEFAULT_SIZE = 8;//默认桶的大小
public int put(int key, int value) {
int index = key % array.length;
Node cur = array[index];
while (cur != null) {
if (cur.key == key) {
return key;
}
cur = cur.next;
}
Node node = new Node(key, value);
node.next = array[index];
array[index] = node;
size++;
double loadFactor=loadFactor();
if(loadFactor>LOAD_FACTOR){
resize();
}
return -1;
}
private void resize() {
//扩容意味着重新哈希
Node[] newArray=new Node[2*array.length];
for(int i=0;i<array.length;i++){
Node cur=array[i];
while(cur!=null){
Node curNext=cur.next;//记录一下，因为是在重新哈希，所以下一个结点会出现找不到的情况
int index=cur.key%newArray.length;
cur.next=newArray[i];
newArray[i]=cur;
cur=curNext;
}
}
}
// write code here
//
//
private double loadFactor() {
return size * 1.0 / array.length;
}
public int get(int key){
int index=key%array.length;
Node cur=array[index];
while(cur!=null){
if(cur.key==key){
return cur.key;
}
cur=cur.next;
}
return -1;
}
}
再回忆一下泛型哈希桶的实现
//泛型哈希桶的实现
public class HashBuck2<K,V> {
private static class Node<K, V> {
private K key;
private V value;
Node<K, V> next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public Node<K,V>[] array=(Node<K,V>[])new Node[10];
public int size;
public void put(K key, V value) {
int hash = key.hashCode();
int index = hash % array.length;//自己写引用类型的时候记得equals和hashcode方法
Node cur = array[index];
while (cur != null) {
if (cur.key.equals(key)) {
return;
}
cur = cur.next;
}
Node<K, V> node = new Node<>(key, value);
node.next = array[index];
array[index] = node;
size++;
}
public V get(K key){
int hash=key.hashCode();
int index=hash%array.length;
Node<K,V> cur =array[index];
while(cur!=null){
if(cur.key.equals(key)){
return cur.value;
}
cur=cur.next;
}
return null;
}
}
2.比较HashTable,ConcurrentHashMap
1.现在再来看一下,HashTable ,HashTable是对整体加锁的,线程是安全的,采用synchronized加锁,来看看图
多线程加锁,对于HashMap来说是线程安全的,但是有一个人问题,假设我现在要在1下标和2下标分别插入元素,那么此时是线程安全的吗?答案是yes!但是现在只有一个锁,加锁对象都是this, 那么1和2就会产生锁竞争,就会产生阻塞等待,所以这样的加锁降低效率,那么我们就采用另一种方式,我们采用ConcurrentHashMap,对每个下标都加锁,每次进行操作都是对不同链表的头结点进行加锁,不会用锁冲突,上图
我要对1和2同时插入,那么既能保证线程安全还能保证效率高,每次操作都是对不同链表加锁不会产生锁冲突,那么这个时候就可以采用偏向锁来解决,也就是做个标记,必要时再加锁.
2.不仅是加锁方面,还有其他方面的
Concurrent更高效的利用CAS操作进行无锁编程,比如进行和获取和更新操作,就可以使用CAS ,CAS是线程安全的,比锁更高效,但是锁应用范围更广泛
3.优化扩容策略
当哈希表的负载因子达到了阈值,也就是0.75的时候就需要扩容,扩容需要重新申请内存空间,搬运元素,也就是把旧表的元素删除加到新表上,这时候就面临一个问题,如果搬运的元素非常多,那么可能会很卡顿,所以我们需要用到Concurrent来进行搬运,那么它也是会申请一根很大的内存空间,但是不同于HashMap的是,它是一点一点搬运的,速度就会很快,那么此时就相当于有两个哈希表,此时插入元素,去新表插入,删除元素在旧表或者新表,查找的时候新表旧表一起查
3.ConcurrentHahMap和HashTable的区别
1.锁力度不同,ConcurrentHahMap的锁力度更低,并发程度就更高
2.关于CAS,Concurrent更高效利用了CAS原子操作,更加高效
3.优化了扩容策略
4.一个小问题:
以上就是今天的分享了,我们下期再见
