面试整理——Java集合

Java集合

第一节 综合

问：java的集合框架有哪几种？

两种：collection和map，其中collection分为set和List。

问：平常用到哪些集合类？

答：ArrayList，LinkedList，HashSet，HashMap，TreeMap等（补充：ArrayQueue，PriorityQueue，TreeSet，EnumSet，LinkedHashSet，EnumMap，LinkedHashMap，WeakHashMap，IdentityHashMap）

Java集合(一) 概述

问：集合迭代器的原理？

集合接口Collection继承了接口Iterable，此接口有一个方法 iterator() 返回一个迭代器Iterator接口。

Iterator接口定义了三个方法：hasNext() 、next() 、remove() 。

在如AbstractList和ArrayList中通过私有类Itr实现Iterator接口，采用快速失败模式，定义了一个计数器ModCount来保证在遍历过程中内容未被修改，否则抛出异常。

问：快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

快速失败是指迭代器遍历集合对象时发现内容被同时修改，且修改导致了计数器与期待值不同，导致抛出异常Concurrent Modification Exception（迭代器内部有计数器ModCount，每次移动指针前会检查当前值是否是expected，若修改不会使modCount不匹配就不会抛出异常）

安全失败则是指相应集合并不直接在内部访问，而是先拷贝副本，在副本上进行遍历，所以遍历过程中的修改不会影响到读取。

问：了解了哪些并发安全集合，从list到map都讲一下？

• 被弃用的两个集合：vector，HashTable。

• Collections对集合的安全封装（如Collections.synchronizedList）

• Concurrent包提供的：ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentSkipListSet和ConcurrentLinkedQueue，还有加了写锁的CopyOnWriteArrayList和CopyOnWriteArraySet。

问：List，Map，Set 接口在存取元素时，各有什么特点？

• List：元素存入有顺序，可重复。取元素时可以用迭代器遍历获取，也可以根据下标获取。
• Map：元素按键值对存储，无存放顺序，键不可重复，值可重复。可以根据键获得值，也可以获得所有键或值的集合，以及键值组合的对象Entry的集合。
• Set：元素存入无顺序，不可重复。取元素时需要用迭代器遍历获取。

问：接口RandomAccess的作用？

类似于Serializable和Cloneable，RandomAccess也是一个标记接口，表示对象支持快速随机访问。比如ArrayList实现了此接口，其底层是数组，而LinkedList则未实现此接口，其底层是链表。

对于支持快速随机访问的集合可以使用循环来高效遍历，而不支持的有序集合最好使用迭代器来遍历。

---

第二节 List

问：List你使用过哪些？

ArrayList和LinkedList使用的最多，也最具代表性。

问：你知道vector和ArrayList和linkedList的区别嘛？扩容机制等？

ArrayList实现是一个数组，可变数组，默认初始化长度为10，也可以我们设置容量，但是没有设置的时候是默认的空数组，只有在第一步add的时候会进行扩容至10（重新创建了数组），后续扩容按照3/2的大小进行扩容，是线程不安全的，适用多读取，少插入的情况。

linkedList是基于双向链表的实现，使用了尾插法的方式，内部维护了链表的长度，以及头节点和尾节点，所以获取长度不需要遍历。适合一些插入/删除频繁的情况。

Vector是线程安全的，实现方式和ArrayList相似，也是基于数组，但是方法上面都有synchronized关键词修饰。其扩容方式是原来的两倍。

问：ArrayList的实现？怎么扩容？怎么插入？怎么删除？在遍历ArrayList时，删除元素会发生什么？LinkedList呢？

ArrayList底层通过数组来存放元素，但因为实现了自动扩容所以也叫作动态数组。扩容、插入和删除操作都通过grow函数调用数组浅复制库函数（System.arraycopy），其中扩容通过复制生成副本返回一个新的数组，非尾部插入和删除则是对当前数组进行覆盖式的复制，删除操作最后会移除末尾元素。

对于ArrayList，删除元素时，后续元素会前移，所以如果遍历方向是正向，会漏掉删除操作后一位的元素判断，如果使用for-each循环遍历会因为修改了操作数而直接抛出异常。

对于LinkedList，删除元素时会先后断开要元素和前后节点的链接，然后重新链接前后节点，根据情况更新链表首尾节点，并清空元素值。

Java集合(三) List

问：ArrayList和LinkedList区别？使用场景？链表和数组的优缺点？

答：ArrayList是动态索引数组，LinkedList则是有序链表。前者可以快速随机访问，后者则会较慢。但链表更方便删除，因为只要局部变动，而数组则会影响到后续所有元素。所以数组易查难改，链表易改难查。LinkedList也通过迭代器进行插入操作。

ArrayList适合在频繁读取的场景，而LinkedList则适合在频繁插入删除的场景。

问：讲一下写时复制？写时复制和读写锁的区别？

写时复制即CopyOnWrite，通过延迟更新的策略，牺牲数据实时性，保证数据一致性和读线程互不阻塞。

• 相同点：两者都是通过读写分离思想实现，都实现了读线程间互不阻塞。

• 不同点：使用读写锁依然会存在线程阻塞等待的情况，而COW则牺牲了数据实时性，保证读线程不会存在等待。

问：CopyOnWriteArrayList 原理？

CopyOnWriteArrayList 通过写时复制思想来实现线程安全的动态数组，底层数据结构仍是对象数组，但被 volatile 修饰来保证可见性。通过可重入锁 ReentrantLock 来保证写线程安全，读操作与单线程无异，写操作则先获取锁，然后通过 System.arraycopy() 进行数组浅复制，在新数组上添加元素，最终再更新数组引用。因为 happens-before 规则，保证读线程可以感知。

问：ArrayBlockingQueue 和 LinkedBlockingQueue 区别？

1. 队列中锁的实现不同：
   • ArrayBlockingQueue 队列中的锁是没有分离的，即生产和消费用的是同一个锁；
   • LinkedBlockingQueue 队列中的锁是分离的，即生产用的是 putLock ，消费是 takeLock 。
2. 在生产或消费时操作不同：
   • ArrayBlockingQueue 队列中在生产和消费的时候，是直接将枚举对象插入或移除的；
   • LinkedBlockingQueue 队列中在生产和消费的时候，需要把枚举对象转换为 Node<E> 进行插入或移除，会影响性能。
3. 队列大小初始化方式不同：
   • ArrayBlockingQueue 实现的队列中必须指定队列的大小；
   • LinkedBlockingQueue 实现的队列中可以不指定队列的大小，但是默认是 Integer.MAX_VALUE 。

---

第三节 Set

问：HashSet 和 TreeSet 原理？

HashSet 即散列集，因为散列的关系所以集合的访问顺序是随机的。底层是基于一个 HashMap 来实现的，相关操作也是直接调用 HashMap API来完成。其设计就是利用 HashMap 的键来存放元素，用统一的 PRESENT 来作为 HashMap 的值，利用 HashMap 的键的唯一性来实现集合的元素不重复。
TreeSet 即树集，与散列集不同，树集是一个有序集合，其排序通过红黑树来实现，每次新增元素时都会放在正确的排序位置，以新增操作的开销来实现有序访问。

---

第四节 Map

4.1 HashMap

问：说说你了解的HashMap吧？

hashMap是Map的结构，内部用了数组+链表的方式，在1.8后，当链表长度达到8的时候，会变成红黑树，这样子就可以把查询的复杂度变成O（nlogn）了，默认负载因子是0.75，为什么是0.75呢？

我们知道当负载因子太小，就很容易触发扩容，如果负载因子太大就容易出现碰撞。所以这个是空间和时间的一个均衡点，在1.8的hashmap介绍中，就有描述了，貌似是0.75的负载因子中，能让随机hash更加满足0.5的泊松分布。

除此之外，1.7的时候是头插法，1.8后就变成了尾插法，主要是为了解决rehash出现的死循环问题，而且1.7的时候是先扩容后插入，1.8则是先插入后扩容(为什么？正常来说，如果先插入，就有可能节点变为树化，那么是不是多做一次树转化，比1.7要多损耗，个人猜测，因为读写问题，因为hashmap并不是线程安全的，如果说是先扩容，后写入，那么在扩容期间，是访问不到新放入的值的，是不是不太合适，所以会先放入值，这样子在扩容期间，那个值是在的）。

1.7版本的时候用了9次扰动，5次异或，4次位移，减少hash冲突，但是1.8就只用了两次，觉得就足够了一次异或，一次位移。

TODO

**问：能讲讲HashMap的实现原理吗？HashMap的底层是什么？HashMap内部数据结构？ **

HashMap是通过散列函数把元素均匀的分散到不同的散列值上，也就是对应的数组下标上。

HashMap的底层实现就是数组+链表。

因为散列是不可靠的，会出现哈希冲突，所以采用链表来存放因为哈希冲突而产生的相同哈希值但不同的元素。1.8版本后增加了红黑树进行优化，在链表结构超过8个节点后就裂变为红黑树。

问：HashMap如何存值？put方法的过程？

HashMap计算元素的哈希码，通过散列函数获得键对应的索引值，来决定其在集合中的存放位置。

判断key是否是null，如果是null对应的hash值就是0，获得hash值过后则进行扰动，（1.7是9次，5次异或，4次位移，1.8是2次），获取到的新hash值找出所在的index，（n-1）& hash，根据下标找到对应的Node/entity，然后遍历链表/红黑树，如果遇到hash值相同且equals相同，则覆盖值，如果不是则新增。如果节点数大于8了，则进行树化（1.8）。完成后，判断当前的长度是否大于阀值，是就扩容（1.7是先扩容在put）。

问：解决hash冲突的方法有哪些？

解决哈希冲突的方法有两种：开放定址法和链地址法（拉链法）。开发地址法会在发生哈希碰撞时通过探测技术继续在哈希表中找到空闲位置来存放，根据探测方式的不同有线性探测、二次探测和双散列探测。链地址法就是将每个散列表元素都对应一个链表。

问：hashmap查询的时间复杂度能达到O(1)是什么实现的？里面的索引是怎么计算的？

HashMap查询时根据哈希映射计算得到哈希码，直接走数组索引找到对应链表，不考虑哈希冲突的情况，可以达到O(1)。

索引通过调用对象的hashcode方法获取原始哈希码，然后右移16位使高区16位和低区16位进行异或运算，保留原高区16位，因为高区16位基本用不到，这样融合高区和低区的特征。在计算数组索引时再通过 (n - 1) & hash 来得到相应下标。

问：HashMap什么时候会进行rehash？

当所存键值对超过阈值，即容量和装填因子的积时，HashMap需要扩容并因为容量的变更而对元素进行再散列。

问：HashMap的初始容量设置成多少比较合适呢？

一般设置为预测元素数的75%到150%，因为一般装填因子为0.75，扩容和再散列会比较影响哈希表性能，所以要尽量保证不会发生多次再散列。

问：HashMap为什么不是线程安全的？怎么让HashMap变得线程安全？HashMap多线程有什么问题？怎么解决？

因为HashMap实现中并没有添加锁机制，多线程时容易导致数据错误。

比如：

1. put操作，多个线程得到相同的哈希码，可能会导致A线程结果覆盖掉B线程结果。
2. 旧版本的resize因为头插法的实现多线程会导致单向循环链表，get操作会陷入死循环。

向HashMap实现中增加锁机制的设计可以使其线程安全，当然一般直接使用线程安全的ConcurrentHashMap。

用JDK提供的ConcurrentHashMap替代HashMap即可。虽然Hashtable有加锁，但synchronized会大大降低效率，而ConcurrentHashMap使用了分段锁技术，效率会更高。当然单线程的HashMap的效率更高，能使用就尽量使用。多线程环境下，也可以运用栈封闭、ThreadLocal类、UnmodifiableMap类等方式使用HashMap。

问：结合源码说说HashMap在高并发场景中为什么会出现死循环？

高并发场景中多线程间会发生竞争，HashMap在put时会因为容量不足而进行扩容，旧版本新增元素是头插法，新元素会插在前面链接老元素，而在扩容后新数组链表会倒置，多线程环境下，线程间竞争一个线程读取数据后挂起，另一个线程执行使链表倒置，线程恢复后继续执行形成循环链表，所以形成了死循环。

问：HashMap 扩容机制，为什么都是 2 的 N 次幂？

根据哈希码获取数组索引是 (n - 1) & hash ，计算机可以高效进行按位与运算，当数组长度是2的N次方，其减一后会是前0后1的二进制格式，因此在进行与运算时1的部分就可以充分散列，如果后面还有0就会导致不同哈希码与运算得到相同索引，使散布不均匀。

问：HashMap和HashTable和ConcurrentHashMap的区别？

• HashMap：是map类型的一种最常用的数据结构，其底部实现是数组+链表/红黑树，其key是可以为null的，默认hash值为0，扩容以2的幂等次，是线程不安全的。
• HashTable：实现形式和hashMap差不多，它是线程安全的，是继承了Dictionary，也是key-value的模式，但是其key不能为null。
• ConcurrentHashMap：是并发包提供的一种线程安全的并发容器，采用分段的思想，早期版本通过分段锁Segment—基于ReetrantLock来实现的，1.8版本修改为 Node[] + CAS + Synchronized。

问：HashMap和HashTable有何不同？

Hashtable对部分方法有线程安全优化，而HashMap非线程安全。HashMap的键值允许为空，Hashtable则都不能为空。Hashtable因为使用synchronized效率不高，而HashMap在单线程环境下效率很高。

问：HashMap 和 WeakHashMap 的区别？

• WeakHashMap通过弱引用来保存键，如果没有普通对象引用只剩弱引用在使用对象（忽略映射中value对对象的强引用），GC会在周期性的垃圾回收中收回这些无用对象。
• 当只剩弱引用在使用对象时WeakHashMap就相当于退化为了HashMap。

问：HashMap 和 ConcurrentHashMap 的区别？在 hash 上的区别？

• ConcurrentHashMap线程安全，HashMap非线程安全。
• ConcurrentHashMap插入前判断是否需要扩容，HashMap则是插入元素后。
• 1.8版本的ConcurrentHashMap和HashMap都通过Node数组来实现，但ConcurrentHashMap的Node的val和next是volatile修饰的。
• TODO

问：HashMap 1.8版本前后的区别？JDK8 做了什么优化？最小树化容量？比如为什么是红黑树，别的树不可以吗；为什么 8 的时候树化，4 不可以吗？

HashMap优化：

• 优化了散列函数，通过移位异或，融合了高位特征；
• 底层由数组+链表改为数组+链表+红黑树，引入了红黑树来处理链表太长的极端情况，提高插入和查询整体效率；
• 头插法变为尾插法，链表顺序不会改变，从而优化了多线程的死循环问题。

最小树化容量：MIN_TREEIFY_CAPACITY = 64，区别于树化阈值8，其约束哈希表容量超过此值时才能将链表转换为红黑树，通过此参数可以决定是扩容还是树形化。

为什么是红黑树：红黑树的优势是插入和删除等操作较快，同时查询也不慢，相比如AVL树等，在单链表过长时，通过优化为红黑树更有利于后续更多节点的插入删除操作，综合性能要优于AVL树。

为什么树化阈值是8：

• 首先当散列均匀时，链表升级为红黑树的概率不大：理想情况下随机散列函数，概率分布遵循泊松分布，链表长度达到8的概率几乎为不可能。
• 当节点数量较少时，采用红黑树的意义不大，且因为红黑树节点的大小是普通链表节点大小的两倍，所以还会造成空间上的浪费。

问：jdk1.8中，对HashMap和ConcurrentHashMap做了哪些优化？

HashMap优化：

• 优化了散列函数，通过移位异或，融合了高位特征；
• 底层由数组+链表改为数组+链表+红黑树，引入了红黑树来处理链表太长的极端情况，提高插入和查询整体效率；
• 头插法变为尾插法，链表顺序不会改变，从而优化了多线程的死循环问题。

ConcurrentHashMap优化：

• 舍弃了臃肿的Segment + HashEntry，改为Node + CAS + Synchronized：Segment继承了ReentrantLock，其分段区域在初始时即确定，即并发数 concurrentLevel是固定的；而后者的并发数 concurrentLevel 是和数组大小保持一致的，每次扩容，并发度扩大一倍。
• 引入了红黑树来处理链表太长的极端情况等
• synchronized在JVM进行了优化：锁粗化、锁消除、锁自旋等等。

4.2 ConcurrentHashMap

问：讲一下你所知道的ConcurrentHashMap？

concurrentHashMap是线程安全的map结构，它的核心思想是分段锁。在1.7版本的时候，内部维护了segment数组，默认是16个，segment中有一个table数组（相当于一个segmeng存放着一个hashmap。。。），segment继承了reentrantlock，使用了互斥锁，map的size其实就是segment数组的count和。而在1.8的时候做了一个大改版，废除了segment，采用了cas加synchronize方式来进行分段锁（还有自旋锁的保证），而且节点对象改用了Node不是之前的HashEntity。

Node可以支持链表和红黑树的转化，比如TreeBin就是继承了Node，这样子可以直接用instanceof来区分。1.8的put就很复杂来，会先计算出hash值，然后根据hash值选出Node数组的下标（默认数组是空的，所以一开始put的时候会初始化，指定负载因子是0.75，不可变），判断是否为空，如果为空，则用cas的操作来赋值首节点，如果失败，则因为自旋，会进入非空节点的逻辑，这个时候会用synchronize加锁头节点（保证整条链路锁定）这个时候还会进行二次判断，是否是同一个首节点，在分首节点到底是链表还是树结构，进行遍历判断。

TODO

问：ConcurrentHashMap分段锁？如何分段？

当对ConcurrentHashMap的节点链表进行写操作时，会获得对应节点的私有锁，这样写操作的线程不会影响到其他操作或其他节点链表的操作。

如何分段：

• 1.7版本时定位Segment通过一种 Wang/Jenkins hash 的变种算法对元素的hashCode进行一次再散列，减少散列冲突。初始化Segment通过并发级别 concurrencyLevel 计算得到Segment长度和段偏移量 segmentShift 和段掩码 segmentMask ，后两者用于在Segment数组中定位 (hash >>> segmentShift) & segmentMask 。
• 1.8版本时，分段锁改为在特殊操作时通过 synchronizied 锁住链表头节点（如put和transfer），大部分操作通过CAS，在有并发竞争时再尝试自旋锁竞争。

问：ConcurrentHashMap如何进行散列？

1.7版本：

• ConcurrentHashMap会先在Segment分段时对获得的hashcode进行一次再散列，保证元素能均匀的分布在不同分段上，此阶段定位为 (hash >>> segmentShift) & segmentMask 。
• 在确定分段后，还会再一次散列，分配到不同的HashEntry中，此阶段定位为 hash & (tab.length - 1) 。两次散列方式不同，这样可以避免一次散列后得到的值过于雷同，导致第二次散列时聚集。

1.8版本：

• 通过获取键的哈希码，并将其高位右移异或 (h ^ (h >>> 16)) & HASH_BITS ，合并高低位特征，得到新的哈希码。
• 定位数组索引则通过 (tab.length - 1) & hash 。

问：ConcurrentHashMap如何获取元素？get()流程？

1. 先对哈希码进行再散列（高位右移异或）。
2. 新哈希码定位到散列表坐标 (n - 1) & h ，找到桶对应的首节点。
3. 依次判断哈希码、键是否相等，若是则命中并返回。
4. 不是则先判断是否已裂变红黑树（哈希码为负），若是则调用树查询。
5. 非树，则遍历链表查询后续节点。

问：ConcurrentHashMap如何放置元素？put()流程？

1. 首先校验不允许空值或空键，先对哈希码进行再散列（高位右移异或），并进入死循环。

2. 哈希表还未初始化，则会先进行初始化，然后继续循环尝试put。

3. 若表下标 (n - 1) & h 对应节点还为null，则尝试CAS新增链表节点，跳出死循环->7。

4. 已有哈希表，桶也存在，但对应桶正在扩容，则先协助扩容，然后继续循环。

5. 已有哈希表，桶也存在，桶可正常使用，则 synchronized 锁住此Node头节点。然后根据链表和红黑树来完成put操作。若是链表则覆盖或尾插法新增节点；若是红黑树则调用API，返回对应节点（可能是新建节点），并覆盖。

6. put操作若未成功就继续循环；若成功则先判断是否需要把链表转为红黑树，然后判断若只是更新操作就直接返回，若导致计数变更，则跳出死循环->7。

7. 死循环结束，调用addCount更新计数器值，并在这个过程中继续判断是否需要扩容。

问：ConcurrentHashMap如何统计数目？size()流程？

1. 若计数单元数组counterCells不为空，就遍历其内元素与baseCount相加求和，得到最终计数值。
2. 若为空则直接返回baseCount

无并发时只要用baseCount就足以，但一旦并发时CAS修改baseCount失败，就要启用counterCells，计算size时会将所有计数单元数组累加。

两种技术器都是通过 addCount() 来更新，但可能会因为并发而更新失败，会采用备用方法 fullAddCount()，死循环不断尝试。

问：ConcurrentHashMap如何更新计数器？addCount()流程？

更新计数器流程分两部分：并发更新和扩容。

1. 首先判断计数单元数组是否已创建，或尝试CAS对baseCount计数更新是否可以成功，二者皆为并发特征。
2. 如果不满足，表示不需要进行并发更新，然后根据check参数是否>=0判断是否需要扩容检查，如果不需要则结束。
3. 如果满足，则表示baseCount不可靠，需要更新计数单元数组。
4. 若当前计数单元数组为空，或选定计数单元为空，或CAS更新计数单元失败，则调用备案fullAddCount，然后结束。
5. 若非上述情况，则表示CAS更新成功，再判断所给check，若<=1表示还是链表，则直接返回，不进行扩容检查；若check>1，表示已是红黑树，需还要再算一下此时的size。
6. 然后进入扩容流程，首先判断只有 check >= 0 才有必要扩容。
7. 当此时size达到sizeCtl扩容阈值等，以此作为循环条件，则进行扩容循环，否则函数执行完毕。
8. 通过哈希表长度获得一个resize标识，是一个低16位首位为1的大数，从而能在左移后变成一个负数。
9. 判断 sizeCtl < 0 ，表示其他线程已经在扩容，然后根据五种特征判断扩容是否要结束，若满足即可跳出扩容循环。
10. 若不满足特征，表示扩容还在继续，则尝试CAS原子操作 sizeCtl++ ，表示帮助线程+1，并执行扩容transfer。
11. 若 sizeCtl >= 0 此时不在扩容，则尝试开启扩容流程，关键在于 (resize << 16) + 2 得到一个大的负数作为初始值，并CAS覆盖 sizeCtl ，后续每个线程都直接 sizeCtl++ ，成功后，执行扩容transfer。
12. 等扩容执行完毕后，更新一下当前size，继续循环，直到扩容条件不满足。

问：ConcurrentHashMap的扩容方式？transfer()流程？

1.7版本：concurrentHashMap是基于了segment的，segment内部维护了HashEntity数组，所以扩容是在这个基础上的，类比hashmap的扩容。

1.8版本：

1. 扩容流程可以多线程协作提高速度，每个线程负责一块区域，要求至少16个桶。
2. 扩容通过转移节点到新表来完成，新表初始化为旧表2倍大小。
3. 因为要线程间协作，在某线程转移某下标链表后，会在旧表用一个转移节点替换表示已处理。
4. 线程按分区一段一段倒序内循环，完成遍历后更新 sizeCtl-- ，表示参与转移线程数-1。
5. 当线程要进行转移时，根据链表和红黑树有不同的实现，但思路是一样的，都保留哈希码不变的，转移哈希码变更的。
6. 转移过程通过 synchronized 锁住同步资源-首节点。

问：ConcurrentHashMap怎么实现线程安全的？

1.7版本中：通过分段锁来实现线程安全，ConcurrentHashMap通过将数据分割，对每块数据添加一块分段锁，这样对一段数据的操作不会影响到另一段数据的操作，提供并行性。
1.8版本后：改进为Node[] + CAS + Synchronized。

在读操作时，用volatile修饰数据，保证了多线程的可见性，Java内存模型的happen-before原则保证了有happen-before关系的操作即使在多线程也可见，所以读操作时不需要加锁即能保证线程安全。

在写操作时，会对链表首节点加锁，通过 synchronized 保证覆盖操作安全，其余如更新计数器或新增节点等通过CAS来尝试原子操作，若因为并发竞争失败就循环竞争自旋锁不停尝试。

问：为什么说ConcurrentHashMap只具有弱一致性？

首先什么是数据弱一致性：

一致性常包含两类：数据一致性和事务一致性。导致数据一致性问题的原因是复制，弱一致性是相对于强一致性。强一致性的复制是同步的，弱一致性的复制是异步的。强一致性保证数据一定是一致的。

回到问题，并发容器具有弱一致性，主要是因为Java内存模型的 happens-before 原则。

现象是对于ConcurrentHashMap，当put一个元素后，并不一定能立刻get到此元素。对于 hb原则 来说，就是put和get的 hb关系 并非代码层面的顺序。即get操作运行到某行代码后，此时put操作还未完成，那么对于此get是无法感知到变化的。

ConcurrentHashMap能够保证每一次调用都是原子操作，但是并不保证多次调用之间也是原子操作。

所以Java API中声明的是保证get操作一定能看到已完成的put操作。

ConcurrentHashMap的弱一致性主要是为了提升效率，是一致性与效率之间的一种权衡。要成为强一致性，就得到处使用锁，甚至是全局锁，这就与Hashtable和同步的HashMap一样了。

问：ConcurrentHashMap和LinkedHashMap有什么区别？

• LinkedHashMap的节点链表是双向，ConcurrentHashMap则是单向
• ConcurrentHashMap是并发容器，LinkedHashMap则不能保证线程安全。

问：为什么ConcurrentHashMap中的链表转红黑树的阀值是8？

红黑树的占用空间是普通链表的两倍，如果哈希表的离散性足够好，各个节点的分布应该很均衡，所以很难会出现某个节点链表聚集的情况，但离散性较差时，就可能出现某个节点频繁哈希碰撞，所以根据概率统计得出随机哈希案例中桶达到8的概率很小仅为0.00000006，置换为红黑树就是为了防止糟糕的设计，使哈希表失去其效率，不如直接替换为红黑树来提升性能。

为什么树化阈值是8：

• 首先当散列均匀时，链表升级为红黑树的概率不大：理想情况下随机散列函数，概率分布遵循泊松分布，链表长度达到8的概率几乎为不可能。
• 当节点数量较少时，采用红黑树的意义不大，且因为红黑树节点的大小是普通链表节点大小的两倍，所以还会造成空间上的浪费。

4.3 ConcurrentSkipListMap

问：什么是ConcurrentSkipListMap？他和ConcurrentHashMap有什么区别？

ConcurrentSkipListMap是跳跃列表映射

ConcurrentHashMap
 ❌ Sorted
 ❌ Navigable
 ✅ Concurrent
ConcurrentSkipListMap
 ✅ Sorted
 ✅ Navigable
 ✅ Concurrent

• ConcurrentSkipListMap是有序的，ConcurrentHashMap则非有序。

• ConcurrentHashMap不能保证其操作的运行时间（散列结构因为重新散列的情况），允许对某些负载因子进行调整（大致是同时修改它的线程数）。ConcurrentSkipListMap则保证了各种操作的平均 O(log n) 性能，其本身是并发的，不支持为了并发性而进行的调优，而ConcurrentHashMap则可以进行并发调优。

• ConcurrentSkipListMap还有许多ConcurrentHashMap没有的操作：ceilingEntry/Key 、floorEntry/Key 等。

因为要维护一个排序顺序，相比ConcurrentHashMap，它的 get/put/contains 操作要慢，但它支持SortedMap，NavigableMap，ConcurrentNavigableMap等接口。如果使用ConcurrentHashMap得到一个顺序映射，则必须计算排序顺序（费用很高）。

通常情况下，如果需要快速添加单个键/值对和快速查找单个键，最好使用HashMap。如果需要更快的顺序遍历，并且能够负担额外的插入成本，可以使用SkipListMap。

ConcurrentSkipListMap通过随机数来保持平衡。

4.4 LinkedHashMap

问：LinkedHashMap用过吗？讲一下？存进集合如何比较大小保证顺序？

答：用过，LinkedHashMap会在每次访问元素后把元素放置到节点链表的尾部，也就记录了链表的访问顺序，可以用来实现LRU。

重写removeEldestEntry方法，使其判断当此时链表达到限制地阈值大小时，返回true，这样put方法被调用时会自动删除最老元素即此时链表的首节点。

LinkedHashMap是HashMap的一种特殊分支，是某种有序的hashMap，和TreeMap是不一样的概念，是用了HashMap+链表的方式来构造的，有两者有序模式：访问有序，插入顺序，插入顺序是一直存在的，因为是调用了hashMap的put方法，并没有重载，但是重载了newNode方法，在这个方法中，会把节点插入链表中，访问有序默认是关闭的，如果打开，则在每次get的时候都会把链表的节点移除掉，放到链表的最后面。这样子就是一个LRU的一种实现方式。

4.5 TreeMap

问：讲讲TreeMap？

TreeMap是Map中的一种很特殊的map，我们知道Map基本是无序的，但是TreeMap是会自动进行排序的，也就是一个有序Map(使用了红黑树来实现），如果设置了Comparator比较器，则会根据比较器来对比两者的大小，如果没有则key需要是Comparable的子类（代码中没有事先check，会直接抛出转化异常，有点坑啊）。
树映射TreeMap，由红黑树实现的有序映射。TreeMap为增、删、改、查这些操作提供了 O(log n) 的时间开销，相比HashMap的 O(1) 存储效率要差些，但查询统计的 O(log n) 比HashMap O(n) 要高效。

Java提高十六：TreeMap深入分析

问：TreeMap查询写入的时间复杂度多少？

TreeMap为增、删、改、查这些操作提供了log(N)的时间开销。