Java基础-Java集合框架

集合框架

HashMap

在 JDK 1.8，HashMap 底层是由 “数组+链表+红黑树” 组成，如下图所示，而在 JDK 1.8 之前是由 “数组+链表” 组成。

使用 “数组+链表” 是为了解决 hash 冲突的问题。

数组和链表有如下特点：

数组：查找容易，通过 index 快速定位；插入和删除困难，需要移动插入和删除位置之后的节点；
链表：查找困难，需要从头结点或尾节点开始遍历，直到寻找到目标节点；插入和删除容易，只需修改目标节点前后节点的 next 或 prev 属性即可；

HashMap 巧妙的将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做 “拉链法” 的方式来解决哈希冲突。
首先通过 index 快速定位到索引位置，这边利用了数组的优点；然后遍历链表找到节点，进行节点的新增/修改/删除操作，这边利用了链表的优点。

为什么要改成“数组+链表+红黑树”？

“数组+链表” 在定位到索引位置后，需要先遍历链表找到节点，这个地方如果链表很长的话，也就是 hash 冲突很严重的时候，会有查找性能问题，因此在 JDK1.8 中，通过引入红黑树，来优化这个问题。
使用链表的查找性能是 O(n)，而使用红黑树是 O(logn)。

那在什么时候用链表？什么时候用红黑树？

对于插入，默认情况下是使用链表节点。当同一个索引位置的节点在新增后超过 8 个（阈值 8）：如果此时数组长度大于等于 64，则会触发链表节点转红黑树节点（treeifyBin）；而如果数组长度小于 64，则不会触发链表转红黑树，而是会进行扩容，因为此时的数据量还比较小。

对于移除，当同一个索引位置的节点在移除后达到 6 个（阈值 6），并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）。

为什么链表转红黑树的阈值是 8？

我们平时在进行方案设计时，必须考虑的两个很重要的因素是：时间和空间。对于 HashMap 也是同样的道理，简单来说，阈值为 8 是在时间和空间上权衡的结果。

红黑树节点大小约为链表节点的 2 倍，在节点太少时，红黑树的查找性能优势并不明显，付出 2 倍空间的代价不值得。

理想情况下，使用随机的哈希码，节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的公式计算，链表中节点个数为 8 时的概率为 0.00000006，这个概率足够低了，并且到 8 个节点时，红黑树的性能优势也会开始展现出来，因此 8 是一个较合理的数字。

那为什么转回链表节点是用的 6 而不是复用 8？

如果我们设置节点多于 8 个转红黑树，少于 8 个就马上转链表，当节点个数在 8 徘徊时，就会频繁进行红黑树和链表的转换，造成性能的损耗。

HashMap 有哪些重要属性？分别用于做什么的？

除了用来存储我们的节点 table 数组外，HashMap 还有以下几个重要属性：
1）size：HashMap 已经存储的节点个数；
2）threshold：1）扩容阈值（主要），当 HashMap 的个数达到该值，触发扩容。2）初始化时的容量，在我们新建 HashMap 对象时， threshold 还会被用来存初始化时的容量。HashMap 直到我们第一次插入节点时，才会对 table 进行初始化，避免不必要的空间浪费。
3）loadFactor：负载因子，扩容阈值 = 容量 * 负载因子。

HashMap 的默认初始容量是多少？HashMap 的容量有什么限制吗？

默认初始容量是 16。HashMap 的容量必须是 2 的 N 次方，HashMap 会根据我们传入的容量计算一个“大于等于该容量的最小的 2 的 N 次方”，例如传 16，容量为 16；传 17，容量为 32。

HashMap 的容量必须是 2 的 N 次方，这是为什么？

计算索引位置的公式为：**(n - 1) & hash**

当 n 为 2 的 N 次方时，n - 1 为低位全是 1 的值，此时任何值跟 n - 1 进行 & 运算的结果为该值的低 N 位，达到了和取模同样的效果，实现了均匀分布。

实际上，这个设计就是基于式：
x mod 2^n = x & (2^n - 1)，因为 & 运算比 mod 具有更高的效率。

插入流程

ConcurrenHashMap，1.7 和 1.8 的区别

ConcurrentHashMap 是 HashMap 的线程安全版本，和 HashMap 一样，在 JDK 1.8 中进行了较大的优化。

JDK1.7：底层结构为：分段的数组+链表；实现线程安全的方式：分段锁（Segment，继承 ReentrantLock），

JDK1.8：底层结构为：数组+链表+红黑树；实现线程安全的方式：CAS + Synchronized，synchronized 只会锁定当前链表或者红黑树的首节点。效率大大提高。

区别：

1、JDK1.8 中降低锁的粒度。JDK1.7 版本锁的粒度是基于 Segment 的，包含多个节点（HashEntry），而 JDK1.8 锁的粒度就是单节点（Node）。

2、JDK1.8 版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用 synchronized 来进行同步，所以不需要分段锁的概念，也就不需要 Segment 这种数据结构了，当前还保留仅为了兼容。

3、JDK1.8 使用红黑树来优化链表，跟 HashMap 一样，优化了极端情况下，链表过长带来的性能问题。

4、JDK1.8 使用内置锁 synchronized 来代替重入锁 ReentrantLock，synchronized 是官方一直在不断优化的，现在性能已经比较可观，也是官方推荐使用的加锁方式

map 对比？

对比

ArrayList 和 Vector 的区别

Vector 和 ArrayList 的实现几乎是一样的，区别在于：

1）最重要的的区别：Vector 在方法上使用了 synchronized 来保证线程安全，同时由于这个原因，在性能上 ArrayList 会有更好的表现。

2） Vector 扩容后容量默认变为原来 2 倍，而 ArrayList 为原来的 1.5 倍。

ArrayList 和 LinkedList 的区别？

arraylist 扩容

第一种情况，当 ArrayList 的容量为 0 时，此时添加元素的话，需要扩容，三种构造方法创建的 ArrayList 在扩容时略有不同：

1.无参构造，创建 ArrayList 后容量为 0，添加第一个元素后，容量变为 10，此后若需要扩容，则正常扩容。

2.传容量构造，当参数为 0 时，创建 ArrayList 后容量为 0，添加第一个元素后，容量为 1，此时 ArrayList 是满的，下次添加元素时需正常扩容。

3.传列表构造，当列表为空时，创建 ArrayList 后容量为 0，添加第一个元素后，容量为 1，此时 ArrayList 是满的，下次添加元素时需正常扩容。

第二种情况，当 ArrayList 的容量大于 0，并且 ArrayList 是满的时，此时添加元素的话，进行正常扩容，每次扩容到原来的 1.5 倍。

1、ArrayList 底层基于动态数组实现，LinkedList 底层基于双向链表实现。

2、对于随机访问（按 index 访问，get/set 方法）：ArrayList 通过 index 直接定位到数组对应位置的节点，而 LinkedList 需要从头结点或尾节点开始遍历，直到寻找到目标节点，在效率上 ArrayList 优于 LinkedList。

3、对于随机插入和删除：ArrayList 需要移动目标节点后面的节点（使用 System.arraycopy 方法移动节点），而 LinkedList 只需修改目标节点前后节点的 next 或 prev 属性即可，因此在效率上 LinkedList 优于 ArrayList。

4、对于顺序插入和删除：由于 ArrayList 不需要移动节点，因此在效率上比 LinkedList 更好。这也是为什么在实际使用中 ArrayList 更多，因为大部分情况下我们的使用都是顺序插入。

5、两者都不是线程安全的。

6、内存空间占用： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

hashmap 对比 hashtable

线程安全：hashmap 不安全，hashtable 安全（方法被 synchronized 修饰过）。

效率：hashtable 效率很低，被淘汰。

null key value？：hashmap 支持一个 null key。hashtable 不支持。

扩容：hashtable 初始：不指定的话为 11，之后变为原来的 2n+1。hashmap 初始 16，每次扩充两倍。hashmap 在指定了初始容量后会扩充为 2 的幂次大小。

底层：解决 hash 冲突，hashmap 在链表大于 8 会转化成红黑树（如果数组长度小于 64，会先进性扩容）。

List、Set、Map 三者的区别?

List（对付顺序的好帮手）： 存储的对象是可重复的、有序的。
Set（注重独一无二的性质）：存储的对象是不可重复的、无序的。
Map（用 Key 来搜索的专业户）: 存储键值对（key-value），不能包含重复的键（key），每个键只能映射到一个值

map 遍历方式

HashMap 遍历从大的方向来说，可分为以下 4 类：

迭代器（Iterator）方式遍历；

For Each 方式遍历；

Lambda 表达式遍历（JDK 1.8+）;

Streams API 遍历（JDK 1.8+）。

使用迭代器（Iterator）EntrySet 的方式进行遍历；

使用迭代器（Iterator）KeySet 的方式进行遍历；

使用 For Each EntrySet 的方式进行遍历；

使用 For Each KeySet 的方式进行遍历；

使用 Lambda 表达式的方式进行遍历；

使用 Streams API 单线程的方式进行遍历；

使用 Streams API 多线程的方式进行遍历

EntrySet 之所以比 KeySet 的性能高是因为，**KeySet 在循环时使用了 map.get(key)**，而 map.get(key) 相当于又遍历了一遍 Map 集合去查询 key 所对应的值。为什么要用“又”这个词？那是因为在使用迭代器或者 for 循环时，其实已经遍历了一遍 Map 集合了，因此再使用 map.get(key) 查询时，相当于遍历了两遍。

而 EntrySet 只遍历了一遍 Map 集合，之后通过代码“Entry<Integer, String> entry = iterator.next()”把对象的 key 和 value 值都放入到了 Entry 对象中，因此再获取 key 和 value 值时就无需再遍历 Map 集合，只需要从 Entry 对象中取值就可以了。

所以，EntrySet 的性能比 KeySet 的性能高出了一倍，因为 KeySet 相当于循环了两遍 Map 集合，而 EntrySet 只循环了一遍。

我们不能在遍历中使用集合 map.remove() 来删除数据，这是非安全的操作方式，但我们可以使用迭代器的 iterator.remove() 的方法来删除数据，这是安全的删除集合的方式。

同样的我们也可以使用 Lambda 中的 removeIf 来提前删除数据，或者是使用 Stream 中的 filter 过滤掉要删除的数据进行循环，这样都是安全的，当然我们也可以在 for 循环前删除数据在遍历也是线程安全的。

综合性能和安全性来看，我们应该尽量使用迭代器（Iterator）来遍历 EntrySet 的遍历方式来操作 Map 集合，这样就会既安全又高效。

Comparable 和 Comparator 比较？

1、Comparable 是排序接口，一个类实现了 Comparable 接口，意味着“该类支持排序”。Comparator 是比较器，我们可以实现该接口，自定义比较算法，创建一个 “该类的比较器” 来进行排序。

2、Comparable 相当于“内部比较器”，而 Comparator 相当于“外部比较器”。

3、Comparable 的耦合性更强，Comparator 的灵活性和扩展性更优。

4、Comparable 可以用作类的默认排序方法，而 Comparator 则用于默认排序不满足时，提供自定义排序

Collection 与 Collections 的区别

Collection：集合类的一个顶级接口，提供了对集合对象进行基本操作的通用接口方法。Collection 接口的意义是为各种具体的集合提供了最大化的统一操作方式，常见的 List 与 Set 就是直接继承 Collection 接口。

Collections：集合类的一个工具类/帮助类，提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作

其他

HashSet 是如何保证不重复的？

HashSet 底层使用 HashMap 来实现，元素放在 HashMap 的 key 里，value 为固定的 Object 对象。

当 add 时调用 HashMap 的 put 方法，如果元素不存在，则返回 null 表示 add 成功，否则 add 失败。

由于 HashMap 的 Key 值本身就不允许重复，HashSet 正好利用 HashMap 中 key 不重复的特性来校验重复元素。

Map、List、Set 它们有的线程安全类和线程不安全的类？

Map

线程安全：CocurrentHashMap、Hashtable
线程不安全：HashMap、LinkedHashMap、TreeMap、WeakHashMap

List

线程安全：Vector（线程安全版的 ArrayList）、Stack（继承 Vector，增加 pop、push 方法）、CopyOnWriteArrayList
线程不安全：ArrayList、LinkedList

Set

线程安全：CopyOnWriteArraySet（底层使用 CopyOnWriteArrayList，通过在插入前判断是否存在实现 Set 不重复的效果

线程不安全：HashSet（基于 HashMap）、LinkedHashSet（基于 LinkedHashMap）、TreeSet（基于 TreeMap）、EnumSe