- 3.3.1.集合概述
- 3.3.2.Collection接口
- 3.3.2.1.List接口
- 3.3.2.1.1.迭代器Iterator 是什么?
- 3.3.2.1.2.Iterator怎么使用?有什么特点?
- 3.3.2.1.3.如何边遍历边移除Collection中的元素?
- 3.3.2.1.4.Iterator和ListIterator有什么区别?
- 3.3.2.1.5.说一下ArrayList的优缺点
- 3.3.2.1.6.如何实现数组和List之间的转换
- 3.3.2.1.7.ArrayList与LinkedList的区别
- 3.3.2.1.8.ArrayList 和 Vector 的区别是什么?
- 插入数据时，ArrayList、LinkedList、Vector谁速度较快?阐述ArrayList、Vector、LinkedList 的存储性能和特性?
- 3.3.2.1.9.多线程场景下如何使用ArrayList？
- 3.3.2.1.10.为什么 ArrayList 的 elementData 加上 transient 修饰?
- 3.3.2.1.11.List和Set的区别
- 3.3.2.2.Set接口
- 3.3.2.3.Queue接口
- 3.3.2.1.List接口
- 3.3.3.Map接口
- 3.3.3.1.说一下 HashMap 的实现原理?
- 3.3.3.2.HashMap默认加载因子为什么选择0.75？
- 3.3.3.3.HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现
- 3.3.3.4.HashMap的put方法的具体流程?
- 3.3.3.5.HashMap的扩容操作是怎么实现的?
- 3.3.3.6.HashMap如何解决哈希冲突
- 3.3.3.7.能否使用任何类作为Map的key
- 3.3.3.8.为什么HashMap中String、Integer这样的包装类适合作为K?
- 3.3.3.9.如果使用Object作为HashMap的Key，应该怎么办呢?
- 3.3.3.10.HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标?
- 3.3.3.11.HashMap的长度为什么是2的幂次方
- 3.3.3.12.HashMap 与 HashTable 有什么区别?
- 3.3.3.13.如何决定使用HashMap还是TreeMap
- 3.3.3.14.HashMap和ConcurrentHashMap的区别
- 3.3.3.15.ConcurrentHashMap和HashTable的区别?
- 3.3.3.16.ConcurrentHashMap 底层具体实现知道吗?实现原理是什么?
- 3.3.3.17.ConcurrentHashMap的同步机制
3.3.1.集合概述
3.3.1.1.什么是集合
集合就是一组用于存储数据的容器，任何集合框架都包含三大块内容：对外的接口、接口的实现和集合运算的算法
- 对外的接口：表示接口的抽象数据类型。接口允许我们操作集合时不必关注具体实现，从而达到多态。在java中，接口通常用来定义规范
- 接口的实现：对数据结构进行一个封装
算法：在一个实现来某个集合框架中的接口对象身上完成某种算法，例如查找、排序等。这些算法通常是多态的，因为相同的算法可以在一个接口上被不同的实现
3.3.1.2.集合特点
存储对象：对象封装数据，对象多了也需要存储。集合用于存储对象
可变长度：对象的个数确定可以使用数组，对象的个数不确定的可以用集合
3.3.1.3.集合和数组的区别
数组是固定长度的；集合是可变长度的
- 数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型
数组存储的元素必须是同一数据类型；集合存储的对象可以是不同数据类型
3.3.1.4.使用集合框架的好处
容量自动增长
- 提供来高性能的数据结构和算法，使编码更轻松，提高程序速度和质量
- 允许不同API之间的相互操作，API之间可以来回传递集合；例如list转map等
- 可以方便的扩展或者改写集合，提高代码复用性和可操作性。
- 通过使用JDK自带的集合类，可以降低代码维护和学习API成本
3.3.1.5.常用的集合类有那些
集合的接口可以分为两大类：Map接口和Collection接口，其他接口都是继承自这两个接口
其中Map接口包含：HashMap、TreeMap、HashTable、ConcurrentHashMap已经Propertites等
Collection接口又包含两个个子接口：Set接口、List接口
Set接口主要实现类有：HashSet、TreeSet、LinkedHashSet等
List接口的实现类主要有：ArrayList、LinkedList、Stack、Vector等
3.3.1.6.集合底层数据结构
ArrayList和Vector底层是Object数组；LinkedList底层是双向循环链表
HashSet是基于HashMap实现的，底层采用的是HashMap来保存元素，他保存的数据无序并且唯一
LikedHashSet继承自HashSet，并且其内部通过LinkedHashMap实现。他保存的数据有序，并且唯一
TreeSet底层使用的是红黑树，他保存的数据有序且唯一
HashMap在JDK1.8之前由数组+链表组成，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（拉链法）。JDK1.8之后HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认8）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了 一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作， 实现了访问顺序相关逻辑。
HashTable:是由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap底层使用的是红黑树(自平衡的排序二叉树)
3.3.2.7.哪些集合类是线程安全的?
Vector比Arraylist多了同步机制，底层方法采用synchronized保证线程安全，所以效率低，现在已经不建议使用。
Stack是一个堆栈类，采用先进后出策略，在进行出栈入栈操作时候也使用了synchronized进行同步，所以也是线程安全的。
Hashtable相对于HashMap多了synchronized进行线程同步
3.3.2.8.Java集合的快速失败机制 “fail-fast”?
fail-fast机制其实就是一个java集合的安全保护机制，当多个线程并发情况下对一个集合的结构进行改变的时候，可能会产生fail-fast机制
例如:假设存在两个线程(线程1、线程2)，线程1通过Iterator在遍历集合A中的元素， 在某个时候线程2修改了集合A的结构(是结构上面的修改，而不是简单的修改集合元素的内容)，那么这个时候程序就会抛出ConcurrentModificationException 异常，从而产 生fail-fast机制。
产生原因：
迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用 hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为 expectedmodCount值，是的话就返回遍历;否则抛出异常，终止遍历。
解决办法:
- 在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
- 使用CopyOnWriteArrayList来替换ArrayList
3.3.2.9.怎么确保一个集合不能被修改?
可以使用Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，这样改变集合的任何操作都会抛出 Java.lang. UnsupportedOperationException异常。List list = new ArrayList<>();list. add("x");Collection clist = Collections. unmodifiableCollection(list);clist. add("y"); // 运行时此行报错
3.3.2.Collection接口
3.3.2.1.List接口
3.3.2.1.1.迭代器Iterator 是什么?
Iterator 接口提供遍历任何Collection的接口。我们可以从一个Collection中使用迭代器方法来获取迭代器实例。迭代器取代了Java 集合框架中的 Enumeration，迭代器允许调用者在迭代过程中移除元素。3.3.2.1.2.Iterator怎么使用?有什么特点?
Iterator的特点是只能单向遍历，但是更加安全，因为它可以确保，在当前遍历的集合元素被更改的时候，就会抛出 ConcurrentModificationException 异常。List list = new ArrayList<>();Iterator it = list. iterator();while(it. hasNext()){String obj = it. next();System. out. println(obj);}
3.3.2.1.3.如何边遍历边移除Collection中的元素?
可以使用迭代器的remove方法；将一个Collection对象通过调用iterator方法的方式转换成迭代器，然后通过hasNext方法判断迭代器是否有下一个元素，通过remove方法移除元素。
Iterator<Integer> it = list.iterator();while(it.hasNext()){it.remove();}
3.3.2.1.4.Iterator和ListIterator有什么区别?
- Iterator可以遍历Set和List集合，而ListIterator只能遍历List。
- Iterator只能单向遍历，而ListIterator可以双向遍历(向前/后遍历)。
ListIterator实现Iterator接口，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。
3.3.2.1.5.说一下ArrayList的优缺点
优点：
ArrayList底层以数组实现，是一种随机访问模式。ArrayList实现了RandomAccess接口，因此查找的时候非常快。
- ArrayList 在顺序添加一个元素的时候非常方便。
缺点：
- 删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
- 插入元素时候，也需要进行一次元素复制操作。
3.3.2.1.6.如何实现数组和List之间的转换
- 数组转List:使用 Arrays. asList(array) 进行转换。
List 转数组:使用 List 自带的 toArray() 方法。
3.3.2.1.7.ArrayList与LinkedList的区别
数据结构实现:ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
- 随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
- 增加和删除效率:在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。
- 内存空间占用:LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据， 还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
- 线程安全:ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全;
综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。
3.3.2.1.8.ArrayList 和 Vector 的区别是什么?
这两个类都实现了List接口(List接口继承了Collection接口)，他们都是有序集合
- 线程安全：Vector使用了synchronized来实现线程同步，是线程安全的，而ArrayList是非线程安全的。
- 性能：由于Vector加同步锁的原因，所以ArrayList效率高于Vector
- 扩容：ArrayList和Vector都会根据实际需要动态调整容量，只不过Vector每次扩容都会增加一倍，而ArrayList只会增加50%
插入数据时，ArrayList、LinkedList、Vector谁速度较快?阐述ArrayList、Vector、LinkedList 的存储性能和特性?
ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。
Vector 中的方法由于加了 synchronized 修饰，因此 Vector是线程安全容器，但性能上较ArrayList差。
LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需要记录当前项的前后项即可，所以 LinkedList插入速度较快。3.3.2.1.9.多线程场景下如何使用ArrayList？
ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。
List<String> synchronizedList = Collections.synchronizedList(list);synchronizedList.add("aaa");synchronizedList.add("bbb");for(int i =0; i < synchronizedList.size(); i++){System.out.println(synchronizedList.get(i));}
3.3.2.1.10.为什么 ArrayList 的 elementData 加上 transient 修饰?
ArryayList中数组定义如下：
private transient Object[] elementData;
ArrayList接口的定义
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
可以看到ArrayList实现了Serializable接口，这意味着ArrayList支持序列化。transient的作用是说不喜欢elementData数组被序列化 ，重写了writeObject的实现：
private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// Write out element count, and any hidden stuffint expectedModCount = modCount;s.defaultWriteObject();// Write out size as capacity for behavioural compatibility with clone()s.writeInt(size);// Write out all elements in the proper order.for (int i=0; i<size; i++) {s.writeObject(elementData[i]);}if (modCount != expectedModCount) {throw new ConcurrentModificationException();}}
每次序列化时，先调用default writeObject()，方法序列化ArrayList中的非transient元素，然后遍历elementData,只序列化已存入的元素，这样既加快了序列化速度，又减少了序列化之后的文件大小。
3.3.2.1.11.List和Set的区别
List和Set都是继承自Collection接口
- List是一个有序的容器（插入的元素有序），元素可以重复，并且可以插入多个null元素，每个元素都有索引。常用的实现类有ArrayList、LinkedList和Vector
- Set是一个无序的容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素的唯一性。Set接口常用的实现类有HashSet、LinkedHashSet和TreeSet
- Set集合检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
- List和数组类似，List可以动态增长，查询元素效率高，插入删除元素效率低，因为会引起其他位置改变
3.3.2.2.Set接口
3.3.2.2.1.说一下HashSet的实现原理
HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap 的value统一为是一个Object对象PRESENT声明，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本 上都是直接调用底层 HashMap 的相关方法来完成，HashSet 不允许重复的值。3.3.2.2.2.HashSet如何检查重复?HashSet是如何保证数据不可重复的?
向HashSet 中add ()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结 合equles 方法比较。
HashSet 中的add ()方法会使用HashMap 的put()方法。
HashMap 的 key 是唯一的，由源码可以看出 HashSet 添加进去的值就是作为HashMap的key，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V。 所以不会重复( HashMap 比较key是否相等是先比较hashcode 再比较equals )。private static final Object PRESENT = new Object();private transient HashMap<E,Object> map;public HashSet(){map =newHashMap<>();}public boolean add(E e){// 调用HashMap的put方法，将hashSet的值set到HashSet的键上return map.put(e, PRESENT)==null;}
3.3.2.2.3.HashSet与HashMap的区别
| HashSet | HashMap | | —- | —- | | 实现了Set接口 | 实现了Map接口 | | 仅存储对象 | 存储键值对 | | 调用add（）方法添加元素 | 调用put（）方法添加元素 | | HashSet 使用成员对象来计算 hashcode 值，对 两个对象 来说 hashcode 可能相 同，所以 equals()方法用来判断对象的相等性， 如果两个对象不同的话，那 么返回 false | HashMap使用键（Key）来计算Hashcode | | HashMap获取对象相对HashSet较快，因为他是使用的唯一键获取对象 | |
3.3.2.3.Queue接口
3.3.2.3.1.BlockingQueue是什么?
BlockingQueue是位于java.util.concurrent包下的一个类，他表示一个队列，在进行检索或移除一个元素的时候，他会等待队列变为非空；当在添加一个元素时，它会等待队列中的可用空间。 BlockingQueue接口是Java集合框架的一部分，主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间，或消费者有可用的对象，因为它都在 BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现，比如 ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、 SynchronousQueue等。
3.3.2.3.2.在 Queue 中poll()和remove()有什么区别?
- 相同点:都是返回第一个元素，并在队列中删除返回的对象。
- 不同点:如果没有元素 poll()会返回 null，而 remove()会直接抛出 NoSuchElementException 异常。
3.3.3.Map接口
3.3.3.1.说一下 HashMap 的实现原理?
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
HashMap 基于 Hash 算法实现的
- 当我们往Hashmap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
- 存储时，如果出现hash值相同的key，此时有两种情况。
- (1)如果key相同，则覆盖原始值;
- (2)如果key不同(出现冲突)，则将当前的key-value放入链表中
- 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
3.3.3.2.HashMap默认加载因子为什么选择0.75？
主要是泊松分布，0.75的话碰撞最小，设置0.75有助于提高空间利用率和减少查询成本的折中。
Hashtable 初始容量是11 ，扩容方式为2N+1;
HashMap 初始容量是16,扩容方式为2N;
HashMap有两个参数影响其性能：初始容量和加载因子。
- 容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。
- 加载因子是哈希表在其容量自动扩容之前可以达到多满的一种度量。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行扩容、rehash操作（即重建内部数据结构），扩容后的哈希表将具有两倍的原容量。
通常，加载因子需要在时间和空间成本上寻求一种折衷。
加载因子过高，例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本；
加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数。
在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash操作次数，所以，一般在使用HashMap时建议根据预估值设置初始容量，减少扩容操作。
选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择。
3.3.3.3.HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现
在Java中，保存数据有两种比较简单的数据结构:数组和链表。
- 数组的特点是:寻址容易，插入和删除困难;
- 链表的特点是:寻址困难，但插入和删除容易;
JDK1.8之前采用数组+链表的方式，也就是拉链法。他是创建了一个链表数组，数组中每一格就是一个链表。如果遇到哈希冲突，则将冲突的值加到链表中。
JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值(默认为8)时，将链表转化为红黑树，以减少搜索时间。
JDK1.7与JDK1.8比较
JDK1.8主要解决或优化了一下问题:
- resize 扩容优化
- 引入了红黑树，目的是避免单条链表过长而影响查询效率；
- 解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。
| 不同 | JDK1.7 | JDK1.8 |
| —- | —- | —- |
| 存储结构 | 数组+链表 | 数组+链表+红黑树 |
| 初始化方式 | 单独函数: inflateTable() | 直接集成到了扩容函数resize()中 |
| Hash值的计算方式 | 4次位运算 + 5次异或运算 | 1次位运 算 + 1次异或运算 |
| 存放数据的规则 | 无冲突时,存放到数组;有冲突时,存放链表 | 无冲突时，存放到数组;
有冲突
- 链表长度 < 8:存放单链表;
- 链表长度 > 8:树化并存放红黑树
| | 插入方式 | 头插法 (先讲原位置的数据移到后1 位，再插入数据到该位置) | 尾插法 (直接插入到链表尾部/红黑树) | | 扩容后存储位置的计算方式 | 全部按照原来方法进行计算 (即 hashCode ->> 扰动函数 ->> (h&lengt h-1)) | 按照扩容后的规律计算(即扩容后的位置=原位置 or 原位 置 + 旧容 量) |
3.3.3.4.HashMap的put方法的具体流程?
当我们put的时候，首先计算 key的hash值，这里调用了 hash方法，hash方法实际是让 key.hashCode()与key.hashCode()>>>16进行异或操作，高16bit补0，一个数和0异或不变， 所以 hash 函数大概的作用就是:高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O(logn)的树结构来提升碰撞下的性能。 putVal方法执行流程图
当调用put方法时候，HashMap会首先对传入的key进行一个哈希运算，运算的方法其实就是，如果key是null，那么设置成0，如果不是空，那么就让key的hashcode值与key的hashcode无符号右移之后的值做异或运算，目前就是为了减少碰撞。当得到key的哈希地址之后，开始进行put操作：首先会判断是不是第一次进行map操作，如果是的话，那么会初始化table的值（通常是2的幂）；如果不是第一次调用，那么会判断当前key节点经过hash运算之后的位置有没有值，如果有值，那么用一个新的节点e来记录当前这个值。然后开始解决hash冲突，进行判断当前解决冲突的类型，如果是TreeNode，也就是红黑树，那么放入树中，如果不是那么放入链表当中，在放入链表时候进行判断，当前链表长度是否超过8，如果超过，那么链表转换成红黑树；最后判断HashMap中的容量是否足够，是否需要扩容。
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}//实现Map.put和相关方法final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 步骤①：tab为空则创建// table未初始化或者长度为0，进行扩容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 步骤②：计算index，并对null做处理// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 桶中已经存在元素else {Node<K,V> e; K k;// 步骤③：节点key存在，直接覆盖value// 比较桶中第一个元素(数组中的结点)的hash值相等，key相等if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 将第一个元素赋值给e，用e来记录e = p;// 步骤④：判断该链为红黑树// hash值不相等，即key不相等；为红黑树结点// 如果当前元素类型为TreeNode，表示为红黑树，putTreeVal返回待存放的node, e可能为nullelse if (p instanceof TreeNode)// 放入树中e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 步骤⑤：该链为链表// 为链表结点else {// 在链表最末插入结点for (int binCount = 0; ; ++binCount) {// 到达链表的尾部//判断该链表尾部指针是不是空的if ((e = p.next) == null) {// 在尾部插入新结点p.next = newNode(hash, key, value, null);//判断链表的长度是否达到转化红黑树的临界值，临界值为8if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//链表结构转树形结构treeifyBin(tab, hash);// 跳出循环break;}// 判断链表中结点的key值与插入的元素的key值是否相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 相等，跳出循环break;// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表p = e;}}//判断当前的key已经存在的情况下，再来一个相同的hash值、key值时，返回新来的value这个值if (e != null) {// 记录e的valueV oldValue = e.value;// onlyIfAbsent为false或者旧值为nullif (!onlyIfAbsent || oldValue == null)//用新值替换旧值e.value = value;// 访问后回调afterNodeAccess(e);// 返回旧值return oldValue;}}// 结构性修改++modCount;// 步骤⑥：超过最大容量就扩容// 实际大小大于阈值则扩容if (++size > threshold)resize();// 插入后回调afterNodeInsertion(evict);return null;}
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
3.3.3.5.HashMap的扩容操作是怎么实现的?
1.在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用 resize方法进行扩容;
2.每次扩展的时候，都是扩展2倍;
3.扩容的场景：第一次put之后，还有就是插入完之后，也要判断是否需要扩容
扩容的方法：
- 1、首先计算出新数组长度和新出租扩容阈值，创建新数组
- 2、扩容前数组元素迁移到扩容后的数组当中去。主要分为：单个元素迁移，链表的迁移，红黑树迁移
final Node<K,V>[] resize() {/*** oldTab: 扩容之前的数组* oldCap：扩容之前的数组长度*/Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;/*** newCap：新数组长度* newThr： 新数组的扩容阈值*/int newCap, newThr = 0;// 下面主要是计算出newCap，newThr的值，算出来后，再进行数组的迁移if (oldCap > 0) { // 数组已经初始化过// 数组长度已经达到最大值，则不扩容了，设置扩容条件为最大值if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}/*** 老数组长度扩大1倍，赋值给新数组长度的变量* 赋值后判断是否小于长度最大值，并且老数组长度要大于16* 满足以上条件，新数组扩容阈值为扩容之前的2倍*/else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY) // 扩容之前的数组长度大于等于16newThr = oldThr << 1; // double threshold 双倍扩容阈值}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}
扩容其实就是分为两大步，第一步就是计算新数组的长度和阈值，第二步就是将老数组中的元素、链表、红黑树进行迁移 hashMap会首先创建两个变量，记录老数组的长度和阈值，然后根据规则创建新数组的长度和扩容阈值。比如：
- 已经初始化过的数组
- 扩容之前的数组长度如果已经达到最大值，那么就不扩容了，直接设置扩容条件为最大值，并且返回原来的值
- 老数组的长度如果大于16，并且扩大一倍后容量满足，按摩直接扩大一倍
- 如果老数组的扩容阈值大于0，则把老数组的扩容阈值赋值给新数组的长度
- 如果老数组的长度和老数组的扩容阈值都是0的时候，那就设置默认值数组长度是16，阈值是16*0.75
- 如果老数组不为空
- 循环遍历数组中的每一个元素，如果是单个元素，先把下标值设置为null，方便jvm回收，然后直接迁移到新数组
- 如果是链表，则有高位链和低位链，首先算出当前节点是高位链0还是1，如果是0，则把当前节点放入低位链，如果是1，则把当前节点放入高位链
- 链表遍历完成之后，判断高低位链表是否为null
- 低位链不为null，则设置低位链的next为null，然后新数组的同一个下标指向这个低位链
- 高位链不为null，把高位链的next设置为null，然后新数组的下标位置指向该高位链
3.3.3.6.HashMap如何解决哈希冲突
什么是哈希
简单说就是一种将任意长度的消息压缩到某一个固定长度消息摘要的函数； 哈希函数有如下特性：
- 根据同一个散列函数计算出来的散列值如果不同，那么输入值肯定也不同
- 根据同一个散列函数计算出来的散列值相同，输入值不一定相同
什么是哈希冲突
当两个不同输入值，根据同一个散列函数计算出相同散列值的现象，就叫做哈希冲突
解决方法
- 链地址法
将相同哈希值的数据组织成一个链表，放在hash值对应的bucket下；但是这种方式有一个缺点：我们HashMap的初始容量是1<<4也就是2的四次方16，这个值要远小于int类型的范围，所以如果单纯使用hashCode取余来获取对应的bucket将会大大增加哈希碰撞的概率，最坏的情况下，HashMap将会变成一个单链表
- 链地址法+扰动函数
主要是优化了hash函数，如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位没有起到作用，所以优化的思路就是让高位参与运算，进一步降低hash碰撞的概率，使数据分布更均匀，也就是扰动操作
static final int hash(Object key){int h;return(key == null)?0:(h = key.hashCode())^(h >>>16);// 与自己右移16位进行异或运算}
- 链地址法+扰动函数+红黑树
链地址法和扰动函数使得数据分布更平均，一定程度减少哈希碰撞，但是当存在大量数据时候，加入我们某个bucket下对应的链表就有链n个元素，遍历复杂度位O（n）,为了针对这个问题，JDK1.8中引入了红黑树，当链表长度大于8的时候将会转换为红黑树
3.3.3.7.能否使用任何类作为Map的key
可以使用任何类作为Map的key，但是前提是，这个类重写了equals方法和hashCode方法
3.3.3.8.为什么HashMap中String、Integer这样的包装类适合作为K?
首先他们都是包装类型，根据包装类型的特性，他们都是被final修饰的类，保证了key的不可改变性，不会存在获取hash值不同的情况，而且他们内部已经重写了equals和hashCode方法，遵守了HashMap内部的规范，不会出现Hash值计算错误的情况。
3.3.3.9.如果使用Object作为HashMap的Key，应该怎么办呢?
需要重写hashCode和equals方法，重写HashCode是因为需要计算存储数据的存储位置，重写equals目的是为了保证key在哈希表中的唯一性。
3.3.3.10.HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标?
hashCode方法返回的值是int类型，int的范围是正负21亿，大约有40个亿的空间。而HashMap的容量范围是16～2^30,HashMap通常情况下是取不到最大值，并且设备上也很难提供这么大的空间。从而导致通过hashCode计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置。
解决方法：
HashMap实现了自己的hash方法，通过两次扰动使他自己的高低位哈希值进行异或运算，降低哈希碰撞概率，也使得数据分布更平均； 保证数组长度为2的幂次方的时候，使用hash运算之后的值与运算（数组长度-1）来获取数组下标的方式进行存储，这么做的原因一是比取余操作更加有效率，二是因为只有数组长度为2的幂次方时，h&(length-1)才等价于h%length，第三点是解决来哈希值余数组大小范围不匹配的问题。
3.3.3.11.HashMap的长度为什么是2的幂次方
这其实和HashMap本身经过哈希运算之后获取数组下标有关系。通过两次扰动，使key的哈希值的高低位进行异或运算使数据分布更均匀。而要获取真正的数组下标除了使用哈希值取余之外，HashMap采用了一种更加优化的方法，那就是经过哈希运算之后的值和（数组长度-1）进行与运算，这种方式由于是位运算，所以比取余效率高，但是有一个局限性，只有数组长度是2的幂次方时候，取余操作的结果才和这个操作的值相等。
为什么是两次扰动
这样加大哈希值低位随机性使得分布均匀，从而提高对应数组存储下标位置的随机性和均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的。
3.3.3.12.HashMap 与 HashTable 有什么区别?
- 1、线程安全：HashMap是非线程安全的，HashTable是线程安全的；HashTable内部的方法基本都经过synchronized修饰。
- 2、效率不同：因为线程安全问题，HashMap比HashTable效率高一些。
- 3、HashMap中null可以作为键，这样的键只能有一个，可以有一个或多个键对应的值为null。但是在HashTable中put进的键如果有null，直接抛出空指针异常
- 4、他们的初始容量和每次扩容大小也不同：
- 创建时不指定容量初始值：HashTable的初始容量是11，之后每次扩容都变为原来的2n+1。HashMap默认的初始化大小是16，之后每次扩容容量都变成原来的2倍。
- 创建时指定容量初始值，那么HashTable会直接使用使用指定的大小，而HashMap会将其扩充为2的幂次方大小。
- 5、他们的底层数据结构不同：1.8以后HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认8）时，将链表转换为红黑树，以减少搜索时间。HashTable没有这样的机制
- 6、在HashTable的类注释可以看到，HashTable是保留类，不建议使用，推荐在单线程环境下使用HashMap替代，如果需要多线程使用则用ConcurrentHashMap替代。‘
3.3.3.13.如何决定使用HashMap还是TreeMap
对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你 需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大 小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。
3.3.3.14.HashMap和ConcurrentHashMap的区别
- 1、ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的synchronized锁的粒度更精细了一 些，并发性能更好，而HashMap没有锁机制，不是线程安全的。(JDK1.8之后 ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。)
2、HashMap的键值对允许有null，但是ConCurrentHashMap都不允许
3.3.3.15.ConcurrentHashMap和HashTable的区别?
ConcurrentHashMap和HashTable主要区别体现在实现线程安全的方式上不同。
1、底层数据结构不同：JDK1.7和ConcurrentHashMap底层采用的是分段数组+链表实现。JDK1.8采用数据结构跟HashMap1.8的结构一样，数组+链表+红黑树。HashTale和JDK1.8之前的HashMap的底层数据结构类似，都是采用数组+链表的形式，数组是实现HashMap的主体，链表则是主要为了解决哈希冲突而存在；
- 2、实现线程安全的方式：
- 1、在JDK1.7的时候，ConcurrentHashMap使用的是分段锁，对整个桶数组进行了分割分段（Segment），每一把锁只锁一个容器的一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率（默认分配16哥Segment，比HashTable效率提高了16倍）。到了JDK1.8的时候，摒弃了Segment的概念，而是直接使用Node数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作。（JDK1.6以后对synchronized锁做了很多优化）整个看起来就像是优化过的HashMap，虽然在JDK1.8中还能看Segment数据结构，但是已经简化了属性，只是为了兼容旧版本；
- 2、HashTable使用的是同步锁synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用put添加元素，另一个线程不能使用put添加元素，也不能使用get，竞争会越来越激烈，效率越来越低。
两者对比图
- HashTable
- JDK1.7的ConcurrentHashMap:
JDK1.8的ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点): 
ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没 有考虑同步，HashTable 考虑了同步的问题。但是 HashTable在每次同步执行时都要锁住整个结构。 ConcurrentHashMap锁的方式是稍微细粒度的。
3.3.3.16.ConcurrentHashMap 底层具体实现知道吗?实现原理是什么?
在JDK1.7中，他是将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。他底层使用的是Segment+HashEntry的方式进行实现的：一个ConcurrentMap里边包含了一个Segment数组。Segment的结构和HashMap类似就是一种数组+链表的结构，一个Segment包含了一个HashEntry数组，每个HashEntry是一个链表结构的元素，每一个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得对应的Segment的锁。
ConcurrentHashMap类说明：
- 该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对，后者用来充当锁的角色;
- Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个 HashEntry 数组里得元素，当对 HashEntry 数组的数据进行修改时，必须首先获得 对应的 Segment 锁。
在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采用Node+CAS+Synchronized来保证并发安全进行实现，Synchronized只锁当前链表或者红黑二叉树的首节点，这样只要Hash不冲突，就不会产生并发，效率提升n倍。
源码：
public V put(K key, V value) {return putVal(key, value, false);}
/**将指定的键映射到此表中的指定值。键和值都不能为空。可以通过使用与原始键相同的键调用 {get 方法来检索该值。@param key 与指定值关联的键@param value 与指定键关联的值@return 与 key 关联的前一个值，如果 key没有映射，则为 null@throws NullPointerException 如果指定的键或值为空*/public V put(K key, V value) {return putVal(key, value, false);}final V putVal(K key, V value, boolean onlyIfAbsent) {//如果key或者value为空抛出异常if (key == null || value == null) throw new NullPointerException();// 计算hash 值int hash = spread(key.hashCode());// 用来记录所在table数组中的桶的中链表的个数，后面会用于判断是否链表过长需要转红黑树int binCount = 0;//for循环用break跳出for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;// 如果数组"空"，进行数组初始化if (tab == null || (n = tab.length) == 0)// 初始化tabletab = initTable();//i为下标，用(数组长度-1)&hash值计算得出//调用tabAt()获取数组中该下标对应的元素//如果这位置为空else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// 使用CAS 操作将这个新值(将新值放入结点，再将结点放入期中)即可// 如果 CAS 失败，那就是有并发操作，继续循环if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))break; // no lock when adding to empty bin}// 如果头结点hash值为-1，则为ForwardingNode结点，说明正在扩容else if ((fh = f.hash) == MOVED)// 帮助数据迁移，这个等到看完数据迁移部分的介绍后，再理解这个就很简单了tab = helpTransfer(tab, f);else { // 到这里就是说，f 是该位置的头结点，而且不为空V oldVal = null;// 获取数组该位置的头结点的监视器锁，锁住头结点synchronized (f) {//双重检测锁，检测加锁前是否被修改if (tabAt(tab, i) == f) {if (fh >= 0) { // 头结点的 hash 值大于 0，说明是链表// 用于累加，记录链表的长度binCount = 1;// 遍历链表for (Node<K,V> e = f;; ++binCount) {K ek;// 如果发现了"相等"的 key，判断是否要进行值覆盖，然后跳出循环if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {oldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}// 没发现相等的key，到了链表的最末端，将这个新值放到链表的最后面Node<K,V> pred = e;if ((e = e.next) == null) {pred.next = new Node<K,V>(hash, key,value, null);break;}}}else if (f instanceof TreeBin) { // 红黑树Node<K,V> p;binCount = 2;// 调用红黑树的插值方法插入新节点if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}}//如果链表的长度不为0if (binCount != 0) {// 判断是否要将链表转换为红黑树，临界值和 HashMap 一样，也是 8if (binCount >= TREEIFY_THRESHOLD)// 这个方法和 HashMap 中稍微有一点点不同，那就是它不是一定会进行红黑树转换，// 如果当前数组的长度小于 64，那么会选择进行数组扩容，而不是转换为红黑树treeifyBin(tab, i);if (oldVal != null)//返回旧值return oldVal;break;}}}// 计数器加1，完成新增后，table扩容，就是这里面触发addCount(1L, binCount);//新增后返回空return null;}
扩容：
1.每次添加完后，调用的addCount中有调用transfer扩容
2.桶中链表大于8调用treeifyBin方法转红黑树的方法的时候，在该方法中会判断table当前总容量是否大于64，如果table当前总容量小于64，不会转红黑树，而是调用tryPresize方法尝试扩容，tryPresize方法中会调用transfer扩容
扩容怎么保证线程安全
1.多个线程都做扩容的时候，由字段transferIndex表示当前已分配的桶到什么下标了，对transferIndex字段的修改是用的CAS，每个线程先获取自己处理哪个区间的桶，每个线程自己迁移自己的桶，互不打扰。一个线程最少处理16个桶。
比如，现在数组长度为32，线程A迁移0-15的桶，线程B迁移16-31的桶。当前哪些区间的桶被分配的的临界值是transferIndex表示，对它的修改是CAS的，所以多线程扩容线程安全
2.如果有线程去写concurrenthashmap，发现现在正在扩容，则去帮组扩容。如果有线程去读，发现正在扩容，则通过桶上的forwdingNode去新的map中去读。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {int n = tab.length, stride;// stride 在单核下直接等于 n，多核模式下为 (n>>>3)/NCPU，最小值是 16（每个做扩容的线程至少处理16个桶）if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)stride = MIN_TRANSFER_STRIDE; // subdivide range//如果nextTab为空，新建一个是原来2倍长度的nextabif (nextTab == null) {try {// 容量翻倍Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];nextTab = nt;} catch (Throwable ex) { // try to cope with OOMEsizeCtl = Integer.MAX_VALUE;return;}// nextTable 是 ConcurrentHashMap 中的属性nextTable = nextTab;// transferIndex 也是 ConcurrentHashMap 的属性，用于控制迁移的位置transferIndex = n;}int nextn = nextTab.length;// ForwardingNode 翻译过来就是正在被迁移的 Node// 这个构造方法会生成一个Node，key、value 和 next 都为 null，关键是 hash 为 MOVED// 后面我们会看到，原数组中位置 i 处的节点完成迁移工作后，// 就会将位置 i 处设置为这个 ForwardingNode，用来告诉其他线程该位置已经处理过了// 所以它其实相当于是一个标志。ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);// advance 指的是做完了一个位置的迁移工作，可以准备做下一个位置的了boolean advance = true;//所有桶是否都已迁移完成boolean finishing = false; // to ensure sweep before committing nextTab/** 下面这个 for 循环，最难理解的在前面，而要看懂它们，应该先看懂后面的，然后再倒回来看**/// i 是位置索引，bound 是边界，注意是从后往前for (int i = 0, bound = 0;;) {Node<K,V> f; int fh;//这个while是给当前线程分配迁移任务，即它负责迁移哪几个桶，它要处理的桶的下标范围while (advance) {int nextIndex, nextBound;if (--i >= bound || finishing)advance = false;//用CAS设置transfer减去已分配的桶，并发扩容保证线程安全，每个扩容的线程根据这个字段扩容自己分配到区间的桶，各不干扰else if ((nextIndex = transferIndex) <= 0) {i = -1;advance = false;}else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ?nextIndex - stride : 0))) {// /确定当前线程每次分配的待迁移桶的范围为[bound, nextIndex)bound = nextBound;i = nextIndex - 1;advance = false;}}if (i < 0 || i >= n || i + n >= nextn) {int sc;if (finishing) {// 所有的迁移操作已经完成nextTable = null;// 将新的 nextTab 赋值给 table 属性，完成迁移table = nextTab;// 重新计算 sizeCtl: n 是原数组长度，所以 sizeCtl 得出的值将是新数组长度的 0.75 倍sizeCtl = (n << 1) - (n >>> 1);return;}// 之前我们说过，sizeCtl 在迁移前会设置为 (rs << RESIZE_STAMP_SHIFT) + 2//当前线程已结束扩容，sizeCtl-1表示参与扩容线程数-1if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {//确定当前线程每次分配的待迁移桶的范围为[bound, nextIndex)if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)return;// 到这里，说明 (sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT，// 也就是说，所有的迁移任务都做完了，也就会进入到上面的 if(finishing){} 分支了finishing = advance = true;i = n; // recheck before commit}}// 如果位置 i 处是空的，没有任何节点，那么放入刚刚初始化的 ForwardingNode ”空节点“else if ((f = tabAt(tab, i)) == null)advance = casTabAt(tab, i, null, fwd);// 该位置处是一个 ForwardingNode，代表该位置已经迁移过了else if ((fh = f.hash) == MOVED)advance = true; // already processedelse {// 对数组该位置处的结点加锁，开始处理数组该位置处的迁移工作synchronized (f) {if (tabAt(tab, i) == f) {Node<K,V> ln, hn;// 头结点的 hash 大于 0，说明是链表的 Node 节点if (fh >= 0) {// 下面这一块和 Java7 中的 ConcurrentHashMap 迁移是差不多的，// 需要将链表一分为二，// 找到原链表中的 lastRun，然后 lastRun 及其之后的节点是一起进行迁移的// lastRun 之前的节点需要进行克隆，然后分到两个链表中int runBit = fh & n;Node<K,V> lastRun = f;for (Node<K,V> p = f.next; p != null; p = p.next) {int b = p.hash & n;if (b != runBit) {runBit = b;lastRun = p;}}if (runBit == 0) {ln = lastRun;hn = null;}else {hn = lastRun;ln = null;}for (Node<K,V> p = f; p != lastRun; p = p.next) {int ph = p.hash; K pk = p.key; V pv = p.val;if ((ph & n) == 0)ln = new Node<K,V>(ph, pk, pv, ln);elsehn = new Node<K,V>(ph, pk, pv, hn);}// 低位链表放在i处setTabAt(nextTab, i, ln);// 高位链表放在i+n处setTabAt(nextTab, i + n, hn);// 将原数组该位置处设置为ForwardingNode，代表该位置已经处理完毕，// 其他线程一旦看到该位置的 hash 值为 MOVED，就不会进行迁移了setTabAt(tab, i, fwd);// advance 设置为 true，代表该位置已经迁移完毕advance = true;}// 红黑树的迁移else if (f instanceof TreeBin) {TreeBin<K,V> t = (TreeBin<K,V>)f;TreeNode<K,V> lo = null, loTail = null;TreeNode<K,V> hi = null, hiTail = null;int lc = 0, hc = 0;for (Node<K,V> e = t.first; e != null; e = e.next) {int h = e.hash;TreeNode<K,V> p = new TreeNode<K,V>(h, e.key, e.val, null, null);if ((h & n) == 0) {if ((p.prev = loTail) == null)lo = p;elseloTail.next = p;loTail = p;++lc;}else {if ((p.prev = hiTail) == null)hi = p;elsehiTail.next = p;hiTail = p;++hc;}}// 如果一分为二后，节点数少于 8，那么将红黑树转换回链表ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :(hc != 0) ? new TreeBin<K,V>(lo) : t;hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :(lc != 0) ? new TreeBin<K,V>(hi) : t;// 将 ln 放置在新数组的位置 isetTabAt(nextTab, i, ln);// 将 hn 放置在新数组的位置 i+nsetTabAt(nextTab, i + n, hn);// 将原数组该位置处设置为 fwd，代表该位置已经处理完毕，// 其他线程一旦看到该位置的 hash 值为 MOVED，就不会进行迁移了setTabAt(tab, i, fwd);// advance 设置为 true，代表该位置已经迁移完毕advance = true;}}}
treeifyBin()链表转红黑树
private final void treeifyBin(Node<K,V>[] tab, int index) {// b表示需要转换为红黑树的那个桶在数组中的下标Node<K,V> b; int n, sc;// 如果table不为空if (tab != null) {// 如果table长小于64，调用tryPresize扩容，而不是转换为红黑树if ((n = tab.length) < MIN_TREEIFY_CAPACITY)// 调用tryPresize扩容tryPresize(n << 1);// 开始进行转换为红黑树// 得到要转换为红黑树的链表的头节点，如果头节点不为空，并且头节点的hash >= 0else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {// 锁住头节点synchronized (b) {// 双重锁检查，以防在锁之前又被其他线程改变了该桶头节点的内容if (tabAt(tab, index) == b) {// hd表示红黑树的根节点// tl表示preNodeTreeNode<K,V> hd = null, tl = null;// 遍历链表for (Node<K,V> e = b; e != null; e = e.next) {// 把链表中的每个Node包装为TreeNodeTreeNode<K,V> p =new TreeNode<K,V>(e.hash, e.key, e.val,null, null);if ((p.prev = tl) == null)// 确定红黑树的根节点hd = p;else// 还是要维护next指针tl.next = p;tl = p;}//用TreeBin<K,V>包装红黑树的根节点，并放入到数组的桶中setTabAt(tab, index, new TreeBin<K,V>(hd));}}}}}
get操作
get操作是无锁的。即使TreeBin的find函数有可能会加TreeBin的内部读锁，但也是非阻塞的。
public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;// 得到key的哈希值int h = spread(key.hashCode());// 如果tabele不为空，并且tab.length大于0，得到桶的头节点不为空if ((tab = table) != null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) != null) {// 桶的头节点的哈希值等于要get的key的哈希值if ((eh = e.hash) == h) {//桶的头节点的key等于要get的keyif ((ek = e.key) == key || (ek != null && key.equals(ek)))//那么桶的头节点就是我们要get的节点，直接返回头节点的valuereturn e.val;}// 桶的头节点的哈希值小于0，表示在红黑树上或者正在扩容else if (eh < 0)return (p = e.find(h, key)) != null ? p.val : null;// 这里表示在桶的链表上// 遍历该桶的链表找到get的节点，返回节点的valuewhile ((e = e.next) != null) {if (e.hash == h &&((ek = e.key) == key || (ek != null && key.equals(ek))))return e.val;}}return null;}
这里可以看到get方法是没有加锁的。Node中的value和nextNode定义的时候用了volatile来保证可见性和有序性
3.3.3.17.ConcurrentHashMap的同步机制
ConcurrentHashMap同步机制的核心其实就是：读读不互斥、读写不互斥、写写互斥
- 读读不互斥
整个get方法是没有锁的，无论是synchronized锁还是JUC包中的那些Lock都没有。
读的时候分两种情况：
- 桶内只是链表，直接遍历链表读了。无任何锁性质的东西。
- 桶内有红黑树，在TreeBin的find方法中操作，是读读同时进行的时候，用红黑树查找。这里用CAS设置LockState字段，不要去理解成成读读互斥了，并不是一个线程读完了才能让另一个线程读，是只有把lockState字段增加这个操作本身互斥而已。
举个例子：
两个线程同时读，A线程用CAS设置了LockState字段为读后，A开始真的做读操作。B线程并不需要等A读完才能读，B线程只需要等A设置完LockState字段后，自己就能去设置LockState字段了然后开始读了。
- 读写不互斥
虽然写方法put会用synchronized去锁桶内头节点/红黑树的根节点，但是：读方法get没有任何锁性质的东西，不需要获取桶内头节点的synchronized锁
读方法细分：
1.桶内只是链表，直接遍历链表读了。无任何锁性质的东西。
2.桶内有红黑树，在TreeBin的find方法中操作，是读写同时进行的时候，用链表方式查找。
- 写写互斥
写和写并发的时候肯定是互斥的，一个线程在写的时候用synchronized对桶内头节点/红黑树的根节点加锁，另一个线程要写同一个桶，首先要用synchronized获取锁，此时只有等待，等正在写的线程写完后释放锁，再去竞争资源
若有收获，就点个赞吧
0 人点赞
