概述

集合是什么？为什么会有集合？数组不好吗？

Java是面向对象的语言，初学时当我们需要将一堆对象存储在一个容器里方便我们使用的时候数组可以满足我们的需要。但是数组有一个极大的缺点，即数组初始化的时候长度是固定的，不可变的。我们事先往往不知道我们到底需要将多少个对象放到一个容器中，若是数组的长度开大了就会浪费存储空间，长度开小了又不够我们用。同时同一个容器我们不仅需要存储同一个类型的对象，也可能需要存储不同类型的对象，这也是普通数组不能够做到的事情，数组只能存储同一个类型的数据。所以这时候集合就来了。专门替我们解决了这个问题。
由上面的叙述我们可以大概了解到集合与数组的区别 （1）长度区别：集合长度可变，数组长度不可变 （2）内容区别：集合可存储不同类型元素，数组存储只可单一类型元素 （3）元素区别：集合只能存储引用类型元素，数组可存储引用类型，也可存储基本类型

Java集合类框架的基本接口有哪些？

集合类接口指定了一组叫做元素的对象。集合类接口的每一种具体的实现类都可以选择以它自己的方式对元素进行保存和排序。有的集合类允许重复的键，有些不允许。Java集合类提供了一套设计良好的支持对一组对象进行操作的接口和类。Java集合类里面最基本的接口有：Collection：代表一组对象，每一个对象都是它的子元素。Set：不包含重复元素的Collection。List：有顺序的collection，并且可以包含重复元素。Map：可以把键(key)映射到值(value)的对象，键不能重复。

为什么集合类没有实现Cloneable和Serializable接口？

克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的。因此，应该由集合类的具体实现来决定如何被克隆或者是序列化。

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

目前查到有两种方法：（1）通过 Collections. unmodifiableCollection(Collection c)（2）通过Arrays.asList创建的集合

快速失败(fail-fast)机制

快速失败机制 “fail-fast” 是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时， 程序就会触发fail-fast机制，抛出 ConcurrentModificationException 异常。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。。 例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素过程中线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常。
原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
解决办法：

  1. 在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
  2. 使用CopyOnWriteArrayList来替换ArrayList

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

    Collection 和 Collections 有什么区别？

    1、Collection 是一个集合的接口，它提供了对集合对象进行基本操作的通用接口方法， 为各种具体的集合提供了最大化的统一操作方式。 像 List，Set，Queue接口都继承Collection接口。
    2、 Collections 是一个包装类。它包含有各种有关集合操作的静态方法（对集合的搜索、排序、线程安全化等）； 不能实例化，就像一个工具类。

    List、Set、Map 之间的区别是什么？

    1、Set子接口：无序，不允许存在重复的元素。 检查元素效率低下，删除和插入的效率高，插入和删除不会引起元素的位置变化。
    2、List子接口：有序，可以存在重复元素。 和数组类似，List可以动态增长，查找元素的效率较高，插入元素和删除元素效率低，因为会引起其他元素位置发生变化。
    3、Map接口不是Collection接口的继承，该接口描述了从不重复的键到值的映射，是一个键值对集合。

    迭代器

    什么是迭代器(Iterator)？

    Iterator提供了统一遍历操作集合元素的统一接口, Collection接口实现Iterable接口,
    每个集合都通过实现Iterable接口中iterator()方法返回Iterator接口的实例, 然后对集合的元素进行迭代操作. 有一点需要注意的是：在迭代元素的时候不能通过集合的方法删除元素, 否则会抛出ConcurrentModificationException异常. 但是可以通过Iterator接口中的remove()方法进行删除。

    Iterator和ListIterator的区别是什么？

    下面列出了他们的区别：Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。

相同点都是迭代器，当需要对集合中元素进行遍历不需要干涉其遍历过程时，这两种迭代器都可以使用。
不同点1.使用范围不同，Iterator可以应用于所有的集合。而ListIterator只能用于List及其子类型。2.ListIterator有add方法，可以向List中添加对象，而Iterator不能。3.ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向遍历。Iterator不可以。4.ListIterator可以定位当前索引的位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。5.都可实现删除操作，但是ListIterator可以实现对象的修改，set()方法可以实现。Iterator仅能遍历，不能修改。

阐述ArrayList、Vector、LinkedList的存储性能和特性。

答：ArrayList 和Vector都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。
Vector中的方法由于添加了synchronized修饰，因此Vector是线程安全的容器，但性能上较ArrayList差，因此已经是Java中的遗留容器。
LinkedList使用双向链表实现存储（将内存中零散的内存单元通过附加的引用关联起来，形成一个可以按序号索引的线性结构，这种链式存储方式与数组的连续存储方式相比，内存的利用率更高），按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。
Vector属于遗留容器（Java早期的版本中提供的容器，除此之外，Hashtable、Dictionary、BitSet、Stack、Properties都是遗留容器），已经不推荐使用。
但是由于ArrayList和LinkedListed都是非线程安全的，如果遇到多个线程操作同一个容器的场景，则可以通过工具类Collections中的synchronizedList方法将其转换成线程安全的容器后再使用（这是对装潢模式的应用，将已有对象传入另一个类的构造器中创建新的对象来增强实现）。

List、Map、Set三个接口存取元素时，各有什么特点？

答：List以特定索引来存取元素，可以有重复元素。Set不能存放重复元素（用对象的equals()方法来区分元素是否重复）。
Map保存键值对（key-value pair）映射，映射关系可以是一对一或多对一。Set和Map容器都有基于哈希存储和排序树的两种实现版本，基于哈希存储的版本理论存取时间复杂度为O(1)，而基于排序树版本的实现在插入或删除元素时会按照元素或元素的键（key）构成排序树从而达到排序和去重的效果。

TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？

答：TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。
Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象实现Comparable接口以实现元素的比较；
第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。

HashMap相关

美团技术文章：
https://tech.meituan.com/2016/06/24/java-hashmap.html

Java中的HashMap的工作原理是什么？

  1.     hashmap是一个key-value键值对的数据结构，**从结构上来讲在jdk1.8之前是用数组加链表的方式实现，jdk1.8加了红黑树。**也就是说现在的 hashmap的内部是使用数组+链表+红黑树的形式实现的，其中数组是一个一个Node[]数组，我们叫他hash桶数组，它上面存放的是key-value键值对的节点。<br />        HashMap是用hash表来存储的，在HashMap里为解决hash冲突，**使用链地址法**。简单来说就是数组加链表的形式来解决，当数据被hash后，得到数组下标，把数据放在对应下表的链表中。<br />然后再说一下hashmap的方法实现。<br />**put方法**<br />1、put方法的第一步，就是计算出要put添加的元素在hash桶数组中的索引位置。<br />    得到索引位置需要三步，去put元素key的hashcode值，高位运算，取模运算，高位运算就是用第一步得到的值h，用h的高16位和低16位进行异或操作，第三步为了使hash桶数组元素分布更均匀，采用取模运算，取模运算就是用第二步得到的值和hash桶数组长度-1的值取与。这样得到的结果和传统取模运算结果一致，而且效率比取模运算高<br />jdk1.8中put方法的具体步骤，先判断hashmap是否为空，为空的话扩容，不为空计算出key的hash值i，然后看table[i]是否为空，为空就直接插入，不为空判断当前位置的key和table[i]是否相同，相同就覆盖，不相同就查看table[i]是否是红黑树节点，如果是的话就用红黑树直接插入键值对，如果不是开始遍历链表插入，如果遇到重复值就覆盖，否则直接插入，如果链表长度大于8，转为红黑树结构，执行完成后看size是否大于阈值threshold，大于就扩容，否则直接结束 get方法就是计算出要获取元素的hash值，去对应位置取即可。 扩容机制，hashmap的扩容中主要进行两部，第一步把数组长度变为原来的两倍，第二部把旧数组的元素重新计算hash插入到新数组中，在jdk1.8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二部一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中。 3.hashmap大小为什么是2的幂次方 在计算插入元素在hash桶数组的索引时第三步，为了使元素分布的更加均匀，用取模操作，但是传统取模操作效率低，然后优化成h&(length-1)，设置成2幂次方，是因为2的幂次方-1后的值每一位上都是1，然后与第二步计算出的h值与的时候，最终的结果只和key的hashcode值本身有关，这样不会造成空间浪费并且分布均匀，如果不是2的幂次方 如果length不为2的幂，比如15。那么length-1的2进制就会变成1110。在h为随机数的情况下，和1110做&操作。尾数永远为0。那么0001、1001、1101等尾数为1的位置就永远不可能被entry占用。这样会造成浪费，不随机等问题。

1、HashMap的结构是什么？

HashMap是Java中对象存储的容器，它的底层数据结构是一个数组和单向链表的结合体，数组呢在查询方面效率很高，随机增删的效率就低；单向链表呢它在随机增删方面效率高，查询效率就低； HashMap将以上两种结合在一起充分发挥各自的优点。
简单来说，hashmap整体是一个Node[]数组，也可以叫hash桶数组。数组的每一个位置是一条链表，链表中的每一个节点的value就是我们存储的对象object；

①、 哈希的相关概念
Hash 就是把任意长度的输入(又叫做预映射， pre-image)，通过哈希算法，变换成固定长度的输出(通常是整型)，该输出就是哈希值。这种转换是一种 压缩映射 ，也就是说，散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出，从而不可能从散列值来唯一的确定输入值。简单的说，就是一种将任意长度的消息压缩到某一固定长度的息摘要函数。
② 哈希的应用：数据结构
我们知道，数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入和删除也容易的数据结构呢？答案是肯定的，这就是我们要提起的哈希表。事实上，哈希表有多种不同的实现方法，我们接下来解释的是最经典的一种方法 —— 拉链法，我们可以将其理解为 链表的数组
我们可以从上图看到，左边很明显是个数组，数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。其中，根据元素特征计算元素数组下标的方法就是 哈希算法。
总的来说，哈希表适合用作快速查找、删除的基本数据结构，通常需要总数据量可以放入内存。在使用哈希表时，有以下几个关键点：

  • hash 函数（哈希算法）的选择：针对不同的对象(字符串、整数等)具体的哈希方法；
  • 碰撞处理：拉链法；

③、 HashMap 的数据结构
在Java中最常用的两种结构是 数组 和 链表，几乎所有的数据结构都可以利用这两种来组合实现，HashMap 就是这种应用的一个典型。实际上，HashMap 就是一个 链表数组组成的结构。
其中，Entry为HashMap的内部类，实现了 Map.Entry 接口，其包含了键key、值value、下一个节点next，以及hash值四个属性。事实上，Entry 是构成哈希表的基石，是哈希表所存储的元素的具体形式。

2、entry元素的添加过程？

在将元素对象添加进hashmap的过程中

  • 首先 通过 HashMap 自己提供的hash 算法算出当前要添加的元素key 的hash 值 ；（1、算出key的hash值）
  • 然后通过计算出的hash 值去调用 indexFor 方法计算当前对象应该存储在hashmap底层数组的几号位置 ；（2、用hash值算出数组位置）
  • 判断size 是否已经达到了当前阈值，如果没有，继续；如果已经达到阈值，则先进行数组扩容，将数组长度扩容为原来的2倍。size 是当前容器中已有 Entry 的数量，不是数组长度。（3、判断是否需要扩容）
  • 将当前对应的 hash，key，value封装成一个 Entry，去数组中查找当前位置有没有链表
    • 如果没有，则将元素放在这个位置的链表表头上；
    • 如果此位置上已经存在链表，那么遍历链表，如果链表上某个节点的 key 与当前key 进行 equals方法 比较后结果为 true，则把原来节点上的value 返回，将当前新的 value替换掉原来的value（即 存在则覆盖原来key的value ）。
  • 如果遍历完链表，没有找到key 与当前 key进行 equals方法为 true的，就把刚才封装的新的 Entry中next 指向当前链表的始节点，也就是说当前节点现在在链表的第一个位置，简单来说即，先来的往后退。
    3、HashMap的扩容机制
    首先，初始化 HashMap的无参构造中，容器默认的数组大小 initialCapacity 为 16，加载(负载)因子loadFactor 为0.75。容器的阈(yu)值为 initialCapacity loadFactor，默认情况下阈值为 16 0.75 = 12;
    当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的， 所产生的子链长度就会越来越长， 这样势必会影响HashMap的存取速度 。
    所以为了提高查询的效率，就要对HashMap的数组进行扩容， 但是，不得不说，扩容是一个非常耗时的过程，因为它需要重新计算这些元素在新table数组中的位置并进行复制处理，这就是resize。 所以，如果我们能够提前预知HashMap 中元素的个数，那么在构造HashMap时预设元素的个数能够有效的提高HashMap的性能。
    当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)loadFactor 时 ， 就 会 进 行 数 组 扩 容 ， loadFactor 的 默 认 值(DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数超过16 0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 216=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
    为什么扩容之后 Entry 在数组中的位置发生了变化？
    重哈希的主要是一个重新计算原HashMap中的元素在新table数组中的位置并进行复制处理的过程 。
    在添加元素进入hashmap的时候是使用 indexFor 方法 计算新元素在数组中的位置的；
    由源码得知，元素所在位置是和数组长度是有关系的，既然扩容后数组长度发生了变化，那么元素位置肯定是要发生变化了。
    特别需要注意的是，在重哈希的过程中，原属于一个桶中的Entry对象可能被分到不同的桶，因为HashMap 的容量发生了变化，那么 *h&(length - 1)     的值也会发生相应的变化。极端地说，如果重哈希后，原属于一个桶中的Entry对象仍属于同一桶，那么重哈希也就失去了意义。
    4、为什么负载因子是0.75 ？
    通俗来讲，当负载因子为1.0时，意味着只有当hashMap装满之后才会进行扩容，虽然空间利用率有大的提升，但是这就会导致大量的hash冲突，使得查询效率变低。
    当负载因子为0.5或者更低的时候，hash冲突降低，查询效率提高，但是由于负载因子太低，导致原来只需要1M的空间存储信息，现在用了2M的空间。最终结果就是空间利用率太低。

另一回答：HashMap中有两个很重要的参数：初始容量 和 负载因子，这两个参数是影响HashMap性能的重要参数。其中，容量表示哈希表中桶的数量 (table 数组的大小)，初始容量是创建哈希表时桶的数量；负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。
对于使用 拉链法（下文会提到）的哈希表来说，查找一个元素的平均时间是 O(1+a)，a 指的是链的长度，是一个常数。特别地，若负载因子越大，那么对空间的利用更充分，但查找效率的也就越低；若负载因子越小，那么哈希表的数据将越稀疏，对空间造成的浪费也就越严重。系统默认负载因子为 0.75，这是时间和空间成本上一种折衷，一般情况下我们是无需修改的。

5、 HashMap 的读取实现

相对于HashMap的存储而言，读取就显得比较简单了。因为，HashMap只需通过key的hash值定位到table数组的某个特定的桶，然后在该桶的链表中查找并返回该key对应的value即可 。
在这里能够根据key快速的取到value，除了和HashMap的数据结构密不可分外，还和Entry有莫大的关系。在前面就已经提到过，HashMap在存储过程中并没有将key，value分开来存储，而是当做一个整体key-value来处理的，这个整体就是Entry对象。特别地，在Entry对象中，value的地位要比key低一些，相当于是 key 的附属。
其中，针对键为NULL的键值对，HashMap 提供了专门的处理 。因此，调用HashMap的get(Object key)方法后，若返回值是 NULL，则存在如下两种可能：

  • 该 key 对应的值就是 null;

  • HashMap 中不存在该 key。

    6、JDK1.8之后的hashmap

    在JDK1.8及以后的版本中引入了红黑树结构，HashMap的实现就变成了数组+链表+红黑树。
    其中，桶数组是用来存储链表，链表是用来解决冲突，转化为红黑树是为了提高查询的效率。
    添加元素时，若桶中链表个数超过8，链表会转换成红黑树；
    删除元素、扩容时，若桶中结构为红黑树并且树中元素个数较少时会进行修剪或直接还原成链表结构，以提高后续操作性能；遍历、查找时，由于使用红黑树结构，红黑树遍历的时间复杂度为 O(logn)，所以性能得到提升。
    https://blog.csdn.net/sinat_40770656/article/details/121667274?

    HashMap中的Key是唯一的，那它是如何保证唯一性的呢？

    我们首先想到的是用equals比较，没错，这样可以实现，但随着元素的增多，put 和 get 的效率将越来越低，这里的时间复杂度是O(n)。也就是说，假如 HashMap 有1000个元素，那么 put时就需要比较 1000 次，这是相当耗时的，远达不到HashMap快速存取的目的。实际上，HashMap 很少会用到equals方法，因为其内通过一个哈希表管理所有元素，利用哈希算法可以快速的存取元素。当我们调用put方法存值时，HashMap首先会调用Key的hashCode方法，然后基于此获取Key哈希码，通过哈希码快速找到某个桶，这个位置可以被称之为 bucketIndex。
    如果两个对象的hashCode不同，那么equals一定为 false；否则，如果其hashCode相同，equals也不一定为 true。所以，理论上，hashCode 可能存在碰撞的情况，当碰撞发生时，这时会取出bucketIndex桶内已存储的元素，并通过hashCode() 和 equals() 来逐个比较以判断Key是否已存在。如果已存在，则使用新Value值替换旧Value值，并返回旧Value值；如果不存在，则存放新的键值对到桶中。因此，在 HashMap中，equals() 方法只有在哈希码碰撞时才会被用到，同时也保证了key在hashMap中的唯一性。

    HashMap是怎么解决哈希冲突的？

    什么是哈希？
    1.   Hash，一般翻译为“散列”，也有直接音译为“哈希”的，就是把任意长度的输入通过散列算法，变换成固定长度的输出，**该输出就是散列值（哈希值）**；这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间。<br />        **不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。**简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。<br />        所有散列函数都有如下一个基本特性**：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同**。

    什么是哈希冲突？

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

    HashMap的数据结构

    在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突：
    这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下（散列值相同的元素对象放在同一个链表里，链表放在bucket数组中）。
    但相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取链表对应的bucket位置，这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表，所以我们还需要对hashCode作一定的优化 。

    hash()函数
    1.   哈希冲突概率增大，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的【是撒意思？】，所以我们的优化思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：<br />static final int hash(Object key) {     int h;     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或） } <br />这比在**JDK 1.7**中，更为简洁，**相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）**；

    JDK1.8新增红黑树
    1.   通过上面的链地址法（使用散列表）和扰动函数我们成功让我们的数据分布更平均，哈希碰撞减少，但是当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)。<br />        为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)；

    小结：

    1 、使用链地址法（使用散列表）来链接拥有相同hash值的数据；2、 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；3、引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；

    能否使用任何类作为 Map 的 key？

    可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：

  • 如果类重写了 equals() 方法，也应该重写 hashCode() 方法。

  • 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。
  • 如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。
  • 用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。

    为什么HashMap中String、Integer这样的包装类适合作为K？

    答：String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率 。
  1. 都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
  2. 内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范，不容易出现Hash值计算错误的情况；

    如果使用Object作为HashMap的Key，应该怎么办呢？

    答：重写hashCode()和equals()方法
  • 重写hashCode()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；
  • 重写equals()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性；

    HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table数组的下标？

    答：hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，没有那么多空间就会导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；
    那怎么解决呢？
    1、HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；2、在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储。这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；

    HashMap 的底层数组长度为什么总是2的幂次方

    为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。
    这个算法应该如何设计呢？
    我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。
    那为什么是两次扰动呢？
    答：这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；

另一个回答：HashMap的底层数组长度总是2的n次方。当 底层数组的length为2的n次方时，h&(length - 1)就相当于对length取模，而且速度比直接取模要快得多，这是HashMap在速度上的一个优化。
总的来说，HashMap 的底层数组长度总是2的n次方的原因有两个，即当 length=2^n 时：
不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，空间利用率较高，查询速度也较快；
h&(length - 1) 就相当于对length取模，而且在速度、效率上比直接取模要快得多，即二者是等价不等效的，这是HashMap在速度和效率上的一个优化。

hashCode()和equals()方法的重要性体现在什么地方？

Java中的HashMap使用hashCode()和equals()方法来确定键值对的索引，当根据键获取值的时候也会用到这两个方法。如果没有正确的实现这两个方法，两个不同的键可能会有相同的hash值，因此，可能会被集合认为是相等的。而且，这两个方法也用来发现重复元素。所以这两个方法的实现对HashMap的精确性和正确性是至关重要的。

如何决定使用 HashMap 还是 TreeMap？

  1.     对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个**有序**的key集合进行**遍历**，TreeMap是更好的选择。<br />        基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。

为什么HashMap 的容量必须是2的N次方？怎么来的？

因为HashMap 中的数据结构是数组加链表还有红黑树嘛，数组中放的就链表，在我们把元素添加进HashMap 的时候，需要先计算出元素应该放在数组中的哪一个位置。计算的方法就是先根据元素的key算出相应的哈希值，然后拿该哈希值跟数组的长度-1进行相与，然后得到我们添加的元素将要添加到数组中的哪一个桶下标。但是这个下标是有要求的， 首先该数组的下标不能越界其次计算出来的下标要均衡。
若果仅是满足这两个条件的话取模操作是非常合适的，但是这里之所以用的是相与操作是因为与操作是位操作，是计算机中计算比较快的运算，比取模更快；
而用与操作去计算下标的话，你用来跟哈希码进行相与的数组容量就必须是一个二的次方数，二的次方数的一个特点就是它对应的二进制串只有一个1，16减去1之后就得到一个高位全是0低位全是1的数15（假如数组容量是16）；这样哈希码不管它的二进制是怎样的，它跟一个高位全是0低位全是1的数15进行相与操作，结果的范围只可能是0-15保证了数组不越界，而且由于哈希码的不确定性，同时保证了计算出来的下标是均匀分布的。
简单来说，之所以是2的次方数，就是为了让相与操作跟取模操作的结果一样。

为什么要将 hashCode 的高16位参与运算？

HashMap在计算hashCode 的时候调用了hash方法对hashCode进行多次的扰动，hash源码如下：
//这个k是添加的元素对应的key
final int hash(Object k) {
//默认的hashSeed值为0
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
//符号^表示异或操作，相同为0，不同为1
//调用hashCode方法获取其哈希码，但因为h的值在上面赋值为0，0跟哈希码进行异或会改变h的值
h ^= k.hashCode();
//不断进行右移，异或操作
h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);
//Entry里面存的不是原来k.hashCode()方法返回的值，而是进行一系列操作后的值
}
这里在算哈希码的时候为什么要进行这么多次的右移、异或操作呢？
这是因为在调用indexFor方法计算下标时，该哈希码要跟数组长度 -1 进行与操作，如下面的indexFor方法介绍的所示，因为int是32位的整数，而在进行与操作的时候哈希码只有低16位参与了与运算，而高16完全不起作用；这就导致两个高位不同而低位相同的key算出来的数组下标产生哈希冲突的概率加大；
所以我们要尽量让高16位也参与运算，减少哈希碰撞的概率；那如何才能让哈希码的高16位也能参与到运算中来呢？这就是进行扰动，即多次的右移、异或操作的原因，目的就是为了让散列表更加散列、随机；
这里注意一点，因为传入的key可以是任意对象的，我们可以去重写它的hashCode方法，倘若你自己重写的方法没有对哈希码进行多次的扰动的话，得出来的散列表的散列性就会很差，链表的长度会很长，查询的性能就会很差；

有关ConcurrentHashMap

https://blog.csdn.net/ThinkWon/article/details/104588551

LinkedHashMap相关

简单概述

  1.     HashMap 是 Java Collection Framework 的重要成员，也是Map族中我们最为常用的一种。不过遗憾的是，HashMap是无序的，也就是说，迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，我们确需要用到一个可以保持插入顺序的Map。<br />        庆幸的是，JDK为我们解决了这个问题，它为HashMap提供了一个子类 —— LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销，**但是它通过维护一个额外的双向链表保证了迭代顺序。**<br />        特别地，该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap 和 保持访问顺序的LinkedHashMap，其中LinkedHashMap的**默认实现是按插入顺序排序的。**<br />    本质上，HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Entry节点链入一个双向链表双向链表的HashMap。<br />在LinkedHashMapMap中，所有put进来的Entry都保存在如下面第一个图所示的哈希表中。<br />但由于它又额外定义了一个以head为头结点的双向链表 ，因此对于每次put进来Entry，除了将其保存到哈希表中对应的位置上之外，还会将其插入到双向链表的尾部。<br />HashMap和双向链表的密切配合和分工合作造就了LinkedHashMap。特别需要注意的是，next用于维护HashMap各个桶中的Entry链，before、after用于维护LinkedHashMap的双向链表，虽然它们的作用对象都是Entry，但是各自分离，是两码事儿。 <br />特别地，由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap也最多只允许一条Entry的键为Null(多条会覆盖)，但允许多条Entry的值为Null。此外，LinkedHashMap 也是 Map 的一个非同步的实现。

LinkedHashMap 的数据结构

Hashtable相关

概述

  1.     事实上，HashMap几乎可以等价于Hashtable，除了HashMap是非线程安全的并且可以接受null键和null值。 <br />        与HashMap类似，HashTable也包括五个成员变量，分别是table[数组](https://so.csdn.net/so/search?q=%E6%95%B0%E7%BB%84&spm=1001.2101.3001.7020)、HashTable中Entry个数count、HashTable的阈值threshold、HashTable的负载因子loadFactor 和 HashTable结构性修改次数modCount。
  • Entry数组table： 一个由Entry对象组成的链表数组，table数组的每一个数组成员就是一个链表；
  • Entry个数count： Hashtable中Entry对象的个数(所有链表加起来？)；
  • 阈值threshold： Hashtable进行扩容时的阈值；
  • 负载因子loadFactor： 在其容量自动增加之前可以达到多满的一种尺度，默认也是0.75；

  • 结构性修改次数modCount： 记录Hashtable生命周期中结构性修改的次数，便于快速失败 (所谓快速失败是指其在并发环境中进行迭代操作时，若其他线程对其进行了结构性的修改，这时迭代器能够立马感知到并且立即抛出ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你（你已经出错了）)；

    Hashtable 的数据结构以及快速存取

    Hashtable与HashMap的数据结构以及保存数据的过程基本相同 。但是也有一些细节上的差异：

  • Hashtable不同于HashMap，前者既不允许key为null，也不允许value为null;

  • HashMap中用于定位桶位的Key的hash的计算过程要比Hashtable复杂一点，没有Hashtable如此简单、直接；
  • 在HashMap的插入K/V对的过程中，总是先插入后检查是否需要扩容；而Hashtable则是先检查是否需要扩容后插入；
  • Hashtable不同于HashMap，前者的put操作是线程安全的。

在读取细节上，Hashtable与HashMap的主要差别如下：

  • 不同于HashMap，Hashtable的读取操作是同步的；

  • 在HashMap中，若读取到的Value值为NULL，则存在如下两种可能：该key对应的值就是null或者HashMap 中不存在该key；而在Hashtable中却只有一种可能：Hashtable中不存在含有该key的Entry。造成这种差别的原因正是二者对Key和Value的限制的不同：HashMap最多允许一个Key为null，但允许多个value值为null；Hashtable既不允许空的Key，也不允许空的Value。

    HashMap和Hashtable有什么区别？

    HashMap和Hashtable都实现了Map接口，因此很多特性非常相似。但是，他们有以下不同点：

  • HashMap允许键和值是null，而Hashtable不允许键或者值是null。

  • Hashtable是同步的，而HashMap不是。因此，HashMap更适合于单线程环境，而Hashtable适合于多线程环境。
  • HashMap提供了可供应用迭代的键的集合，因此，HashMap是快速失败的。另一方面，Hashtable提供了对键的列举(Enumeration)。
  • 一般认为Hashtable是一个遗留的类。 因为 Hashtable虽然是线程安全的，但是我们一般不推荐使用它，因为有比它更高效、更好的选择ConcurrentHashMap；而单线程环境下，HashMap拥有比Hashtable更高的效率(Hashtable的操作都是同步的，导致效率低下)，所以更没必要选择它了。
  • 初始容量大小和每次扩充容量大小的不同： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小。

    ArrayList

    概述

    1.   ArrayList 实现了 List 中所有可选操作，并允许包括 NULL 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作其支撑数组的大小。<br />        ArrayList 是基于动态数组实现的，其容量能自动增长，并且用 size 属性来标识该容器里的**元素个数**，而**非这个被包装数组的大小**。每个 ArrayList 实例都有一个容量，该容量是指用来存储列表元素的数组的大小,并且它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝。因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量，这可以减少递增式再分配的数量。<br />        注意，此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改(结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改.)了列表，**那么它必须保持外部同步？？。**
  1. ArrayList 实现了 Serializable 接口，因此它支持序列化，能够通过序列化传输。阅读源码可以发现，ArrayList内置的数组用 transient 关键字修饰，以示其不会被序列化。当然，ArrayList的元素最终还是会被序列化的，在序列化/反序列化时，会调用 ArrayList 的 writeObject()/readObject() 方法，将该 ArrayList中的元素（即0…size-1下标对应的元素） 和 容量大小 写入流/从流读出。这样做的好处是，只保存/传输有实际意义的元素，最大限度的节约了存储、传输和处理的开销。

ArrayList 实现了 RandomAccess 接口， 支持快速随机访问，实际上就是通过下标序号进行快速访问(于是否支持get(index)访问不同)。RandomAccess 接口是 List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。特别地，在对List的遍历算法中，要尽量来判断是属于 RandomAccess(如ArrayList) 还是 SequenceAccess(如LinkedList），因为适合RandomAccess List的遍历算法，用在SequenceAccess List上就差别很大，即对于实现了RandomAccess接口的类实例而言，此循环
for (int i=0, i的运行速度要快于以下循环：
for (Iterator i=list.iterator(); i.hasNext(); ) i.next();
所以，我们在遍历List之前，可以用 if( list instanceof RamdomAccess ) 来判断一下，选择用哪种遍历方式。

ArrayList 实现了Cloneable接口 ，能被克隆 。Cloneable 接口里面没有任何方法，只是起一个标记作用，表明当一个类实现了该接口时，该类可以通过调用clone()方法来克隆该类的实例。

扩容机制

  1.     向 ArrayList 中增加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度。如果超出，ArrayList 将会进行扩容，以满足添加数据的需求。数组扩容通过一个 public 方法 ensureCapacity(int minCapacity) 来实现 : 在实际添加大量元素前，我们也可以使用 ensureCapacity 来手动增加 ArrayList 实例的容量，以减少递增式再分配的数量。 <br />     ArrayList 进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长为其原容量的 1.5 倍 + 1。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用 ensureCapacity 方法来手动增加ArrayList实例的容量。

小结

三个不同的构造方法。无参构造方法构造的ArrayList的容量默认为10； 带有Collection参数的构造方法的实现是将Collection转化为数组赋给ArrayList的实现数组elementData。扩充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就设置新的容量为旧的容量的1.5倍加1，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量）。之后，用 Arrays.copyof() 方法将元素拷贝到新的数组。从中可以看出，当容量不够时，每次增加元素，都要将原来的元素拷贝到一个新的数组中，非常之耗时，也因此建议在事先能确定元素数量的情况下，才使用ArrayList，否则建议使用LinkedList。ArrayList 的实现中大量地调用了Arrays.copyof() 和 System.arraycopy()方法 。我们有必要对这两个方法的实现做下深入的了解。首先来看Arrays.copyof()方法。它有很多个重载的方法，但实现思路都是一样的
ArrayList 基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此 查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低；在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理，ArrayList中允许元素为null。

说一下 ArrayList 的优缺点

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

  • ArrayList 的缺点如下：ArrayList 比较适合顺序添加、随机访问的场景。

  • 数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。

  • 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
  • 因为ArrayList 是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的，可以直接返回数组中index位置的元素，因此在随机访问集合元素上有较好的性能。ArrayList 获取数据的时间复杂度是O(1),但是要插入、删除数据却是开销很大的，因为这需要移动数组中插入位置之后的的所有元素。
  • 相对于ArrayList，LinkedList的随机访问集合元素时性能较差，因为需要在双向列表中找到要index的位置，再返回；但在插入，删除操作是更快的。因为LinkedList不像ArrayList一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是ArrayList最坏的一种情况，时间复杂度是O(n)，而LinkedList中插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据时还需要更新索引（除了插入数组的尾部）。
  • 另外LinkedList类不仅是List接口的实现类，可以根据索引来随机访问集合中的元素，除此之外，LinkedList还实现了Deque接口，Deque接口是Queue接口的子接口，它代表一个双向队列，因此LinkedList可以作为双向队列 ，栈（可以参见Deque提供的接口方法）和List集合使用，功能强大。
  • LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置。
  • 线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

使用场景：
（1）如果应用程序对数据有较多的随机访问，ArrayList对象要优于LinkedList对象；
( 2 ) 如果应用程序有更多的插入或者删除操作，较少的随机访问，LinkedList对象要优于ArrayList对象；
（3）不过ArrayList的插入，删除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移动较少的数据，而LinkedList则需要一直查找到列表尾部，反而耗费较多时间，这时ArrayList就比LinkedList要快。

ArrayList 和 Vector 的区别是什么？

这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合

  • 线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。
  • 性能：ArrayList 在性能方面要优于 Vector。

  • 扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。

    插入数据时，ArrayList、LinkedList、Vector谁速度较快？阐述 ArrayList、Vector、LinkedList 的存储性能和特性？

    ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据???LinkedList不是双向链表吗。数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。
    Vector 中的方法由于加了 synchronized 修饰，因此 Vector 是线程安全容器，但性能上较ArrayList差。
    LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需要记录当前项的前后项即可，所以 LinkedList 插入速度较快。

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

    ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用

    数组(Array)和列表(ArrayList)有什么区别？什么时候应该使用Array而不是ArrayList？

    下面列出了Array和ArrayList的不同点：1、Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。2、Array大小是固定的，ArrayList的大小是动态变化自动扩展的。3、ArrayList提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等。4、对于基本类型数据，集合使用自动装箱来减少编码工作量。但是，当处理固定大小的基本数据类型的时候，这种方式相对比较慢。

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

  • Array 转 List： Arrays. asList(array) ；

  • List 转 Array：List 的 toArray() 方法。

    ArrayList和LinkedList有什么区别？

    ArrayList和LinkedList都实现了List接口，他们有以下的不同点：ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。与此对应，LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。也可以参考ArrayList vs. LinkedList。

    comparable 和 comparator的区别？

  • comparable接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序

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

一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo方法或compare方法，当我们需要对某一个集合实现两种排序方式，比如一个song对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的Collections.sort().

其他

HashSet

HashSet这个类实现了Set集合，但它实际是一个HashMap的实例，因为它的构造方法就是直接new了一个HashMap的示例。
对集合的迭代次序没有任何保证; 特别是，它不能保证订单会随着时间的推移保持不变。这个类允许null 元素。
HashSet提供了三个构造函数：
无参数的构造函数，此构造函数创建一个大小为16的容器，加载因子为0.75（容器的大小始终是2的幂，默认为16不在赘述，在后面文章中介绍另外的构造函数，添加指定值的时候会介绍程序是如何保证始终是2的冥，透露一点如果我们传值为5的一个容器大写，那么创建的容器实际大小为8，感兴趣的可以先去看一下算法。），具体看一下实例化一个hashSet的具体参数，并且为了保证速度，我们在实例化的这个参数的时候尽量不要把容器设置的太大，或者加载因子设置太小，后面在说得到HashSet的另外三个构造函数。
Set set =new HashSet<>();

TreeMap 和 TreeSet 在排序时如何比较元素？Collections 工具类中的 sort()方法如何比较元素？

TreeSet 要求存放的对象所属的类必须实现 Comparable 接口，该接口提供了比较元素的 compareTo()方法，当插入元素时会回调该方法比较元素的大小。
TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。
Collections 工具类的 sort 方法有两种重载的形式，
第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较；
第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator 接口的子类型（需要重写 compare 方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java 中对函数式编程的支持）。