知识充电站
TreeMap<K,V>的Key值是要求实现java.lang.Comparable,所以迭代的时候TreeMap默认是按照Key值升序排序的;TreeMap的实现是基于红黑树结构。适用于按自然顺序或自定义顺序遍历键(key)。
HashMap<K,V>的Key值实现散列hashCode(),分布是散列的、均匀的,不支持排序;数据结构主要是桶(数组),链表或红黑树。适用于在Map中插入、删除和定位元素。
HashMap是线程安全的吗?为什么呢?
HashMap是线程不安全的!
线程不安全体现在JDK.1.7时在多线程的情况下扩容可能会出现死循环或数据丢失的情况,主要是在于扩容的transfer方法采用的头插法,头插法会把链表的顺序给颠倒过来,这是引起死循环的关键。在JDK1.8时在多线程的情况下扩容会可能会出现数据覆盖的情况,例如有两个线程A、B都在进行put操作(对HashMap进行put操作实际上是调用了putVal()方法),并且这两个线程hash函数计算出的插入下标是相同的,当线程A执行完putVal()方法中的一句用于判断有没有发生hash碰撞的代码后(下面源代码的15行),由于时间片耗尽导致被挂起(注意这个时候线程A的判断结果是没有发生hash碰撞,保存了这个判断结果,但是还没有执行下一句插入元素代码,这个时候被挂起了),而线程B得到时间片后也是调用putVal()方法插入元素,由于两个线程hash函数计算出的下标是一样的,并且前面线程A因为时间片到了还没来得及插入元素就被挂起了,所以这个时候线程B判断结果也是没有hash碰撞,直接在该下标处插入了元素,完成了正常的插入,然后线程A获得时间片,由于之前已经进行了hash碰撞的判断,所有此时不会再进行判断,而是直接进行插入,这就导致了线程B插入的数据被线程A覆盖了,所以HashMap是线程不安全。
原因:
- JDK1.7 中HashMap线程不安全体现在多线程扩容导致死循环、数据丢失
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; //线程A执行完这句后因为时间片耗尽就被挂起了 newTable[i] = e; e = next; } } }
HashMap的扩容就是调用上面的transfer方法来实现的,扩容后要采用头插法将元素迁移到新数组中,头插法会将链表的顺序翻转,这也是形成死循环的关键点。
上面的代码主要看下面的四句代码
//重新定义下标 Entry<K,V> next = e.next; //下面三句就是头插法的实现 e.next = newTable[i]; newTable[i] = e; e = next;
模拟扩容造成死循环和数据丢失
假设现在有两个线程A、B同时对下面这个HashMap进行扩容操作:
正常扩容后的结果是下面这样的:
但是当线程A执行完上面transfer函数的第10行代码时,CPU时间片耗尽,线程A被挂起。即如下图中位置所示:
解析:线程A中:e=3、next=7、e.next=null,可以看到图1的链表中第一个是3,下一个是7,所以transfer函数第一次执行中e=3,next=7,本来根据图1的情况应该是e.next=7,但是线程A在transfer函数中执行到了 e.next = newTable[i]; 这句,而newTable[i]由于是刚扩容的所以是为null,所以执行这句后 e.next =null
线程A挂起后,此时线程B得到时间片后正常执行,并完成resize扩容操作,结果如下:
线程B完成扩容后,此时主内存中newTable和table都是最新的
也就是说主内存中7.next=3和3.next=null(这里我一开始就疑惑为什么线程B都扩容完了线程A拿到时间片后还要扩容?其实是因为线程A压根就不知道线程B已经扩容完了,线程A也不管你扩容完了没,反正就是继续执行自己之前没有执行完的代码,由于是根据线程B扩容完后存放在内存中的数据继续扩容的,所以线程A才会出现下面的数据丢失和死循环)
随后线程A获得CPU时间片继续执行newTable[i] = e和e = next;这两句代码,线程A在挂起之前的数据是e=3、next=7、e.next=null,执行这两句后结果是newTable[3] =3,e=7,执行完此轮循环后线程A的情况如下
解析:newTable[3] =3,e=7(这里的newTable[3] =3可以理解为指针,其实就是newTable[3] 是个数组,那它的值就是指向3这个节点,e=7的e可以理解为指针,从原本的指向3到指向7)
接着继续执行下一轮循环,此时e=7,从主内存中读取e.next时发现主内存中7.next=3,此时next=3,并将7采用头插法的方式放入新数组中,并继续执行完此轮循环
//此时e=7,内存中7.next=3、3.next=null,newTable[3] =3,e=7 //JMM中规定所有的变量都存储在主内存中每条线程都有自己的工作内存, //线程的工作内存中保存了该线程所使用的变量的从主内存中拷贝的副本。 //线程对于变量的读、写都必须在工作内存中进行,而不能直接读、写主内存中的变量。 //同时,本线程的工作内存的变量也无法被其他线程直接访问,必须通过主内存完成。 Entry<K,V> next = e.next;------->next=7.next=3; //下面三句就是头插法的实现 e.next = newTable[i];----------》e.next=3;//注意这里的e还是7,这句就是7的指针指向3 newTable[i] = e; --------------》newTable[3]=e=7; e = next;----------------------》e=next=3;
注意:JMM中规定所有的变量都存储在主内存(Main Memory)中,每条线程都有自己的工作内存(Work Memory),线程的工作内存中保存了该线程所使用的变量的从主内存中拷贝的副本。线程对于变量的读、写都必须在工作内存中进行,而不能直接读、写主内存中的变量。同时,本线程的工作内存的变量也无法被其他线程直接访问,必须通过主内存完成。
所以上面线程B执行后它的工作内存存储自己的执行结果7.next=3和3.next=null,然后主内存同步过去,最后线程A去主内存复制过来到自己的工作内存中
执行完此轮循环后结果如下
注意:当e=3时3.next=null这个是线程B执行后主内存中的结果
解析:这里唯一要注意的地方就是上面在执行 e.next = newTable[i];的时候结果是e.next=3;而这其中的e是7不是3!这句是把7和3连接起来,从7指向3。这里我一开始就把e.next=3;作为下一次循环的数据依据,然后就觉得应该是下面的图示情况,其实应该是当e=3的时候e.next=null作为数据依据
这种是错误的!
上轮next=3,e=3,执行下一次循环可以发现,3.next=null,所以此轮循环将会是最后一轮循环。
//此时e=3,内存中next=3,newTable[3]=7,e=3,e.next=null //任何一个线程的执行情况应该是放在内存中的,所以并发的时候才会出问题 //例如这个线程A去内存中拿的数据是线程B执行后的数据,已经不是线程A之前存的数据了 Entry<K,V> next = e.next;------->next=null; //下面三句就是头插法的实现 e.next = newTable[i];----------》e.next=7; newTable[i] = e; --------------》newTable[3]=3; e = next;----------------------》e=3;
执行完此轮循环后结果如下
当执行完上面的循环后发现next=null后,将不会进行下一轮循环。到此线程A、B的扩容操作完成,很明显当线程A执行完后,HashMap中出现了环形结构,当在以后对该HashMap进行操作时会出现死循环。并且从上图可以发现,元素5在扩容期间被莫名的丢失了,这就发生了数据丢失的问题。
JDK1.8 中HashMap线程不安全主要体现在数据覆盖
如果有两个线程A、B都在进行put操作(对HashMap进行put操作实际上是调用了putVal()方法),并且这两个线程hash函数计算出的插入下标是相同的,当线程A执行完putVal()方法中的一句用于判断有没有发生hash碰撞的代码后(下面源代码的15行),由于时间片耗尽导致被挂起(注意这个时候线程A的判断结果是没有发生hash碰撞,保存了这个判断结果,但是还没有执行下一句插入元素代码,这个时候被挂起了),而线程B得到时间片后也是调用putVal()方法插入元素,由于两个线程hash函数计算出的下标是一样的,并且前面线程A因为时间片到了还没来得及插入元素就被挂起了,所以这个时候线程B判断结果也是没有hash碰撞,直接在该下标处插入了元素,完成了正常的插入,然后线程A获得时间片,由于之前已经进行了hash碰撞的判断,所有此时不会再进行判断,而是直接进行插入,这就导致了线程B插入的数据被线程A覆盖了,从而线程不安全。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //如果当前map中无数据,执行resize方法。并且返回n if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //判断有没有发生hash碰撞,没有就直接插入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //否则的话,说明这上面有元素 else { Node<K,V> e; K k; //如果这个元素的key与要插入的一样,那么就替换一下,也完事。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //1.如果当前节点是TreeNode类型的数据,执行putTreeVal方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //还是遍历这条链子上的数据,跟jdk7没什么区别 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //2.完成了操作后多做了一件事情,判断,并且可能执行treeifyBin方法 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) //true || -- e.value = value; //3. afterNodeAccess(e); return oldValue; } } ++modCount; //判断阈值,决定是否扩容 if (++size > threshold) resize(); //4. afterNodeInsertion(evict); return null; }
通常解决hash冲突的方法有4种
1)开放定址法,也称为线性探测法,就是从发生冲突的那个位置开始,按照一定的次序从hash表中找到一个空闲的位置,然后把发生冲突的元素存入到这个空闲位置中。ThreadLocal就用到了线性探测法来解决hash冲突的。
像这样一种情况
在hash表索引1的位置存了一个key=name,当再次添加key=hobby时,hash计算得到的索引也是1,这个就是hash冲突。
使用开放定址法,就是按顺序向前找到一个空闲的位置来存储冲突的key,也就是如果这个冲突的位置的右边一个位置没有存放数据那就存放这个冲突的位置,如果存放了数据还是冲突了那就继续往右边推一个位置,直到可以存放这个数据,例如上面冲突后就应该放到索引2的位置,然后索引2的位置没有数据所以就直接存放,有数据还是冲突那就放索引3的位置,以此类推,直到存放了这个数据到Hash表
(2)链式寻址法,这是一种非常常见的方法,简单理解就是把存在hash冲突的key,以单向链表的方式来存储,比如HashMap就是采用链式寻址法来实现的。
像这样一种情况
存在冲突的key直接以单向链表的方式进行存储。
(3)再hash法,就是当通过某个hash函数计算的key存在冲突时,再用另外一个hash函数对这个key做hash,一直运算直到不再产生冲突。这种方式会增加计算时间,性能影响较大。
(4)建立公共溢出区, 就是把hash表分为基本表和溢出表两个部分,凡是存在冲突的元素,一律放入到溢出表中。
补充:HashMap在JDK1.8版本中,通过链式寻址法+红黑树的方式来解决hash冲突问题,其中红黑树是为了优化Hash表链表过长导致时间复杂度增加的问题。当链表长度大于8并且hash表的容量大于64的时候,再向链表中添加元素就会触发转化。
HashMap不是线程安全的,如果要保证线程安全怎么办呢?可以用什么?
(1)使用HashTable(不推荐使用)
private Map map = new Hashtable<>()
HashTable源码中发现,其get/put方法均被synchronized关键词修饰(该关键词修饰代表这个方法加上了同步锁,相当于任意线程运行到该方法时,首先应检查有没有其它线程在使用该方法,有的话要等待上一个线程使用完毕后,当前线程才能使用)
正因如此,Hash Table的线程安全是基于方法级阻塞制的,它们占用共享资源,所以导致同时只能有一个线程操作get或put,并且get和put操作不能同时执行,所以这种同步的集合效率很低,一般不建议使用这个集合。
(2)使用SynchronizedMap(不推荐使用)
private Map map = Collections.synchronizedMap(newHashMap())
这种是直接使用工具类里面的方法创建synchronizedMapCollections.synchronizedMap(newHashMap())返回的synchronizedMap对象,把传入的HashMap对象进行了包装而已。
这个同步方式实现也比较简单,看出SynchronizedMap的实现方式是加了个对象锁(HashTable加的是同步锁,SynchronizedMap加的是对象锁),每次对HashMap的操作都要先获取这个mutex对象才能进入,故而性能也不会比HashTable好到哪去,也不建议使用。
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) { return new SynchronizedMap<>(m); } private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable { private static final long serialVersionUID = 1978198479659022715L; private final Map<K,V> m; // Backing Map final Object mutex; // Object on which to synchronize SynchronizedMap(Map<K,V> m) { this.m = Objects.requireNonNull(m); mutex = this; } ... } //SynchronizedMap的put方法,实际调用的还是HashMap自己的put方法 public V put(K key, V value) { synchronized (mutex) {return m.put(key, value);} }
(3)ConcurrentHashMap(推荐使用)
private Map map = new ConcurrentHashMap<>()
这个实现结构最复杂,但同时也是效率最高最推荐使用的线程安全的Map,每个版本实现方式不一。Jdk8之前是使用分段加锁的方式,分成16个桶,每次只加锁其中一个桶,而jdk8又加入了红黑树和CAS算法来实现。
ConcurrentHashMap
什么是ConcurrentHashMap?实现原理是什么?
在多线程环境下,使用HashMap进行put操作时存在丢失数据的情况,为了避免这种bug的隐患,强烈建议使用ConcurrentHashMap代替HashMap。
HashTable是一个线程安全的类,它使用synchronized来锁住整张Hash表来实现线程安全,即每次锁住整张表让线程独占,相当于所有线程进行读写时都去竞争一把锁,导致效率非常低下。
ConcurrentHashMap可以做到读取数据不加锁,并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小,允许多个修改操作并发进行,其关键在于使用了锁分段技术。它使用了多个锁来控制对hash表的不同部分进行的修改。对于JDK1.7版本的实现, ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分,每个段其实就是一个小的Hashtable,它们有自己的锁。只要多个修改操作发生在不同的段上,它们就可以并发进行。JDK1.8的实现降低锁的粒度,JDK1.7版本锁的粒度是基于Segment的,包含多个HashEntry,而JDK1.8锁的粒度就是HashEntry(首节点)。
实现原理
JDK1.7
JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组结构和链表数组 HashEntry 结构组成,即 ConcurrentHashMap 把哈希桶数组切分成多个段Segment ,每个Segment 有 n 个 链表数组(HashEntry)组成,也就是通过分段锁来实现的。
ConcurrentHashMap 定位一个元素的过程需要进行两次Hash操作,第一次 Hash 定位到 Segment,第二次 Hash 定位到元素所在的链表的头部,因此,这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长,但是带来的好处是写操作的时候可以只对元素所在的 Segment 进行操作即可,不会影响到其他的 Segment,这样,在最理想的情况下,ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作(刚好这些写操作都非常平均地分布在所有的 Segment上),所以,通过这一种结构,ConcurrentHashMap 的并发能力可以大大的提高
如下图所示,首先将数据分为一段一段(Segment)的存储,然后给每一段(Segment)数据配一把锁,当一个线程占用锁访问其中一段数据时,其他段的数据也能被其他线程访问,实现了真正的并发访问。
Segment 是 ConcurrentHashMap 的一个内部类,主要的组成如下:
Segment 继承了 ReentrantLock,所以 Segment 是一种可重入锁,扮演锁的角色。Segment 默认为 16,也就是并发度为 16。
存放元素的 HashEntry,也是一个静态内部类,主要的组成如下:
其中,用 volatile 修饰了 HashEntry 的数据 value 和 下一个节点 next,保证了多线程环境下数据获取时的可见性!
为什么要用二次hash
主要原因是为了构造分离锁,使得对于map的修改不会锁住整个容器,提高并发能力。当然,没有一种东西是绝对完美的,二次hash带来的问题是整个hash的过程比hashmap单次hash要长,所以,如果不是并发情形,不要使concurrentHashmap。
JAVA7之前ConcurrentHashMap主要采用分段锁机制,在对某个Segment进行操作时,将该Segment锁定,不允许对其进行非查询操作,而在JAVA8之后采用CAS无锁算法,这种乐观操作在完成前进行判断,如果符合预期结果才给予执行,对并发操作提供良好的优化.
JDK1.8
在数据结构上, JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的Node数组+链表+红黑树结构;在锁的实现上,抛弃了原有的 Segment 分段锁,采用CAS + synchronized实现更加细粒度的锁。
将锁的级别控制在了更细粒度的哈希桶数组元素级别,也就是说只需要锁住这个链表头节点或红黑树的根节点,就不会影响其他的哈希桶数组元素的读写,大大提高了并发度。
ConcurrentHashMap中变量使用final和volatile修饰有什么用呢?
在 ConcurrentHashMap 中,使用 final 和 volatile 修饰变量可以提高线程安全性和可见性,具体作用如下:
1. final:使用 final 修饰的变量表示不可变变量,即该变量的值在初始化之后不能被修改。在 ConcurrentHashMap 中,使用 final 修饰 Node 类中的 key 和 hash 变量,可以保证它们在初始化之后不会被修改,从而避免了多线程之间的竞争和冲突。final修饰变量可以保证变量不需要同步就可以被访问和共享
2. volatile:使用 volatile 修饰的变量表示该变量是可见的,即对该变量的修改会立即被其他线程所感知。在 ConcurrentHashMap 中,使用 volatile 修饰了 Segment 类中的 count 和 modCount 变量,可以保证它们的修改对其他线程是可见的,从而避免了多线程之间的冲突和数据不一致的问题。
需要注意的是,虽然使用 final 和 volatile 修饰变量可以提高线程安全性和可见性,但是并不能完全保证线程安全和正确性。在使用 ConcurrentHashMap 时,还需要注意其他方面的线程安全问题,例如迭代器的使用、复合操作的原子性等。
JDK1.8 的CocurrentHashMap中为什么使用 synchronized替换 ReentrantLock?
在 JDK1.8 中,ConcurrentHashMap 内部对锁的实现进行了优化,使用了 CAS 操作和 synchronized 关键字来替换原来的可重入锁 ReentrantLock,主要原因如下:
1. 性能优化:使用 synchronized 关键字可以避免 ReentrantLock 中的 CAS 操作带来的性能损失,从而提高并发性能。
2.提高吞吐量:ConcurrentHashMap 是一个高并发的哈希表实现类,需要支持多个线程同时进行读写操作。使用 synchronized 关键字可以减少锁的竞争和冲突,从而提高吞吐量,提高并发性能。
3.简化代码:使用 synchronized 关键字可以避免 ReentrantLock 中需要手动加锁和解锁的复杂操作,从而简化了代码实现。这样可以减少代码的复杂度和出错的可能性,提高代码的可维护性和可读性。
需要注意的是,虽然 ConcurrentHashMap 在 JDK1.8 中使用了 synchronized 关键字来替换 ReentrantLock,但是它并不是传统意义上的 synchronized,而是使用了锁分段技术,将整个哈希表分成了多个段,每个段都有一个独立的锁,从而实现了高效的并发访问。这种锁分段技术可以避免锁的粒度过大或过小的问题,从而提高了并发性能和可伸缩性。
骚戴理解:在竞争和非竞争情况下使用 synchronized 的性能更好。因为 synchronized 关键字可以自动升级为轻量级锁、自旋锁等优化锁,避免了线程阻塞和切换的开销,从而提高了并发性能。而可重入锁 ReentrantLock 则需要进行手动加锁和解锁,需要进行 CAS 操作等复杂操作,从而导致性能损失
我们可以使用CocurrentHashMap来代替Hashtable吗?
我们知道Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。它们都可以用于多线程的环境,但是当Hashtable的大小增加到一定的时候,性能会急剧下降,因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation),不论它变得多么大,仅仅需要锁定map的某个部分,而其它的线程不需要等到迭代完成才能访问map。简而言之,在迭代的过程中,ConcurrentHashMap仅仅锁定map的某个部分,而Hashtable则会锁定整个map。
ConcurrentHashMap有什么优点和缺点吗?
优点
1. 高并发性能:ConcurrentHashMap 内部使用锁分段技术,将整个哈希表分成多个段,每个段都有一个独立的锁,从而实现了高效的并发访问。在多线程并发访问的情况下,ConcurrentHashMap 可以提供很高的并发性能和吞吐量。
2. 线程安全:ConcurrentHashMap 是一个线程安全的哈希表实现类,可以支持多个线程同时进行读写操作,而不需要额外的同步措施。在多线程并发访问的情况下,ConcurrentHashMap 可以保证数据的一致性和正确性。
3. 可伸缩性:ConcurrentHashMap 内部使用锁分段技术,可以根据实际的需求来调整锁的粒度和数量,从而实现可伸缩性。在多线程并发访问的情况下,ConcurrentHashMap 可以根据实际的并发情况来动态调整锁的数量和大小,以提供更好的并发性能。
4. 高效迭代器:ConcurrentHashMap 内部的迭代器是快速失败的迭代器,可以在迭代过程中检测到其他线程对哈希表的修改,从而避免了数据的不一致性和错误。在多线程并发访问的情况下,ConcurrentHashMap 可以提供高效的迭代器操作,以支持数据的遍历和访问。
5. 可定制性:ConcurrentHashMap 提供了很多可定制的参数和配置选项,可以根据实际的需求来调整哈希表的大小、负载因子、并发级别等参数,以实现更好的性能和可伸缩性。
缺点
1. 内存占用:ConcurrentHashMap 内部需要维护多个段和多个链表,以支持高并发的读写操作,从而导致内存占用较高。在数据量较大的情况下,可能会导致内存溢出等问题。
2. 无序性:ConcurrentHashMap 内部使用哈希表来存储数据,哈希表的特点是无序性,因此无法保证数据的顺序。如果需要按照某种顺序来访问数据,需要进行额外的排序操作。
3. 迭代器弱一致性:ConcurrentHashMap 内部的迭代器是弱一致性的,即在迭代过程中,如果其他线程对哈希表进行了修改,会导致迭代器抛出 ConcurrentModificationException 异常。因此,在使用迭代器访问 ConcurrentHashMap 时,需要注意线程安全和异常处理。
4. 扩容代价:ConcurrentHashMap 内部需要进行扩容操作,以支持更多的数据存储和更高的并发性能。但是,扩容操作需要进行数据迁移和重建哈希表等复杂操作,可能会导致性能下降和延迟增加。
ConcurrentHashMap在JDK 7和8之间的区别
ConcurrentHashMap 在 JDK 7 和 JDK 8 中都有所改进和优化,主要的区别如下:
1. 数据结构:JDK 7 中的 ConcurrentHashMap 内部使用分段锁技术实现并发访问,每个段都是一个独立的哈希表,可以独立地进行读写操作。而 JDK 8 中的 ConcurrentHashMap 则使用了 CAS 操作和链表/红黑树结构来实现并发访问,可以更好地支持高并发和大规模数据。
2. 并发性能:JDK 8 中的 ConcurrentHashMap 在并发性能方面有所提升,主要是因为它使用了 CAS 操作和链表/红黑树结构来实现并发访问,减少了锁的竞争和开销,从而提高了并发性能。JDK1.7 采用 Segment 的分段锁机制实现线程安全,其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CAS+synchronized保证线程安全。
3. 内存占用:JDK 8 中的 ConcurrentHashMap 在内存占用方面有所改进,主要是因为它使用了链表/红黑树结构来存储数据,可以更好地利用内存空间,减少了内存占用。
4. 扩容策略:JDK 8 中的 ConcurrentHashMap 在扩容策略方面有所改进,主要是因为它使用了链表/红黑树结构来存储数据,可以更好地支持并发扩容,减少了数据迁移和重建哈希表的开销。
5. API 接口:JDK 8 中的 ConcurrentHashMap 增加了一些新的 API 接口,例如 forEach、reduce、search 等,可以更方便地对哈希表进行遍历和操作。
6.锁的粒度:JDK1.7 是对需要进行数据操作的 Segment 加锁,JDK1.8 调整为对红黑树的根节点或者链表的头结点进行加锁
Java 中 ConcurrentHashMap 的并发度是什么?
并发度可以理解为程序运行时能够同时更新 ConccurentHashMap且不产生锁竞争的最大线程数。在JDK1.7中,实际上就是ConcurrentHashMap中的分段锁个数,即Segment[]的数组长度,默认是16,这个值可以在构造函数中设置。
如果自己设置了并发度,ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作为实际并发度,也就是比如你设置的值是17(24<17<25),那么实际并发度是32(25)。
如果并发度设置的过小,会带来严重的锁竞争问题;如果并发度设置的过大,原本位于同一个Segment内的访问会扩散到不同的Segment中,CPU cache命中率会下降,从而引起程序性能下降。
在JDK1.8中,已经摒弃了Segment的概念,选择了Node数组+链表+红黑树结构,并发度大小依赖于数组的大小。
ConcurrentHashMap 迭代器是强一致性还是弱一致性?
ConcurrentHashMap 的迭代器是弱一致性的,而不是强一致性的。
弱一致性的迭代器指的是迭代器在遍历过程中可以看到其他线程对哈希表的修改,但是无法保证遍历结果的一致性和正确性。如果其他线程在遍历过程中对哈希表进行了修改,可能会导致迭代器抛出 ConcurrentModificationException 异常,或者遍历到重复或丢失的元素。
这是因为 ConcurrentHashMap 内部使用分段锁技术来实现并发访问,每个段都有一个独立的锁,可以独立地进行读写操作。在遍历过程中,如果其他线程对同一个段进行了修改,就可能会导致迭代器遍历到不一致的元素。因此,ConcurrentHashMap 的迭代器只能保证最终一致性,不能保证强一致性。
为了避免迭代器的异常和错误,可以在遍历过程中使用锁或者采用其他的同步措施。也可以使用 ConcurrentHashMap 的新 API 接口 forEach、reduce、search 等,它们使用了更加安全和可靠的遍历方式,可以更好地避免迭代器的异常和错误。
ConcurrentHashMap 不支持 key 或者 value 为 null 的原因?
因为 ConcurrentHashMap 是用于多线程的 ,如果ConcurrentHashMap.get(key)得到了 null 就会有二义性,可能没有这个key或者可能有这个key但是对应的值是null
那为什么HashMap就没有这个二义性呢?
可以调用containsKey方法来判断二义性,没有这个key就返回false,有这个key但是对应的值是null就返回true,可以通过这个方法来区分上面说道的二义性问题,注意containsKey这个方法HashMap和ConcurrentHashMap中都有,之所以一个有二义性一个没二义性主要是因为一个是单线程的情况,一个是多线程的情况
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
ConcurrentHashMap为什么不能解决二义性问题
因为ConcurrentHashMap是线程安全的,一般使用在并发环境下,你一开始get方法获取到null之后,再去调用containsKey方法,没法确保get方法和containsKey方法之间,没有别的线程来捣乱,刚好把你要查询的key给设置了进去或者删除掉了。
SynchronizedMap 和 ConcurrentHashMap 有什么区别?
SynchronizedMap 和 ConcurrentHashMap 都是线程安全的 Map 实现类,但是它们之间有以下区别:
1. 数据结构:SynchronizedMap 是基于 Hashtable 实现的,而 ConcurrentHashMap 是基于哈希表实现的。
2. 并发性能:ConcurrentHashMap 在并发性能方面比 SynchronizedMap 更优秀,因为它使用了分段锁技术来实现并发访问,可以同时进行读写操作,而 SynchronizedMap 则需要使用同步锁来保证线程安全,因此在高并发环境下性能较差。
3. 锁粒度:ConcurrentHashMap 的锁粒度更细,可以支持更高的并发度,而 SynchronizedMap 的锁粒度更粗,只能支持单个线程的访问。
4. 扩容策略:ConcurrentHashMap 的扩容策略更优秀,可以在不影响并发性能的情况下进行扩容,而 SynchronizedMap 的扩容策略则需要使用同步锁来保证线程安全,可能会影响并发性能。
5. null 值:ConcurrentHashMap 不支持 key 或者 value 为 null,而 SynchronizedMap 则允许 key 或者 value 为 null。
综上所述,虽然 SynchronizedMap 和 ConcurrentHashMap 都是线程安全的 Map 实现类,但是在并发性能、锁粒度、扩容策略和 null 值等方面存在差异,因此在实际开发中需要根据具体的应用场景选择合适的实现类。如果需要支持高并发、大规模数据和 null 值,建议使用 ConcurrentHashMap,如果数据量较小,可以使用 SynchronizedMap。
HashMap 和 ConcurrentHashMap 的区别
HashMap 和 ConcurrentHashMap 都是哈希表实现的 Map 集合,但是它们之间有以下区别:
1. 线程安全性:HashMap 是非线程安全的,而 ConcurrentHashMap 是线程安全的。ConcurrentHashMap 使用了分段锁技术来实现并发访问,可以同时进行读写操作,而 HashMap 则需要使用同步锁来保证线程安全,因此在高并发环境下性能较差。
2. 并发性能:ConcurrentHashMap 在并发性能方面比 HashMap 更优秀,因为它使用了分段锁技术来实现并发访问,可以同时进行读写操作,而 HashMap 则需要使用同步锁来保证线程安全,因此在高并发环境下性能较差。
3. 锁粒度:ConcurrentHashMap 的锁粒度更细,可以支持更高的并发度,而 HashMap 的锁粒度更粗,只能支持单个线程的访问。
4. 扩容策略:ConcurrentHashMap 的扩容策略更优秀,可以在不影响并发性能的情况下进行扩容,而 HashMap 的扩容策略则需要使用同步锁来保证线程安全,可能会影响并发性能。
5. null 值:ConcurrentHashMap 不支持 key 或者 value 为 null,而 HashMap 则允许 key 或者 value 为 null。
综上所述,虽然 HashMap 和 ConcurrentHashMap 都是哈希表实现的 Map 集合,但是在线程安全性、并发性能、锁粒度、扩容策略和 null 值等方面存在差异,因此在实际开发中需要根据具体的应用场景选择合适的实现类。如果需要支持高并发、大规模数据,建议使用 ConcurrentHashMap,如果数据量较小,可以使用 HashMap。
ConcurrentHashMap 和 Hashtable 的区别?
ConcurrentHashMap 和 Hashtable 都是线程安全的哈希表实现类,但是它们之间有以下区别:
1. 数据结构:ConcurrentHashMap 是基于哈希表实现的,而 Hashtable 是基于同步方法实现的。
2. 并发性能:ConcurrentHashMap 在并发性能方面比 Hashtable 更优秀,因为它使用了分段锁技术来实现并发访问,可以同时进行读写操作,而 Hashtable 则需要使用同步锁来保证线程安全,因此在高并发环境下性能较差。
3. 锁粒度:ConcurrentHashMap 的锁粒度更细,可以支持更高的并发度,而 Hashtable 的锁粒度更粗,只能支持单个线程的访问。
4. 扩容策略:ConcurrentHashMap 的扩容策略更优秀,可以在不影响并发性能的情况下进行扩容,而 Hashtable 的扩容策略则需要使用同步锁来保证线程安全,可能会影响并发性能。
5. null 值:ConcurrentHashMap 不支持 key 或者 value 为 null,而 Hashtable 则允许 key 或者 value 为 null。
6. 迭代器:ConcurrentHashMap 的迭代器是弱一致性的,可以在迭代过程中进行并发修改,而 Hashtable 的迭代器是强一致性的,不允许在迭代过程中进行并发修改。
综上所述,虽然 ConcurrentHashMap 和 Hashtable 都是线程安全的哈希表实现类,但是在线程安全性、并发性能、锁粒度、扩容策略、null 值和迭代器等方面存在差异,因此在实际开发中需要根据具体的应用场景选择合适的实现类。如果需要支持高并发、大规模数据和 null 值,建议使用 ConcurrentHashMap,如果数据量较小,可以使用 Hashtable。
两者的对比图: HashTable:
JDK1.7的ConcurrentHashMap:
JDK1.8的ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点):
ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。