大家好,今天为大家带来新的知识, 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.一个小问题:
ConcurrentHashMap 在 jdk1.8 做了哪些优化？
取消了分段锁 , 直接给每个哈希桶 ( 每个链表 ) 分配了一个锁 ( 就是以每个链表的头结点对象作为锁对
象 ).
5.总结HashTable, HashMap, ConcurrentHashMap 之间的区别
Hashtable和HashMap、ConcurrentHashMap 之间的区别?
HashMap: 线程不安全. key 允许为 null
Hashtable: 线程安全. 使用 synchronized 锁 Hashtable 对象, 效率较低. key 不允许为 null.
ConcurrentHashMap: 线程安全. 使用 synchronized 锁每个链表头结点, 锁冲突概率低, 充分利用
CAS 机制. 优化了扩容方式. key 不允许为 null
以上就是今天的分享了,我们下期再见
