浅谈HashTable, HashMap, ConcurrentHashMap 之间的区别

       大家好,今天为大家带来新的知识,  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.一个小问题:

以上就是今天的分享了,我们下期再见