参考

https://www.nowcoder.com/discuss/593247
https://www.nowcoder.com/discuss/589336
https://blog.csdn.net/qq_36520235/article/details/82417949
https://thinkwon.blog.csdn.net/article/details/104588551
https://blog.csdn.net/Hacker_ZhiDian/article/details/85270407

Java集合

Java的集合

Java 的集合也称为容器，是用来存放数据的容器，集合存放的只能是引用数
据类型的数据，也就是对象（如果存入基本数据类型的数据，会自动装箱成
包装类）。集合的好处如下

1. 集合的长度是可变的
2. 集合可以存放不同类型的对象
3. Java 为每个基本数据类型都提供了一个包装类，这样我们就可以像操作对
   象那样来操作基本数据类型
4. 集合为我们提供了多种数据结构和操作的API，选用合适的集合，能够提
   程序性能和开发效率

List，Set，Map的区别

1. List：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可
   以重复，可以插入多个null元素，元素都有索引
2. Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元
   素，只允许存入一个null元素，必须保证元素唯一性
3. Map：是一个键值对集合，存储键、值和之间的映射。Key无序唯一，value
   不要求有序，允许重复。Map没有继承于Collection接口，从Map集合中检索
   元素时，只要给出键对象，就会返回对应的值对象

常用的集合类

在Java 中除了以Map 结尾的类之外，其他类都实现了Collection 接口

1. Collection接口的子接口包括 Set接口、List接口，提供了线性类型和
   一般集合类型的集合的通用接口方法，比如add remove contain等方法

• Set接口的实现类主要有 HashSet、TreeSet、LinkedHashSet等，没有新
  增任何方法，集合有三个特性：无序、有限、无重复
• List接口的实现类主要有 ArrayList、LinkedList、Stack以及Vector等
  。新增排序方法sort(Comparator c)，并且增加了按照下标添加、修改和删
  除元素的方法

2. Map接口的实现类有 HashMap、TreeMap、Hashtable、LinkedHashMap、
   ConcurrentHashMap。其提供了两种不同类型的数据对象进行相互关联的能
   力，也就是键值对。Map 中通过Map.Entry 接口来描述这种类型的元素，
   Entry 接口代表一个key-value对（键值对）形成的数据结构，即为映射
   元素。这个接口中有获取键和值的方法，在 Map(HashMap)正是通过实现
   了这个接口的类对象来储存键值对的信息。Map 中添加键值对和通过key
   获取键值对的方法，还有一个entrySet 方法返回一个包含了所有键值
   对对象的集合类型对象

Iterable接口是什么？

Iterable 接口实际上是Java 集合中最顶级的接口，Collection接口直接继承
了这个接口。Map没有直接继承这个接口，但是可以通过Map的KeySet来遍历Map
。Iterable接口有一个产生迭代器Iterator 的方法，其作用就是提供了统一的
方法接口来方便我们遍历容器。对List接口，它是可以产生一个ListIterator
对象，而这个接口也是继承于Iterator接口，提供了向前访问和向后访问两种
方式

Iterator是什么？有什么特点？

Iterator是一个迭代器，迭代器是一种模式，它可以使得对于序列类型的数据
结构的遍历行为与被遍历的对象分离，作用是迭代器给我们提供了统一的接口
来遍历实现了迭代器接口的类的对象，实现了遍历集合方法的复用，减少我们
的代码量。
这个接口有三个方法。如果类本身也实现了Iterator 接口，那么iterator方
法可直接返回this，注意在使用foreach之后需要重置迭代器位置，也证明
了foreach确实是通过迭代器实现的

1. next()：返回序列中的下一个元素

   //lastRet是返回值的索引，一开始是-1
   checkForComodification();
   i=cursor;
   if(i>=size)
   	throw ..;
   ...
   cursor=i+1;
   return elementData[lastRet=i];
   
   final void checkForComodification() {
           if (modCount != expectedModCount)
           throw new ConcurrentModificationException();
       }

2. hasNext()：检查序列中是否还有元素

   //cursor是一个游标，初始值是0，表示第几次
   return cursor!=size;

3. 使用remove()：将迭代器新返回的元素删除

   public void remove() {
              if (lastRet < 0)
                  throw new IllegalStateException();
              checkForComodification();
              try {
                  ArrayList.this.remove(lastRet);
                  cursor = lastRet;
                  lastRet = -1;
                  //注意这里更新
                  expectedModCount = modCount;
              } catch (IndexOutOfBoundsException ex) {
                  throw new ConcurrentModificationException();
              }
          }
          final void checkForComodification() {
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
          }
   	//集合类自身也有删除方法
          public E remove(int index) {
          rangeCheck(index);
          modCount++;
          E oldValue = elementData(index);
          int numMoved = size - index - 1;
          if (numMoved > 0)
              System.arraycopy(elementData, index+1, elementData, index,
                               numMoved);
          elementData[--size] = null; // clear to let GC do its work
          return oldValue;
      }

Iterator和foreach遍历集合的区别？

1. Iterator 和 foreach 都可以遍历集合
2. foreach 不可以在遍历的过程中删除元素，不然会出现并发修改异常，
   其实是基于快速失败机制
3. 使用 Iterator遍历集合时，可以删除集合中的元素，这里的删除集合
   是指可以用Iterator来删除集合元素而不是集合本身的删除方法

foreach的实现原理是什么？

foreach的实现原理是编译器将遍历直接转换成了对集合iterator.next()
的调用（可以使用foreach进行遍历集合都实现了Iterable接口），所以如
果自定义类实现了Iterable接口并且实现了该接口中iterator()方法的具
体定义，则可以通过foreach语法来遍历自定义的类。区别如下

1. foreach 不可以在遍历的过程中使用集合的删除方法删除元素，在获取
   iterator时会将expectedModCount初始化为记录版本变量的modCount，
   当通过iterator的remove方法删除时，本质也是通过调用集合的删除方法
   ，但是删除时候会更新expectedModCount，而直接使用集合的删除方法不
   会更新expectedModCount，所以下一次删除或遍历时就会抛出异常
2. 而迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个
   modCount变量。集合在被遍历期间如果内容发生变化，就会改变modCount
   的值。当迭代器使用 remove()/next() 遍历下一个元素之前，都会检测
   modCount变量是否为expectedModCount值，是的话就返回遍历，否则抛
   出异常，终止遍历。

Iterator和ListIterator有什么区别？

1. Iterator可以遍历Set和List集合，而ListIterator只能遍历List
2. Iterator只能单向遍历，而ListIterator可以双向遍历（向前/后遍历）
3. ListIterator 实现 Iterator 接口，然后添加了一些额外的功能，
   比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置

什么是快速失败（fast-fail）机制？

快速失败是Java集合的一种错误检测机制，在多线程和单线程环境下都有可
能出现快速失败。

1. 使用迭代器遍历，在遍历过程中，刻意在某一步迭代中remove一个元素
2. 当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast
   。比如一个线程对集合进行迭代，另一个线程对集合进行删除元素的操作

如何防止快速失败？

1. 在单线程的遍历过程中，如果要进行remove操作，调用迭代器的remove
   方法而不是集合类的remove方法
2. 使用JUC 中的线程安全类来替代，比如使用 CopyOnWriteArrayList来
   替代ArrayList，使用ConcurrentHashMap 来替代HashMap 。concurrent
   包下的容器都是安全失败的，可以在多线程下并发使用和并发修改。安全失
   败方式遍历的容器有ConcerrentHashMap和CopyOnWriteArrayList等

什么是安全失败机制？

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是
先复制原有集合内容，在拷贝的集合上进行遍历。由于迭代时是对原集合的拷
贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到
，所以不会触发ConcurrentModificationException

什么情况下modCount会增加？

add和remove方法修改数组会增加modCount，set方法不会增加modcount
，modCountb表示结构上面的修改，而不是简单的修改集合元素的内容

怎么确保一个集合不能被修改？

1. 可以使 Collections.unmodifiableCollection(Collection c)方法
   来创建一个只读集合，因为它不是将原本的比如list集合对象增加了限制不
   能修改，而是将原本的集合的值copy了一份，定义为了一个新的集合这样改
   变集合的任何操作都会抛出UnsupportedOperationException 异常
2. 使用Arrays.asList创建的集合 通过Arrays.asList方法创建了一个集
   合，但不是我们传统中使用的ArrayList集合，两者继承同一个父类，但是
   内部却又不同的实现，Arrays.asList 创建的ArrayList中没有重写其父
   类AbstractList的add、remove 方法，所以不持支新增和删除。如果强行
   调用，虽然不会出现编译错误，调用的是父类的该方法，则会报出
   UnsupportedOperationException异常

Arrays.asList()使用

可以使用它将一个数组转换为一个List集合

String[] myArray = {"Apple", "Banana", "Orange"};
List<String> myList = Arrays.asList(myArray);
//上面两个语句等价于下面一条语句
List<String> myList = Arrays.asList("Apple","Banana", "Orange");

传递的数组必须是对象数组，而不是基本类型。因为Arrays.asList()是泛型
方法，传入的对象必须是对象数组

int[] myArray = {1, 2, 3};
List myList = Arrays.asList(myArray);
System.out.println(myList.size());//1
System.out.println(myList.get(0));//数组地址值
System.out.println(myList.get(1));//报错：ArrayIndexOutOfBoundsException
int[] array = (int[]) myList.get(0);
System.out.println(array[0]);//1

Stream可以实现转换

Integer [] myArray = { 1, 2, 3 };
List myList = Arrays.stream(myArray).collect(Collectors.toList());
//基本类型也可以实现转换（依赖boxed的装箱操作）
int [] myArray2 = { 1, 2, 3 };
List myList = Arrays.stream(myArray2).boxed().collect(Collectors.toList());

Collection.toArray()方法使用

该方法是一个泛型方法，如果toArray方法中没有传递任何参数的话返回的是
Object类型数组

String [] s= new String[]{
    "dog", "lazy", "a", "over", "jumps", "fox", "brown", "quick", "A"
};
List<String> list = Arrays.asList(s);
Collections.reverse(list);
s=list.toArray(new String[0]);//没有指定类型的话会报错

集合框架底层数据结构总结

1. List

• Arraylist：Object[]数组
• Vector：Object[]数组
• LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

2. Set

• HashSet（无序，唯一）:基于HashMap 实现的，底层采用HashMap来保存元素
• LinkedHashSet：LinkedHashSet 是HashSet 的子类，并且其内部是通过
  LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部
  是基于 HashMap 实现一样，不过还是有一点点区别的
• TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树)

3. Map

集合类别是什么？

分为三类

1. 线性集合类
2. 映射集合类
3. 一般集合类

线性集合类有哪些？

ArrayList

ArrayList 内部通过数组保存元素，默认初始容量为10 ，之后以1.5倍进行扩
容。每次扩容时新建一个新的数组，然后将原数组中的元素复制到新数组中（直
接复制引用），之后将原数组中的元素清除，数组引用指向新的数组。插入元素
和删除元素时间复杂度都是O(n)，获取元素的时间复杂度为O(1)，ArrayList
是非线程安全的类

ArrayList继承和实现的接口有哪些？

ArrayList类继承于AbstractList抽象类，ArrayList类还实现Serializable
、RandomAccess、Cloneable 接口。其中 Serializable 接口是用于将对象序
列化以储存在文件中或者通过流的形式在网络中传输的接口，RandomAccess 接
口是一个没有声明任何方法的空接口，标识该类支持快速随机访问。cloneable
接口是一个对象复写Object类中clone()方法必须实现的接口

ArrayList是什么？底层数据结构是什么？

ArrayList就是有序的动态数组列表，主要⽤来装载数据，它的主要底层实现是
数组Object[] elementData

ArrayList的扩容机制是什么样的？

1. JDK1.7 相当于设计模式中的饿汉式，第一次创建无参构造器时就创建一个
   初始容量为10的数组，否则就根据参数创建指定长度的数组
2. JDK1.8 相当于设计模式中的懒汉式，ArrayList可以通过构造⽅法在初始
   化的时候指定底层数组的⼤⼩。 通过⽆参构造⽅法的⽅式ArrayList()初始化
   ，则赋值底层数组 Object[] elementData 为⼀个默认的空数组 Object[]
   所以数组容量为0，只有真正对数据进⾏添加add时，如果当前数组就是那个
   默认空数组，才分配默认为10的初始容量
3. 在扩容的时候，1.6是取余，1.7和1.8是位运算，右移⼀位，其实就是除以
   2这个操作

   int newCapacity = (oldCapacity * 3)/2 + 1;
   int newCapacity = oldCapacity + (oldCapacity >> 1);

ArrayList的add方法具体是如何实现的？

1. add方法思路：add添加一个元素时首先判断elementData 是不是默认的
   空数组，如果是那么当前设定容量就赋值为初始容量10，否则直接使用当前
   元素个数加1的值作为当前容量进入下一个判断方法。判断方法结束以后就
   在数组末尾添加元素
2. 判断方法：首先modeCount会1，表示列表元素结构进行了更改。然后比
   较当前设定容量与数组长度的大小关系。如果已经大于数组长度那么就会调
   用扩容方法grow
3. grow方法：首先获得一个原数组1.5倍长的长度设定为新长度，如果设定
   容量小于这个1.5倍的新长度那么这个新长度就是数组扩容后的长度。否则数
   组扩容后的长度就是一开始设定的长度。接下来还要判断这个新长度是否溢
   出，与Integer.MAX_VALUE-8进行比较，如果大于就调用调整容量的方法
4. 调整容量的方法：判断设定容量是否超过最大整数的限制，如果超过就
   直接抛出异常表示没有判断获取型数组。如果没有超过限制则将设定容量赋
   值为最大整数-8，如果已经大于最大整数-8则直接赋值为最大整数，获取
   新长度后将原数组扩容为新数组，调用Arrays.copyOf方法将原数组的值
   拷贝到新数组。这里使用设定容量进行判断而不是1.5倍的长度进行判断是
   因为设定容量可能并没有超过限制

一句话概括ArrayList的扩容机制？

1. 先判断元素数组是否需要扩容
2. 确定扩容后的容量（第一次将容量调整为默认容量(10)，之后以1.5倍
   数进行扩容）
3. 判断扩容后容量是否溢出
4. 进行数组扩容并复制原数组元素到新数组中

ArrayList按照索引增加和减少是什么样的？

ArrayList有指定index（索引下标）新增，也有尾部新增，但是都有校验长
度的判断过程，就是说如果⻓度不够，是需要扩容的

ArrayList⽤来做队列合适么？

ArrayList不适合做队列。队列⼀般是FIFO（先⼊先出）的，如果⽤ArrayList
做队列，就需要在数组尾部追加数据，数组头部删除数组，反过来也可以。但是
⽆论如何总会有⼀个操作会涉及到数组的数据搬迁，这个是⽐较耗费性能的

ArrayList的优缺点有哪些？

ArrayList的优点如下

• ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了
  RandomAccess 接口，因此查找的时候非常快
• ArrayList 在顺序添加一个元素的时候非常方便

ArrayList的缺点如下

• 删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那
  么就会比较耗费性能
• 插入元素的时候，也需要做一次元素复制操作，缺点同上

如何实现数组和List之间的转换？

1. 数组转 List：使用 Arrays.asList(array) 进行转换
2. List 转数组：使用 List 自带的 toArray() 方法

为什么ArrayList的elementData加上transient修饰？

ArrayList 实现了Serializable 接口，这意味着ArrayList支持序列化。
transient的作用是默认elementData数组不序列化，重写了writeObject
实现。每次序列化时先调用defaultWriteObject()方法序列化ArrayList
中的非transient 元素，然后遍历elementData，只序列化已存入的元素
，这样既加快了序列化的速度，又减小了序列化之后的文件大小

ArryList是线程不安全的？为什么？

ArrayList 是线程不安全的，因为ArrayList 里的方法没有加锁，也没有
使用其他保证线程安全的措施，当多个线程来对ArrayList 进行操作时，
就会出现并发修改异常

LinkedList

LinkedList 内部以双向链表的结构来保存元素，每一个元素都是一个双向链表
节点。每次来一个元素，就新建一个链表节点并将这个节点插入当前的双向链表
尾部，时间复杂度为 O(1)。删除元素的时候也是通过要删除元素的值来找到对
应的链表节点，之后将这个链表节点从双向链表中移除，寻找链表节点的时间
复杂度为O(n)，删除节点的时间复杂度为 O(1)，因此整个删除节点的时间复
杂度为O(n)。因为LinkedList 实现了Deque 接口，因此也可以将其作为队
列/双端队列使用。LinkedList 也是非线程安全的类

LinkedList是什么？底层数据结构是什么？

底层使用的是双向链表数据结构，可以作为队列/双端队列使用。LinkedList
实现了List、Queue、Deque、Cloneable、Serializable接口

LinkedList和ArrayList在尾部插入数据效率？

1. 当输入的数据一直是小于千万级别的时候，大部分是Linked效率高，应该
   是当出现ArrayList扩容的时候，会效率降低，所以ArrayList的效益比较低
   。而当数据量大于千万级别的时候，就会出现ArrayList的效率比较高了
2. LinkedList每次增加的时候，会new 一个Node对象来存新增加的元素，
   所以当数据量小的时候，这个时间并不明显，而ArrayList需要扩容，所以
   LinkedList的效率就会比较高，其中如果ArrayList出现不需要扩容的时
   候，那么ArrayList的效率应该是比LinkedList高的，当数据量很大的时
   候，new对象的时间大于扩容的时间，那么就会出现ArrayList的效率比
   Linkedlist高了

Queue有什么作用？

这个接口声明一个队列的相关操作

1. add添加一个元素到队列尾部，offer添加一个元素到队列尾部
2. remove移除头部元素如果队列为空抛出异常，poll也是移除头部元素如果
   队列为空返回null
3. element取出头部元素，如果队列为空抛出异常，peek也是取出头部元素
   当队列为空时返回null

Deque有什么作用？

这个接口声明了双端队列的相关操作

1. addFirst添加元素到双端队列的头部，addLast添加元素到双端队列的尾
   部，以上两个如果有容量限制添加失败会抛出异常。offerFirst添加元素到
   双端队列头部
2. offerLast添加元素到双端队列尾部，以上两个添加失败false
3. removeFirst removeLast
4. poolFirst pollLast
5. getFirst getLast
6. peekFirst peekLast

LinkedList用什么保存元素？

LinkedList有一个用来表示元素节点的类Node，有前驱和后继指针字段。
LinkedList没有扩容机制，添加元素时只需要插入链表尾即可。但是每个
节点除了保存元素值外还要保存前驱和后继指针，消耗额外的内存空间。
有一个first和last指针分别指向头结点和尾节点

LinkedList如何实现插入？

add方法默认是将元素插入到链表尾部。如果使用add(int index,E e)来
添加元素的话首先判断越界以及是否是直接插入在尾部，否则就会先找到
节点的位置，这里是调用node方法找到节点位置，思路是如果index不大
于链表长度的1/2就正向遍历，否则就反向遍历，这种设计能够最小化减
少循环的次数。注意索引是从0开始，找到这个节点后还要获取该节点的
前驱节点，注意插入的意思是新节点要插入到index这个位置，所以新
节点的后继节点就是找到的这个节点

ArrayList和LinkedList

ArrayList的遍历和LinkedList遍历性能⽐较如何？

ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的
连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内
存的性能开销

ArrayList与LinkedList的应用场景？

在需要频繁读取集合中的元素时，更推荐使用ArrayList，而在插入和删除
操作较多时，更推荐使用 LinkedList。如果需要线程安全的就是可以使用
Vector，CopyOnWriteArrayList

ArrayList与LinkedList的区别？

1. 数据结构实现 ArrayList 是动态数组的数据结构实现，而LinkedList
   是双向链表的数据结构实现
2. 随机访问效率 ArrayList比LinkedList在随机访问的时候效率要高，因为
   LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找
3. 增加和删除效率 在非首尾的增加和删除操作，LinkedList要比ArrayList
   效率要高，因为ArrayList增删操作要影响数组内的其他数据的下标
4. 内存空间占用LinkedList 比ArrayList 更占内存，因为LinkedList的
   节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后
   一个元素
5. 线程安全 ArrayList和LinkedList都是不同步的，也就是不保证线程安全

插入和删除是否受元素位置的影响？

1. ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置
   的影响。 比如：执行add(E e)方法的时候，ArrayList 会默认在将指定的元
   素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位
   置i插入和删除元素的话（add(int index, E element)）时间复杂度就为
   O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)
   个元素都要执行向后位/向前移一位的操作
2. LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位
   置的影响，都是近似O(1)而数组为近似O(n)

Vector

Vector和ArrayList类似，内部都是采用数组来保存元素，而其与ArrayList最
大的区别在于Vecotr是线程安全的类。因此如果需要用线程安全的线性结构，可
以采用Vecotor

Vector是什么？底层数据结构是什么？

Vecctor类和ArrayList继承的类和实现的接口都一样，也是有序的动态数据
列表，Vector可以指定每次扩容的增量，如果不指定默认每次扩容2倍。默认
无参构造器设定的数组长度是10。Vector类的所有方法都是同步的

ArrayList 和 Vector 的区别是什么？

1. 线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安
   全的，而 ArrayList 是非线程安全的。
2. 性能：ArrayList 在性能方面要优于 Vector。
3. 扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只
   不过在Vector 扩容每次会增加1倍，而ArrayList 只会增加50%

Stack

该类继承自Vector，因此也是线程安全的类，其提供了“栈”这种数据结构的一
些操作元素 API，入栈、出栈、取栈顶元素等

Stack是什么？底层数据结构是什么？

Stack继承了Vector类，也是线程安全的，提供了栈的实现。
push pop peek都是线程安全的方法，push 本质是在链表尾部添加元素，pop
本质是在链表尾部移除元素，peek本质是在链表尾部取出元素

遍历一个List有哪些不同的方式？

1. for 循环遍历，基于计数器。在集合外部维护一个计数器，然后依次读取每
   一个位置的元素，当读取到最后一个元素后停止
2. 迭代器遍历，Iterator。Iterator是面向对象的一个设计模式，目的是屏蔽
   不同数据集合的特点，统一遍历集合的接口
3. foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现，使用
   时不需要显式声明 Iterator 或计数器。优点是代码简洁，不易出错，缺点是只
   能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换

多线程场景下如何使用 ArrayList？

1. Vector类替代
2. ArrayList不是线程安全的，如果遇到多线程场景，可以通过Collections
   的synchronizedList 方法将其转换成线程安全的容器后再使用。核心就是
   arrayList 的add() 的外面套了一层 synchronized 锁

   List<String> synchronizedList = Collections.synchronizedList(list);

3. JUC中的CopyOnWriteArrayList（写时复制）是java.util.concurrent
   包里的类，是个线程安全的类

   List<String> list =new CopyOnWriteArrayList<>();

   CopyOnWriteArrayList 的思想是写时复制

• 写时复制：我们要向一个文件中添加新数据时，先将原来文件拷贝一份，
  然后在这个拷贝文件上进行添加，而此时如果有别人读取数据，还是从原文
  件读取，添加数据完成后，再用这个拷贝文件替换掉原来的文件。这样做的
  好处是，读写分离，写的是拷贝文件，读的是原文件，可以支持多线程并
  发读取，而不需要加锁。其中的 setArray方法中的array是用volatile
  修饰的，可以保证可见性。其中add操作依然是要加锁的

缺点如下
在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写
少的应用场景。不适合内存敏感以及对实时性要求很高的场景

• 内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两
  倍左右
• 数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未
  同步到读数组中。只能保证数据的最终一致性，不能保证数据的实时一致性。

映射集合类有哪些？

HashMap

HashMap提供了一种高效的两种数据之间的映射能力。内部提供了一个table数
组，数组元素为自定义的实现了Map.Entry 接口的对象。Map.Entry就描述了
一个完整的键值对对象。通过键的hash 值来决定当前键值对元素所在的数组
下标。其默认的初始元素容量为 16，扩容因子默认为0.75，当容量达到当前
最大容量* 扩容因子的值时进行扩容。 每次扩容的时候容量翻倍。这样保证
每次进行键值对进行hash时可以通过位运算来代替取余操作（防止得到的数
组下标越界）提高效率。当出现 hash 值冲突的时候，先采用链地址法处理
（使用单链表将冲突的元素连接），当某个冲突链表的长度大于8 并且数组
长度大于等于64时，将其树化（转换为红黑树，加快查找速度）。HashMap
是非线程安全的类

HashMap用哪个类保存键值对？

在HashMap中通过一个名为Node的静态内部类来实现Map.Entry接口并实现接
口中的方法。Node类中有键的哈希值、key、value、next指针用于指向下一个
Node（用于处理冲突）

HashMap的loadFactor和threshold两个字段有什么用？

1. loadFactor 意为负载因子，这个值用于计算出下一次需要对HashMap进
   行扩容时HashMap中包含的最大元素（即键值对）数
2. threshold 意为容纳键值对的最大值

Node[] table的初始化长度length(默认值是16)，Load factor为负载因
子(默认值是0.75)，threshold 是 HashMap 所能容纳键值对的最大值。
threshold = length * Load factor。也就是说，在数组定义好长度之
后，负载因子越大，所能容纳的键值对个数越多。如果键值对的数量超出
threshold就会扩容

为什么元素个数达到threshold就进行扩容？

这样做确实会浪费一部分内存，但是主要目的是为了减少元素冲突。当当前的
HashMap 容量越大的时候，给元素的 key 计算出来的 hashCode 的选择也
就越多，这样就越不容易产生冲突。而 HashMap 的任务其实主要是致力于保
证在尽可能低的时间复杂度O(1) 中插入和查询元素。所以从这个角度上来说
牺牲一点内存是值得的

默认负载因子为什么是0.75？

0.75是对空间和时间效率的一个平衡选择

• 如果内存空间很多而又对时间效率要求高，可以降低负载因子Loadfactor
  的值
• 相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子
  loadFactor的值，这个值可以大于1

作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。较
高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包
括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，
并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，
rehash操作将不会发生

HashMap的最大容量是多少？

最大容量MAXIMUM_CAPACITY是1073741824，2*MAXIMUM_CAPACITY-1就是
最大整数，最大容量也就是最大整数+1的一半

HashMap的底层数据结构是什么？

1. jdk7及jdk7之前，底层是用数组+链表 来实现的
2. jdk8及jdk8之后，底层是用数组+链表+红黑树来实现的，HashMap是通过
   一个Node类型的数组table保存所有键值对，数组长度必须是2的幂次方。有
   一个Set类型的集合entrySet保存所有键值对

HashMap在JDK1.8的构造方法具体内容是什么？

1. 自定义初始容量和负载因子，如果初始容量大于最大容量那么就设置为最
   大容量，负载因子不能小于0 或者是一个非数，注意0.0/0.0 不会抛异常但
   是每次的结果不同，然后就会通过tableSizeFor方法得到下一次要进行扩容
   时 HashMap对象包含的元素数目，赋值给threshold
2. 自定义初始化容量，默认负载因子是0.75
3. 无参构造函数 默认容量是16，默认负载因子0.75
4. 参数是一个Map对象 默认负载因子是0.75，并且把该对象的所有所有键
   值对通过putMapEntries方法传入

Float.isNaN有什么作用？

为了判断出一个值是否为 “非数字” 值，“非数字”值指的是类似于0.0/0.0
得到的值。在Java 中，小数除以 0 不会抛出 ArithmeticException异常
，但是每次0.0 / 0.0 得到的结果都是不同的值（对象）

tableSizeFor方法的作用是什么？

tableSizeFor方法中对当前cap指定的容量进行操作，返回第一个大于等于
cap的2的次幂值，具体实现就是把n的二进制数中最左边的那一位1之后的0
全变为1，如果n是正常的再加上1，那么一定就是2的次幂。一开始赋值时n
要减1是因为防止本来就是一个2的次幂再扩大两倍

n = cap - 1 = 5
//n 的二进制：000..00(29个0) 101，之后省略前导零
n |= n >>> 1 = (101) | (010) = 111
n |= n >>> 2 = (111) | (001) = 111
n |= n >>> 4 = (0) | (111) = 111
n |= n >>> 8 = (0) | (111) = 111
n |= n >>> 16 = (0) | (111) = 111

HashMap中key的存储索引是怎么计算的？

首先根据key的值计算出hashcode的值，然后根据hashcode计算出hash值
，最后通过hash&(length-1)计算得到存储的位置

HashMap在JDK1.7和1.8中的hash函数如何实现的？

首先取key的hashCode值、根据hashcode计算出hash值。JDK1.7和1.8的
不同之处在于根据hashcode计算出hash值

1. JDK1.7 扰动9次，先是右移20位和右移12位异或取得的值又右移7位
   与右移4位异或，为了让每一位都参与位运算，让相近的数最后通过hash
   能分散开并减少碰撞，采用多次位移和异或，多一次与key的hashCode
   异或，也是为了尽量减少碰撞
2. JDK1.8 hashCode值与其右移16位的值进行异或操作

   static final int hash(Object key) {
           int h;
           return key == null ? 0 : (h = key.hashCode()) ^ h >>> 16;
       }

JDK1.8为什么要hashcode异或其右移十六位的值?

1. 因为在JDK1.7 中扰动用了9次扰动处理=4次位运算+5次异或，计算
   hash 值的性能会稍差一点点
2. 从速度、功效、质量来考虑，JDK1.8 优化了高位运算的算法，只用了2
   次扰动处理=1次位运算+1次异或。通过hashCode()的高16位异或低16位，
   这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit
   都参与到Hash的计算，同时不会有太大的开销

HashMap数组的长度为什么是2 的幂次方？

这样做效果上等同于取模，在速度、效率上比直接取模要快得多。除此之外
，2的N次幂有助于减少碰撞的几率。如果length为2的幂次方，则length
-1转化为二进制必定是11111……的形式，在与h的二进制与操作效率会非
常的快，而且空间不浪费，每一个位置都有可能存放数据

为什么在两个版本都是hash值与length-1相与？

1. 把hash值对数组长度取模运算，模运算的消耗很大，没有位运算快
2. HashMap 的数组长度必须是2的次幂，所以其容量n转换成二进制中必
   然只有一位是1，那么n-1，就是将最左边的那一位1变为0，并且将其右边
   的0变成1，再将得到的值和hash通过&按位相与，这样的话得到的结果必
   然不会大于n-1。位操作速度一般的操作符快

HashMap在JDK7之前是如何实现的？

1. jdk7及jdk7之前，底层是用 数组+链表 来实现的
2. new HashMap()之后，底层不会直接创建数组，而是第一次put才创建
3. put 数据时(put(key,value))，如果是第一次put 会创建一个长度为
   16的数组(Entry[] table)，会先调用key 所在类的hashCode 方法计算
   出此 key 的哈希值，再将此哈希值经过处理计算后，得到该数据在数组
   table上的位置
4. 然后分情况判断是否存储

• 情况一 位置为空，直接在该位置上存储put的数据
• 情况二 位置不为空，说明存在一条链表，如果要put数据的key的哈希值
  与链表上的数据的key的哈希值不一样，则将数据放在此位置上，也就是链
  表头部
• 情况三 位置不为空，如果要put数据的key的哈希值与链表上的数据的key
  的哈希值一样，继续调用key的equals方法进行比较，如果一样那么覆盖这
  个值，否则插入链表头部

5. 当存储的数据超出临界值，且要存放数据的位置非空时，则扩容，扩容为
   原来容量的2倍。 临界值 = 当前容量 x 填充因子

JDK1.8中put中的冲突有哪两种情况？

这里的冲突是指两个键值对元素的 “键” 的 hashCode 相同

1. 要插入的键值对的 “键” 和冲突的键值对的 “键” 等价（两个引用指向
   一个对象或者两个引用指向的对象的 equals 方法返回 true）。此时记录
   这个键值对，到后面更新一下它的值即可
2. 要插入的键值对的 “键” 和冲突的键值对的 “键” 不等价（两个引用指
   向的对象的 equals 方法返回 false）。这种情况下就需要进行特殊处理
   （链化或者树化节点）

什么是哈希？

Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的
输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）
，这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间
，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定
输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘
要的函数

什么是哈希冲突？

当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们
就把它叫做碰撞（哈希碰撞）

HashMap在JDK1.8如何实现？

1. new HashMap() 之后，底层并不会直接创建数组。而是等put 数据时才
   会创建数组
2. put 数据时，如果是第一次向这个集合中put 数据，如果是的话就通过
   resize 方法申请空间并调整table的容量，会先创建一个长度为16的一维
   数组(Node[] table)，然后存储数据
3. 存储数据的过程和jdk7 及之前基本一样，即先计算哈希值，然后根据，
   最后通过hash&(length-1) 计算得到存储的位置
4. 找到位置后分为四种情况判断

• 情况一 位置为空，直接在该位置上存储put的数据
• 情况二 位置不为空，如果要put数据的key的哈希值与位置上的数据的key
  的哈希值一样并且继续调用key的equals方法进行比较也一样，那么先记录
  冲突的元素到后面更新。既然是更新那么modCount不会改变
• 情况二 位置不为空，并且哈希值不一样，那么判断节点是否是TreeNode
  类型，如果是的话说明这条链表已经被树化，那么直接将这个节点插入到
  红黑树中，返回一个TreeNode对象。如果为null 说明这是更新操作那么
  不会更新modCount
• 情况三 位置不为空，并且与该位置的key不等价，那么判断该节点是链表
  类型的节点，那么遍历链表如果存在等价的key则记录这个链表位置
• 情况四 位置不为空，并且与该位置的key不等价，那么遍历完整个链表都
  没有等价的key，这时把节点插入到链表尾部。然后判断链表长度是否大于8
  以及数组长度是否大于等于64，如果满足这两个条件就将链表树化，否则
  就扩容数组

5. 之前如果判断是更新操作那么不会更改modCount，而是直接return 旧
   的值，如果不是更新操作那么modCount+1，如果插入一个键值对后大于阈
   值，那么会调用resize方法重新分配数组的长度

HashMap的put方法简要流程？

简要流程如下：

1. 首先根据key的值计算hash值，找到该元素在数组中存储的下标
2. 如果数组是空的，则调用resize 进行初始化
3. 如果没有哈希冲突直接放在对应的数组下标里
4. 如果冲突了，且key 已经存在，就覆盖掉value
5. 如果冲突后，发现该节点是红黑树，就将这个节点挂在树上
6. 如果冲突后是链表，判断该链表是否大于8 ，如果大于8并且数组容量小于64
   ，就进行扩容
7. 如果链表长度大于8并且数组的容量大于等于64，则将这个结构转换为红黑树
8. 否则，链表插入键值对，若 key 存在，就覆盖掉 value

resize方法的作用是什么？

这个方法是真正给HashMap扩容的方法

1. 首先判断数组长度是否大于0，如果大于0分为两种情况。第一种情况就是
   数组长度已经大于HashMap 指定的最大容量，那么这个时候数组的长度就不
   能再增大了，但是阈值threshold 变为最大整数。第二种情况就是如果当前
   HashMap 容量不小于默认容量16并且其*2 小于允许的最大容量，那么将
   HashMap长度变成原来的两倍，并且容量分配阀值*2
2. 如果当前HashMap的容量为0，并且容量分配阀值大于0。之前解析构造方
   法时已经说明了，当调用传入指定初始容量的构造方法时，数组依然没有扩
   容，所以长度为0，但是阈值threshold设置为大于等于初始容量的2的次幂
   ，所以这时数组的长度就扩容为阈值的大小
3. HashMap的长度和容量分配阀值都为0。说明这个时候调用的是默认的无参
   构造器，那么HashMap的容量就设置为16，阈值就是12
4. 如果新分配的阈值newThr为0，说明调用了有初始容量和指定负载因子的
   构造器或有初始容量的构造器，这两个构造器刚刚只把初始容量设置为阈值
   大小，没有设置新阈值的大小，通过刚刚的代码可以看到只设置了newCap
   还没有设置newThr。直接使用loadFactor字段计算出新的容量分配阈值
5. 到此HashMap的新长度和阈值都已经获取，接下来为table申请内存空间

扩容在JDK1.8中有什么不一样？

有两处优化

1. resize 之后，元素的位置在原来的位置，或者原来的位置+oldCap（原
   来哈希表的长度）。不需要像 JDK1.7 的实现那样重新计算hash ，只需要
   看看原来的 hash 值新增参与运算的那个bit是1还是0就好了，是0的话索
   引没变，是1的话索引变成“原索引 + oldCap ”。这个设计非常的巧妙，
   省去了重新计算 hash 值的时间
2. JDK1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的
   数组索引位置相同，则链表元素会倒置（头插法），容易出现逆序且环形链
   表死循环问题。JDK1.8 不会倒置，使用尾插法

在JDK1.7的时候是先扩容后插入，JDK1.8先插入后扩容？

1. JDK1.7 先进行扩容后进行插入的，当前数据存储的数量大小必须大于
   等于阈值以及当前加入的数据是否发生了hash冲突这两个条件都满足那么
   就会扩容，但是如果不发生Hash冲突的话，说明当前桶是空的（后面并没
   有挂有链表），那就等到下一次发生Hash冲突的时候在进行扩容。但是当
   如果以后都没有发生hash冲突产生，那么就不会进行扩容了，减少了一
   次无用扩容，也减少了内存的使用
2. JDK1.8 先插入后进行扩容，当最新的数据存储的数量大于阈值的时候
   就会扩容

HashMap将旧数组复制到新数组的过程是怎样的？

如果旧数组不为null的话还要把之前数组的元素复制到新数组，复制过程如下

1. 如果原数组元素引用不为null，并且这个元素没有next节点，证明没有
   元素和它产生冲突，那么直接复制到新数组，注意这个索引位置有变化，
   用新长度-1与hash值进行按位与操作。注意如果是TreeNode类型的节点
   也有next，因为TreeNode继承了Node类
2. 如果有冲突，并且节点类型是TreeNode类型，会调用split方法，处理
   树中元素的重排
3. 如果有冲突，并且节点类型是链表节点类型，元素的位置在原来的位置，
   或者原来的位置+oldCap ，如果有些节点还在相同的位置那么这条链表的相
   对顺序也不会改变

HashMap中如何通过键获取相应的值？

1. 首先判断数组table是否为null，如果为null说明根本没有这个键值对，
   直接返回null
2. 如果数组table不为null，key的hash值与length-1向与的结果得到索
   引，如果数组中相应索引位置第一个键值对与要查询的键等价那么直接返回
   第一个键值对
3. 如果不等价的话，根据这个节点是树类型节点还是链表类型节点在相应
   数据结构中查找等价的键

HashMap中如何通过键删除相应的值？

remove方法中通过参数key删除相应键值对，本质是调用removeNode方法

1. 首先判断数组table是否为null，如果为null说明根本没有这个键值对，
   直接返回null
2. 如果数组table不为null，那么就要根据索引位置取得要删除的节点
3. 如果要删除的是树类型节点，那么直接从红黑树中移除
4. 如果要删除的是链表类型节点，如果删除的是头结点那么直接将数组下
   标赋给下一个节点，如果不是头结点那么删除时注意上一个节点的next要改

HashMap 为什么是红黑树不是平衡二叉树？

1. 在CurrentHashMap中是加锁了的，实际上是读写锁，如果写冲突就会等待
   ，如果插入时间过长必然等待时间更长，而红黑树相对AVL树他的插入更快
2. 插入和删除方面，AVL树速度较慢，需要更高的旋转次数才能在修改时正确
   地重新平衡数据结构
3. AVL树比红黑树保持更加严格的平衡，在AVL树中查找通常更快，但这是以
   更多旋转操作导致更慢的插入和删除为代价的

EntrySet类的作用是什么？

EntrySet 类是 HashMap 的一个内部类，而 HashMap 的 entrySet方
法中返回的也是一个 EntrySet 对象，也就是说我们通过 entrySet方
法得到的其实是一个 EntrySet 对象，我们对 Set 进行遍历时是通过
其提供的迭代器进行的，能够返回一个EntryIterator迭代器

EntryIterator类的作用是什么？

EntryIterator就是一个实现了Itreator接口的迭代器，通过next方法
遍历HashMap中所有的元素。在构造方法中初始化next引用为table数组
中第一个不为null的元素，然后开始按照数组的顺序遍历。如果当前位
置有一个链表，那么会从头节点到尾节点的顺序遍历。我通过阅读源码
发现如果是一个红黑树的话，链表树化的过程中next节点没有变化

HashMap中元素的遍历顺序和元素的插入顺序有关系吗？

没有任何关系，因为插入元素时主要依据的是元素的键的 hashCode 值，而
每个元素的键的 hashCode 没有什么规则（根据键所属的类的实现而定），
所以我们并不能试图按照插入元素的顺序来取出元素。如果需要使得取出的
元素顺序是按照插入元素的先后顺序排序的话，使用LinkedHashMap

HashMap的重要属性是什么？

1. 容量（默认为 16，如果自定义初始容量，那么会处理成最小的不小于指
   定的容量的2 的次幂数，注意HashMap 的长度一定会是2的次幂数）
2. 扩容机制（每次扩容变成上一次容量的 2 倍，如果当前元素数目达到扩
   容阀值（负载因子 * 当前 HashMap 总容量），进行扩容）
3. 负载因子（默认 0.75 ）
4. 最大容量(Integer.MAX_VALUE - 8)，可以指定的最小容量(1(2^0))

不直接用红黑树？而选择先用链表，再转红黑树？

因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。
当元素小于8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当
元素大于8 个的时候，红黑树搜索时间复杂度是O(logn)，而链表是O(n)，
此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。因此，如果
一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性
能的

不用红黑树，用二叉查找树可以么？

可以。但是二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链
表结构一样了，造成很深的问题），遍历查找会非常慢

当链表转为红黑树后，什么时候退化为链表？

为6的时候退转为链表。中间有个差值7可以防止链表和树之间频繁的转换。假设
一下，如果设计成链表个数达到8则链表转换成树结构，链表个数小于8则树结
构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘
徊，就会频繁的发生树转链表、链表转树，效率会很低

为什么链表改为红黑树的阈值是8，而不是7或20？

1. 由于treenodes的大小大约是常规节点的两倍，因此我们仅在容器包含
   足够的节点以保证使用时才使用它们，当它们变得太小（由于移除或调整
   大小）时，它们会被转换回普通的node节点，容器中节点分布在hash 桶
   中的频率遵循泊松分布，桶的长度超过8的概率非常非常小。所以作者应
   该是根据概率统计而选择了8作为阀值

HashMap中key的存储索引是怎么计算的？

首先根据key的值计算出hashcode的值，然后根据hashcode计算出hash值，最后
通过hash&（length-1）计算得到存储的位置。这里的 Hash 算法本质上就是三
步：取key的 hashCode值、根据 hashcode 计算出hash值、通过取模计算下标

JDK1.8为什么要hashcode异或其右移十六位的值？

因为在JDK 1.7 中扰动了4次，计算 hash 值的性能会稍差一点点。 从速度、功效
、质量来考虑，JDK1.8 优化了高位运算的算法，通过hashCode()的高16位异或低
16位实现：(h = k.hashCode()) ^ (h >>> 16)。这么做可以在数组 table 的
length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不
会有太大的开销

为什么 hash 值要与length-1相与？

把hash值对数组长度取模运算，模运算的消耗很大，没有位运算快。当length总是
2的n次方时，h& (length-1) 运算等价于对length取模，也就是 h%length，但
是&比%具有更高的效率

还知道哪些hash算法？

Hash函数是指把一个大范围映射到一个小范围，目的往往是为了节省空间，使得
数据容易保存。 比较出名的有MurmurHash、MD4、MD5等等

key 可以为 Null 吗？

可以，key 为 Null 的时候，hash算法最后的值以0来计算，也就是放在数组
的第一个位置

一般用什么作为HashMap的key？

一般用Integer、String 这种不可变类当HashMap 当key，而且String
最为常用。因为字符串是不可变的，所以在它创建的时候hashcode 就被
缓存了，不需要重新计算。这就是HashMap 中的键往往都使用字符串的
原因。因为获取对象的时候要用到equals() 和hashCode() 方法，那
么键对象正确的重写这两个方法是非常重要的，这些类已经很规范的
重写了hashCode() 以及equals() 方法

用可变类当HashMap 的key 有什么问题?

一般用Integer、String 这种不可变类当HashMap 当key，而且String 最为
常用。因为字符串是不可变的，所以在它创建的时候hashcode 就被缓存了，
不需要重新计算。这就是HashMap 中的键往往都使用字符串的原因。因为获取
对象的时候要用到equals() 和hashCode() 方法，那么键对象正确的重写
这两个方法是非常重要的，这些类已经很规范的重写了 hashCode() 以及
equals()方法

HashMap扩容时候的死循环问题？

1. HashMap 1.7 插入数据时，使用的是头插法，并发下扩容时的Rehash，会
   出现死循环问题，可能导致链表成环
2. 而HashMap 1.8 插入数据时，改成了尾插法，解决了扩容时的死循环问题

多线程的put可能导致元素的丢失？

多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前
一个key 被后一个key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和JDK
1.8 中都存在

1. 假设线程1和线程2同时执行put，并且都冲突在同一个位置，异常就发生
   当两个线程都找到数组位置的时候，假设线程1先new Node放在这个位置然
   后切换，线程2此时也new Node就会覆盖这个线程1的Node

put和get并发时，可能导致get为null？

1. 线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此
   时执行get，有可能导致这个问题。此问题在JDK 1.7和JDK 1.8 中都存在。
2. 线程1用新计算的容量new 了一个新的hash表，将新创建的空hash表赋值
   给实例变量table，但是还没有进行值的拷贝，此时线程2执行get，就会get
   出null

如何解决HashMap 线程不安全的问题？

1. Hashtable类替代
2. Collections 工具类转换，synchronizedMap 方法来得到一个保证
   线程安全的Map，这是一个静态的方法，返回一个线程安全的 Map，这个
   方法只是对参数中的 Map对象进行了一下包装，返回了一个新的Map对象
   ，将参数中的Map 对象的相关操作方法都通过使用 synchronized 关键
   字修饰的方法包装了一下，但是具体的操作流程还是和原来的Map对象一
   样
3. JUC 中的ConcurrentHashMap 替代

ConcurrentHashMap

用ConcurrentHashMap 替代HashMap，可以解决线程安全的问题，但是
ConcurrentHashMap 也是有jdk1.7 和jdk1.8 的区别。

1. 数据结构 jdk1.7 采用Segment分段锁方式。jdk1.8 采用数组+链表
   和红黑树实现
2. 保证线程安全机制 jdk1.7 采用Segment分段锁方式保证线程安全，
   其中Segment 继承自ReentrantLock，jdk1.8采用CAS和synchronized
   来保证线程安全
3. 锁的粒度 jdk1.7 将数据分成一段一段的存储，然后每一段数据单独
   一个锁，所以当一个线程占用一个锁访问其中的一段数据时，其他段的数
   据可以被其他线程访问，包含一个Segment数组，数组中的每个Segment
   都包含一个HashEntry 数组，每个HashEntry 是一个链表结构的元素。
   jdk1.8 锁的锁更细粒度了，synchronized 只锁定当前链表或红黑树
   的首节点，只要hash不冲突，就不会有线程安全问题，效率大幅提升
4. 链表转化为红黑树 定位节点的 hash 算法简化会带来弊端，hash
   冲突加剧，因此在链表节点数量大于 8（且数据总量大于等于 64）时
   ，会将链表转化为红黑树进行存储
5. 查询时间复杂度 从 JDK1.7的遍历链表O(n)， JDK1.8 变成遍历红
   黑树O(logN)

Segment是什么？

Segment是ConcurrentHashMap 的一个静态内部类，保存一个HashEntry数
组，继承了ReentrantLock，所以Segment是一种可重入锁，扮演锁的角色。
Segment 默认为16，也就是并发度为16

HashEntry是什么？

保存key 和value 以及一个指向下一个节点的引用，用volatile 修饰了
HashEntry 的数据 value 和 下一个节点 next，保证了多线程环境下
数据获取时的可见性

实现原理？

1. JDK1.7 JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组结构和
   HashEntry 数组结构组成，即 ConcurrentHashMap 把哈希桶数组切分成小
   数组（Segment），每个小数组有n 个HashEntry 组成。将数据分为一段一
   段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数
   据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。
2. JDK1.8 JDK1.8 中的ConcurrentHashMap 选择了与HashMap相同的Node
   数组+链表+红黑树结构，在锁的实现上，抛弃了原有的Segment 分段锁，采
   用CAS + synchronized实现更加细粒度的锁。将锁的级别控制在了更细粒度
   的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点（红黑树的根
   节点），就不会影响其他的哈希桶数组元素的读写，大大提高了并发度

JDK1.8 中为什么使用synchronized替换ReentrantLock？

1. 在JDK1.6 中，对synchronized 锁的实现引入了大量的优化，并且
   synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 ->
   重量级锁一步步转换
2. 减少内存开销。假设使用可重入锁来获得同步支持，那么每个节点都需
   要通过继承AQS 来获得同步支持。但并不是每个节点都需要获得同步支持
   的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨
   大内存浪费

两个版本put 方法执行逻辑是什么？

1. JDK1.7 先定位到相应的Segment，然后再进行put 操作。首先会尝试
   获取锁，如果获取失败肯定就有其他线程存在竞争，则利用
   scanAndLockForPut() 自旋获取锁
2. JDK1.8 分为4步

• 第一步 根据key 计算出hash 值
• 第二步 判断是否需要进行初始化
• 第三步 定位到Node，拿到首节点 f，判断首节点f。如果f为null那么
  就采用CAS的方式尝试添加，如果为f.hash=MOVED=-1 ，说明其他线程
  在扩容，参与一起扩容。如果都不满足，synchronized 锁住f 节点，
  判断是链表还是红黑树，遍历插入
• 第四步 当在链表长度达到8 的时候，数组扩容或者将链表转换为红黑树

两个版本get 方法的执行逻辑是什么？

1. JDK1.7 根据key 计算出hash 值定位到具体的Segment，再根据hash
   值获取定位HashEntry 对象，并对HashEntry 对象进行链表遍历，找到
   对应元素。由于 HashEntry 涉及到的共享变量都使用volatile 修饰，
   volatile 可以保证内存可见性，所以每次获取时都是最新值
2. JDK1.8 可以分为4步

• 第一步 根据key 计算出hash 值，判断数组是否为空
• 第二步 如果是首节点，就直接返回
• 第三步 如果是红黑树结构，就从红黑树里面查询
• 第四步 如果是链表结构，循环遍历判断

get 方法是否要加锁？

get 方法不需要加锁。因为Node 的元素value 和指针next 是用volatile
修饰的，在多线程环境下线程A修改节点的value 或者新增节点的时候是对
线程B可见的。这也是它比其他并发集合比如 Hashtable、用Collections
.synchronizedMap()包装的 HashMap 效率高的原因之一

get 方法不需要加锁与volatile 修饰的哈希桶数组有关吗？

没有关系，哈希桶数组table用volatile 修饰主要是保证在数组扩容的时
候保证可见性

ConcurrentHashMap 不支持key 或者value 为null？

先来说value 为什么不能为null。因为 ConcurrentHashMap 是用于多线程
的，如果ConcurrentHashMap.get(key)得到了null ，这就无法判断，是
映射的value是null ，还是没有找到对应的key而为null ，就有了二义性
。而用于单线程状态的HashMap 却可以用containsKey(key) 去判断到底
是否包含了这个null。二义性是指

1. 这个key从来没有在map中映射过。
2. 这个key的value在设置的时候，就是null

ConcurrentHashMap 的并发度是什么？

1. 并发度可以理解为程序运行时能够同时更新ConccurentHashMap 且不产
   生锁竞争的最大线程数。在JDK1.7中，实际上就是ConcurrentHashMap中的
   分段锁个数，即Segment[]的数组长度，默认是16，这个值可以在构造函数
   中设置
2. 如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最
   小的2的幂指数作为实际并发度，也就是比如你设置的值是17，那么实际并
   发度是32
3. 如果并发度设置的过小，会带来严重的锁竞争问题，如果并发度设置的过
   大，原本位于同一个Segment内的访问会扩散到不同Segment中，CPU cache
   命中率会下降，从而引起程序性能下降
4. 在JDK1.8中，已经摒弃了Segment的概念，选择了Node数组+链表+红黑树
   结构，并发度大小依赖于数组的大小

ConcurrentHashMap 迭代器是强一致性还是弱一致性？

与HashMap 迭代器是强一致性不同，ConcurrentHashMap迭代器是弱一致性。
ConcurrentHashMap 的迭代器创建后，就会按照哈希表结构遍历每个元素，
但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分
，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发
现并反映出来，这就是弱一致性。这样迭代器线程可以使用原来老的数据，而
写线程也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连
续性和扩展性，是性能提升的关键，无法保证读取到的数据是原集合中最新
的数据，即迭代器进行遍历的是拷贝的集合，在遍历期间原集合发生的修改
，迭代器是检测不到的

ConcurrentHashMap能完全替代Hashtable吗？

不能

1. 线程安全 ConcurrentHashMap 和 Hashtable 都是线程安全的
2. 底层数据结构 ConcurrentHashMap 的底层数据结构： jdk1.7 是用分
   段数组+链表实现，jdk1.8 是用数组+链表+红黑树实现，红黑树可以保证查
   找效率，Hashtable 底层数据结构是用 数组+链表 实现
3. 保证线程安全的方式 ConcurrentHashMap jdk1.7 是用分段锁的方式保
   证线程安全，jdk1.8 是用synchronized和CAS 保证线程安全，Hashtable
   是用全表锁来保证线程安全（既一个Hashtable 只用一把锁），这种的方式
   的效率非常低
4. 一致性 ConcurrentHashMap 的迭起器是弱一致性的，而Hashtable 的
   迭代器是强一致性的。弱一致性是指当数据更新后，后续对该数据的读取操
   作可能得到更新后的值，也可能是更改前的值。强一致性是指当更新操作完
   成之后，在任何时刻所有的用户或者进程查询到的都是最近一次成功更新
   的数据。强一致性是程度最高一致性要求，也是最难实现的

size操作？

1. JDK1.7 每个Segment 维护了一个count 变量来统计该Segment 中的键
   值对个数，在执行size 操作时，需要遍历所有Segment 然后把count 累计
   起来。 在执行size 操作时先尝试不加锁，如果连续两次不加锁操作得到的
   结果一致，那么可以认为这个结果是正确的。尝试次数为3 ，如果尝试的次
   数超过3次，就需要对每个Segment 加锁
2. JDK1.8 不需要加锁，数组的每个位置都有一个元素数量值

多线程下安全的操作map还有其他方法吗？

还可以使用Collections.synchronizedMap方法，对方法进行加同步锁。本
质也是对 HashMap 进行全表锁。在竞争激烈的多线程环境下性能依然也非常
差，不推荐使用

HashMap是如何遍历键值对的？

有三种遍历方式

1. 通过 entrySet() 方法得到 HashMap 的键值对集合，再通过集合提供
   的迭代器来遍历元素，这个遍历过程其实就是顺序遍历HashMap中的table
   数组
2. 通过 keySet() 方法得到HashMap 的所有键值对中 “键” 的集合，然后
   通过 get()方法得到值来遍历元素
3. 通过 forEach方法来实现HashMap中的元素遍历（JDK1.8以上支持），
   本质也是通过遍历HashMap中的table数组

TreeMap

同 HashMap 一样，TreeMap也是提供了一种数据之间的的映射能力，但是这
里并没有用高效来形容它，是因为同 HashMap 相比，它的效率还是略低，因
为其还提供对键排序的功能，我们在遍历 TreeMap 的时候，元素的遍历顺序
已经是根据某种规则排序后的序列，为了达成这种功能，其内部借助了一种平
衡二叉树（红黑树）的数据结构来实现。当我们在插入新的元素的时候，其依
据定义的排序规则来找到合适的位置进行插入。所以其插入元素的过程是来一
个插一个，所以在 TreeMap 中并没有初始容量和扩容的概念。而插入、删除、
查询等操作的时间复杂度为 O(logn)。n为树中的节点总数，即为元素总数

TreeMap的comparator属性有什么用？

TreeMap 的实现原理是红黑树，即为一种二叉搜索树，comparator的任务就
是为了判断出两个节点的大小关系的。Comparator是提供了一个泛型参数的
接口，需要实现compare方法，比较传入的两个参数的大小关系

TreeMap是用什么数据结构来描述键值对？

用一个Entry类来实现键值对，这个Entry实现了Map.Entry接口，包含key
value、左子节点和右子节点和父节点，以及表示颜色的boolean值

TreeMap的特点是什么？

TreeMap 最大的特点是能根据插入的键值对的键来对键值对元素节点进行
排序，而当我们遍历TreeMap 对象的时候取得的元素顺序是按照某个规则
来进行排序的，具体规则我们可以在创建TreeMap 对象的实现传入一个
Comparator 对象的参数来进行指定。注意如果没有指定 TreeMap 的
Comparator对象，那么需要保证TreeMap储存的键值对元素的 “键”
是实现了Comparable 接口，否则会报类型转换异常

TreeMap是否可以指定元素的值进行排序？

我们已经知道 TreeMap 默认会依据键值对元素的键来对元素进行排序。我
们也可以通过自定义的 Comparator 接口对象来指定其对键的排序方式，
也可以通过指定对元素的值的排序方式来对元素进行排序。
可以利用TreeMap会利用键来对键值对元素进行排序的特点，来自定义一个
“键的包装类”来作为新的键，我们就叫它 KeyWrap吧，这个KeyWrap内部
有两个引用，分别指向原本的 Key 和 Value两个属性，我们使得这个类
实现Comparable接口，并且重写其 compareTo方法，这个方法直接调用
Value 的 compareTo 方法作为返回值。同时，因为 TreeMap 本身需要
用到 Key的equals 方法来进行键的等价比较，因此我们实现这两个方法
并且调用对应键的方法来作为返回值

HashMap和TreeMap 如何选用？

1. 在需要大量插入、删除和查找元素这种操作的，选择HashMap ，因为底
   层使用数据+链表+红黑树实现，对于插入、删除、查找的性能都不错，但是
   HashMap的结果是没有排序的
2. 在需要对集合排序的时候，选择TreeMap，TreeMap 基于红黑树实现，
   TreeMap 的映射根据键的自然顺序进行排序，或者根据创建映射时提供的
   Comparator 进行排序，具体取决于使用的构造方法

LinkedHashMap的底层实现原理是什么？

LinkedHashMap内部通过双向链表来维持元素顺序，同时继承于HashMap
，元素的遍历顺序和插入顺序相同。有一个链表头和链表尾节点

LinkedHashMap如何保存键值对？

使用内部类Entry保存键值对，继承于 HashMap.Node，每个节点都有一
个前驱和后继节点

LinkedHashMap相较于父类HashMap重写了什么内容？

put 和 remove 方法都没有在LinkedHashMap 中提供，但是我们在使用
LinkedHashMap的时候都是直接使用这些方法来操作元素，HashMap中提
供了3个方法供LinkedHashMap 重写

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
Node<K, V> newNode(int hash, K key, V value, Node<K, V> e)
TreeNode<K, V> newTreeNode(int hash, K key, V value, Node<K, V> next)

LinkedHashMap是怎么实现元素访问顺序和插入顺序相同的功能？

在 HashMap 的 putVal（HashMap 的 put 方法中会调用）方法中还会调
用newNode和newTreeNode 方法。

1. newNode 这个方法新建的是LinkedHashMap 提供的表示双向链表节
   点的类对象，之后调用了linkNodeLast方法来连接这个新建的链表元素
   ，也就是将新建的节点连接到链表尾部
2. afterNodeRemoval remove 方法中最后会调用afterNodeRemoval
   (node)方法，既然移除了一个元素，自然要把这个元素从链表中移除

LinkedHashMap是如何遍历元素的？

和其他Map一样，LinkedHashMap也是通过迭代器(Iterator)来遍历元
素的，有两种方式遍历元素。这两个迭代器对象都调用了nextNode方法
，实际就是根据已经有的双向链表的来顺序遍历元素

1. 通过keySet 得到键的集合，可以返回一个LinkedKeyIterator迭
   代器
2. 通过entrySet 得到键值对的集合，返回一个LinkedEntryIterator
   迭代器

LinkedHashMap的属性accessOrder有什么作用？

表示链表元素排序依据：按访问顺序排序(true)，按插入顺序排序(false)
，比如一开始插入了很多元素，第一次遍历的时候完全按照插入的顺序进行
遍历，第二次遍历时，如果中间访问了一些元素，那么这些元素就会放在后
面，也就是说accessOrder为true时会将已经访问的元素放到链表末尾，
这里已经访问包括get和put

1. afterNodeAccess() 当一个节点被访问时，如果accessOrder为true，
   则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后，在每次访问一
   个节点时，会将这个节点移到链表尾部，保证链表尾部是最近访问的节点，
   那么链表首部就是最近最久未使用的节点
2. afterNodeInsertion() 这个方法在插入元素之后（putVal之中会调
   用，即在元素插入完成之后会调用），并且传递的参数evict值为true，
   这里面将removeEldestEntry 方法的返回值作为一个条件判断

LinkedHashMap如何重写afterNodeInsertion？

这个方法在插入元素之后（putVal 之中会调用，即在元素插入完成之后会
调用），并且传递的参数 evict值为true，这里面将removeEldestEntry
方法的返回值作为一个条件判断。这个方法直接返回了 false ，并且它是
protected 修饰的，因此可以被子类重写，假设我们自定义一个子类并且
将这个方法重写返回 true 的话，在上面的代码中就会调用（当链表头结
点不为null时）将新添加的节点移除，这样的话LinkedHashMap 就是一
个没有任何元素的空链表。这个方法移除链表最老的节点（因为采用尾插
法建立双向链表，因此头结点是最老的节点）

removeEldestEntry的作用是什么？

根据removeEldestEntry的介绍来看，主要是用于当LinkedHashMap作为
缓存映射时，可以节省内存而设计的。其实我们熟悉的LRU缓存算法就可以
通过LinkedHashMap中提供的accessOrder和removeEldestEntry方法来
实现，我们知道LRU 算法的缓存的思想是每次有新元素加入时，淘汰最近
最少被使用的元素。其核心思想是 如果数据最近被访问过，那么将来被访
问的几率也更高。也就是说每当元素被访问时，LRU就将该元素移至缓存队
列顶部，而每次如果需要淘汰元素时，LRU将缓存队列底部的元素淘汰。而
在LinkedHashMap中，我们可以通过accessOrder属性来控制将每次访问
的元素移至链表尾部，通过removeEldestEntry方法来控制是否移除链表
头部节点，只是将链表尾部看成了 LRU 中缓存队列的顶部，将链表头部
看成了 LRU 中缓存队列的底部

LinkedHashMap

HashMap 在遍历时的元素顺序和插入时的元素顺序是不一定相同的，那么有时
候我们可能有这种需求，即使得遍历时的元素顺序和插入时一致，此时我们就
可以考虑使用LinkedHashMap，因为 LinkedHashMap 是继承于HashMap 的
，只不过为了维护元素顺序和插入时的保持一致，LinkedHashMap在HashMap
节点的基础上增加了指向前驱和后继节点的引用，也就是通过双向链表来维护
元素的顺序。而同时留有一些扩展方法，一些缓存算法（LRU）就可以通过
LinkedHashMap 来轻松实现

如何通过LinkedHashMap实现LRU？

1. 重写removeEldestEntry方法 如果容量超过最大值就返回true，表示可以
   进行操作最久未使用节点
2. 调用构造器时第三个参数accessOrder 设置为true

WeakHashMap

WeakHashMap 的Entry 继承自WeakReference，被WeakReference 关联的
对象在下一次垃圾回收时会被回收。WeakHashMap 主要用来实现缓存，通过
使用WeakHashMap 来引用缓存对象，由JVM 对这部分缓存进行回收。

HashTable

和 HashMap 类似，不过其是线程安全的类，其实也就是在每个操作元素的方法
前加入synchronized关键字修饰，效率不高，我们完全有更好的方法来代替这
个，同时具体的扩容机制和HashMap 也略有不同：默认初始容量为11，扩容因
子为0.75，每次扩容后的容量变为之前容量的2倍+1。这个类已经被标为遗留类
，即不被推荐使用。键和值都不能为null

Hashtable的底层实现原理？有什么特点？

这个类类似于 HashMap，不过它相对于HashMap而言其中的相关操作元素
的方法名前多用了一个synchronized关键字修饰，也就是说这个类是多
线程安全的。默认初始容量为11，扩容因子为 0.75，每次扩容后的容量
变为之前容量的 2 倍 + 1

WeakHashMap

由于弱引用的出现，使得 WeakHashMap 可以做到保证其所引用的元素不会导致
OutofMemoryError 异常。同HashMap 一样，WeakHashMap 内部也是通过数组
来储存元素的，WeakHashMap 默认的初始容量是 16，最大容量为 1 << 30，
默认扩容因子为 0.75，可以指定初始容量，但是处理过后的初始容量一定是2
的次幂，好处是可以通过 & 运算来代替 % 运算提高效率；每次扩容时容量翻
倍。节点（Entry）之间利用单项链表之间来处理 hash 值冲突

IdentifyHashMap

之前介绍的Map 都是通过具体元素的 key 的 equals 方法来判断元素等价，
而这个Map 中则是通过最原始的方法（Object 的equals 方法）来判断，即
如果两个对象不是同一个对象，即使其内部属性值相同，那么也被当做不等价
。其内部通过一个Object 类型的数组来储存元素，即键值都用这个数组储存
，键所在的下标是偶数（0、2、4…），值所在的下标是对应的键下标+1。同时
，存入元素也按照相同的规则。如果 当前元素个数 * 3 > table.length
（包括了键和值）。那么进行扩容，扩容是数组容量翻倍。table 数组的最
大容量是 1 << 30，默认初始容量为32

一般集合类有哪些？

HashSet的底层实现原理？

这个类用来尽量保证以 O(1) 的时间复杂度来添加/判断元素存在/移除元
素等。所有对元素的相关操作都交给了其内部的一个HashMap 对象处理，
而添加进HashSet中的元素其实都是作为“键”储存在了这个HashMap对象
中

HashSet和HashMap的区别？

1. HashMap是实现了Map接口，存储的是键值对，HashSet是实现了Set接
   口，只存储对象。前者调用put 方法添加键值对，后者通过add方法添加元
   素，add方法的本质是调用put方法，值是一个不可更改的object
2. HashMap使用键来计算哈希值，HashSet是使用成员对象来计算哈希值
3. HashMap 比HashSet 快，前者使用了唯一的键来获取对象，当取对象
   时，HashMap 可以直接通过hash 计算得到的键来获取对象。HashSet 判
   断对象是否存在时调用的是 contains 方法，本质其实是调用HashMap
   的containsKey方法，这个方法本质也是通过hash 计算得到的值。以上
   来看实际没有差距，都必须计算哈希码，快是因为HashMap的键的性质-
   它通常是一个简单的String或者数字，而 String 和Integer 的计算
   哈希码的速度比整个对象的默认哈希码计算要快得多。也就是说如果
   HashMap的键与存储在HashSet中的键是相同的对象，则性能将没有
   真正的区别。区别在于HashMap的键是哪种对象
4. HashSet 的底层其实是基于HashMap 实现的，大部分方法都是直接调
   用HashMap中的方法，除少数方法比如clone readObject writeObject

TreeSet的底层实现原理？

这个类可以使得添加进入 Set 集合中的元素按照某种规则来排序，而和
HashSet类似，其内部也是借助了一个TreeMap类型的对象来实现相关的
操作，底层结构是红黑树，查找的时间复杂度是O(log(N))

LinkedHashSet的底层实现原理？

就像 HashMap 和 LinkedHashMap 的关系一样，LinkedHashSet 是继承
了 HashSet 的，这个类的作用时保证遍历元素得到的元素序列的顺序和插
入元素的先后顺序一样。而其中没有重写任何操作元素的方法，底层使用了
一个双向链表

如何实现安全的Set集合？

1. Set 集合内部都是通过对应的Map 实现的，那么我们自定义一个Set 集
   合类，内部用一个线程安全的Map 来实现，比如使用ConcurrentHashMap
2. 在集合工具类Collections 中已经提供了一些方法来创造一些线程安全
   的集合，这里面有一些以synchronized 开头的方法名，接受的参数也是有
   List、Map、Set 等集合

comparable 和 comparator的区别？

1. comparable接口实际上是出自java.lang包，它有一个compareTo(Object
   obj)方法用来排序
2. comparator接口实际上是出自java.util包，它有一个compare(Object
   obj1, Object obj2)方法用来排序

Collection 和Collections 有什么区别？

1. java.util.Collection 是一个集合接口（集合类的一个顶级接口）
   它提供了对集合对象进行基本操作的通用接口方法。Collection接口在
   Java 类库中有很多具体的实现。Collection接口的意义是为各种具体
   的集合提供了最大化的统一操作方式，其直接继承接口有List与Set
2. Collections则是集合类的一个工具类，其中提供了一系列静态方法
   ，用于对集合中元素进行排序、搜索以及线程安全等各种操作

TreeMap 和TreeSet 在排序时如何比较元素？

1. TreeSet 要求存放的对象所属的类必须实现 Comparable 接口，该接
   口提供了比较元素的compareTo() 方法，当插入元素时会回调该方法比较
   元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable
   接口从而根据键对元素进行排序

Collections 工具类中的sort() 方法如何比较元素？

sort 方法有两种重载的形式

1. 待排序容器中存放的对象比较实现Comparable 接口
2. 不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，
   参数是Comparator 接口的子类型（需重写compare 方法实现元素比较）