汇合框架

1. Java 汇合框架概述

1.1 什么是汇合框架

如果一个程序只蕴含固定数量的且其生命周期都是已知的对象，那么这是一个非常简单的程序。

通常，程序总是依据运行时才晓得的某些条件去创立新对象。在此之前，不会晓得你所须要对象的数量，甚至不晓得确切的类型。为了解决这个广泛的编程问题，须要在任意时刻和任意地位创立任意数量的对象。所以，就不能依附创立命名的援用来持有每一个对象，因为你不晓得实际上会须要多少这样的援用 ——Thinking in Java

首先晓得咱们所学习的 Java 语言是一个齐全 面向对象 的语言，而这种语言对事物的形容是通过对象体现的，为了不便 对多个对象进行操 作，咱们就必须把这多个 对象进行存储。

一个根本类型的变量显然是无奈满足存储多个对象的，所以应该是一个 容器类型 的变量，通过后面的常识，咱们晓得数组和 StringBuffer、StringBuilder 均属于容器类型。然而呢? StringBuffer 的后果是一个字符串，不肯定满足咱们的要求，所以咱们只能抉择数组，这就是对象数组。

可是问题又来了，对象数组 又不能适应变动的需要，因为数组的 长度是固定的 ，而且他不能依据咱们的操作（增删改查）抉择最好的策略，这个时候，为了适应变动的需要，Java 就提供了 汇合类 供咱们应用。

1.1.1 数组和汇合的区别?

首先数组的 长度固定 ，而汇合的 长度可变 ，其次数组存储的是 同一种类型 的元素，而汇合能够存储 不同类型 的元素，最初数组能够 存储根本数据类型 ，也能够 存储援用数据类型

尽管数组看起来有一丝不太灵便，但数组也的确是保留一组对象的无效办法，如果想要保留一组根本数据类型，咱们也举荐应用这种办法，只是因为其长度固定，导致它在很多时候也受到一些限度。

1.1.1.1 汇合的弹性空间调配须要开销

在 Java 中，数组是一种效率最高的存储和随机拜访对象的援用序列的形式。数组就是一个简略的线性序列，这使得元素拜访十分疾速。然而为这种速度所付出的代价是数组对象的大小被固定，并且在其生命周期中不可扭转。你可能会倡议应用 ArrayList，它能够通过创立一个新实例，而后把旧实例中所有的援用到移到新实例中，从而实现更多空间的主动调配。只管通常应该首选 ArrayList 而不是数组、然而这种弹性须要开销，因而，ArrayList 的效率比数组低很多。——Thinking in Java 第 16 章

1.2 汇合框架体系结构

根本常见的汇合框架就是下图所示，还有一些非凡的没写进去，例如 ConcurrentHashMap 等等

简略看一下其体系结构

Collection

Map

1.3 请阐明 Java 汇合类框架的根本接口有哪些？

首先汇合类操作的对象，咱们称为元素，而汇合类接口的每一种具体的实现类都能够抉择以它本人的形式对元素进行保留和排序。有的汇合类容许反复的键，有的则不容许。

Java 汇合类外面最根本的接口有：

• Collection：代表一组对象，每一个对象都是它的子元素。
• List：有程序的 collection，并且能够蕴含反复元素（程序）。
• Set：不保障有序，同时不蕴含反复元素的 Collection（惟一）。
• Map：能够把 键(key) 映射到 值(value) 的对象，键不能反复（键值对）。

1.4 说一说 Java 常见汇合的数据结构以及其特点

1.4.1 List

• ArrayList：Object 数组（查问快，增删慢，线程不平安，效率高）
• Vector：Object 数组（查问快，增删慢，线程平安，效率低）
• LinkedList：双向链表，JDK1.6 之前是循环链表，JDK1.7 勾销了循环（查问慢，增删快，线程不平安，效率高）

1.4.2 Map

• HashMap：JDK1.8 之前 HashMap 由数组 + 链表组成的，数组是 HashMap 存储元素的主体，链表则是次要为了解决哈希抵触而存在的，即“拉链法”解决抵触。JDK1.8 当前在解决哈希抵触时有了较大的变动，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以缩小搜寻工夫（哈希表对键进行散列，Map 构造即映射表寄存键值对）
• LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层依然是基于拉链式散列构造即由数组和链表或红黑树组成。另外，LinkedHashMap 在下面构造的根底上，减少了一条双向链表，使得键值对的插入程序以及拜访程序等逻辑能够得以实现。
• Hashtable：数组 + 链表组成的，数组是 HashMap 的主体，链表则是次要为了解决哈希抵触而存在的
• TreeMap：红黑树（均衡二叉排序树）

1.4.3 Set

• HashSet: 基于 HashMap 实现的，底层采纳 HashMap 来保留元素（不保障有序，惟一）
• LinkedHashSet：LinkedHashSet 继承与 HashSet，并且其外部是通过 LinkedHashMap 来实现的。有点相似于咱们之前说的 LinkedHashMap 其外部是基于 Hashmap 实现一样，不过还是有一点点区别的。
• TreeSet：红黑树，自均衡的排序二叉树（可实现天然排序，例如 a-z）

1.5 Collection 和 Collections 的区别

• Collection 是汇合的下级接口，继承它的有 Set 和 List 接口
• Collections 是汇合的工具类，提供了一系列的静态方法对汇合的搜寻、查找、同步等操作

1.6 请简略阐明一下什么是迭代器？

Iterator 提供了遍历及操作汇合元素的接口，而 Collection 接口实现 Iterable 接口，也就是说，每个汇合都通过实现 Iterable 接口中 iterator() 办法返回 Iterator 接口的实例，而后对汇合的元素进行迭代操作。

有一点须要留神的是：在迭代元素的时候不能通过汇合的办法删除元素, 否则会抛出 ConcurrentModificationException 异样. 然而能够通过 Iterator 接口中的 remove() 办法进行删除，同现实要减少元素，就能够应用 ListIterator 的 add 办法（ListIterator 领有 add、set、remove 办法，Iterator 领有 remove 办法）

1.7 请你说说 Iterator 和 ListIterator 的区别？

Iterator 可用来遍历 Set 和 List 汇合，然而 ListIterator 只能用来遍历 List。

• Iterator 只能 remove() 元素，而 ListIterator 能够 add()、set()、remove()

• Iterator 只能应用 next() 程序的向后遍历，ListIterator 则向前 previous()和向后 next() 遍历都能够

  • 还有一个额定的性能，ListIterator 能够应用 nextIndex() 和 previousIndex() 获得以后游标位置的前后 index 地位，Iterator 没有此性能

可参考：Java – Iterator 和 ListIterator

1. List 接口

2.1 论述 ArrayList 别离与 Vector、LinkedList 的异同点

2.1.1 ArrayList 与 Vector

ArrayList 是当初 List 的一种次要实现类，而 Vector 曾经是过期的 Java 遗留容器

• 同：两者都是应用 Object 数组形式存储数据，均能够实现扩容且容许间接按序号查问（索引）元素，然而插入元素要波及数组元素挪动等内存操作，所以两者 查问数据快而插入数据慢
• 异：Vector 中的办法因为增加了 synchronized 润饰，因而 Vector 是线程平安的容器，但性能上较 ArrayList 差

2.1.2 ArrayList 与 LinkedList

• 数据结构：ArrayList 是 Object 数组，LinkedList 是双向链表（JDK1.6 之前是循环链表，JDK1.7 勾销了循环）

  • 查问效率：ArrayList 反对高效的随机元素拜访，即通过下标疾速获取元素对象。而 LinkedList 不反对，所以 ArrayList 的查问效率更高
  • 增删效率：ArrayList 底层是数组存储，所以插入和删除元素的工夫复杂度与元素插入的地位无关，因为会波及到元素的挪动问题，例如追加在开端，则工夫复杂度为 O(1)，若在首部插入，则工夫复杂度为 O(n)，两头任意地位插入，工夫复杂度为，为 O((n - 1) / 2)，均匀工夫复杂度还是 O(n) 而 LinkedList 采纳的是链表存储，所以增删不会波及到元素的挪动，只须要批改指针即可，工夫复杂度能够简略看为 O(1)，然而要是在指定地位增删元素的话，须要先挪动到指定地位再插入，以这个角度看工夫复杂度为 O(n)
• 线程平安：ArrayList 和 LinkedListed 都是非线程平安的，如果遇到多个线程操作同一个容器的场景，则能够通过工具类 Collections 中的 synchronizedList 办法将其转换成线程平安的容器后再应用（这是对装潢模式的利用，将已有对象传入另一个类的结构器中创立新的对象来加强实现）。
• 内存耗费：LinkedListed 每一个元素都须要寄存前驱和后继节点的地址，所以每一个元素都更加耗费空间，而 ArrayList 只有是在结尾会预留肯定的容量空间，这是扩容所导致的不能充沛填满数组的状况（除非应用办法瘦身）

2.2 ArrayLsit 扩容机制和并发批改异样（请跳转）

在 001-ArrayList 源码剖析（含扩容机制等重点问题剖析）文章中，我做过具体的剖析，篇幅过长，可跳转浏览。

2.3 ArrayList 汇合退出指定大量数据，应该怎么提高效率

ArrayList 的默认初始容量为 10，要插入大量数据的时候须要一直扩容，而扩容是十分影响性能的，在已知数据量的状况下，能够间接在初始化的时候就设置 ArrayList 的容量，以提高效率。

1. Set 接口

3.1 Set 无序性是怎么了解的

无序性是指存储的数据在底层数组中并非依照数组索引的程序增加，而是依据数据的哈希值决定的。

具体分析可参考我在知乎的答复：Java 遍历 HashSet 为什么输入是有序的？@BWH_Steven 的答案

这个问题十分值得深入分析，对于 Set 和 Map 源码的了解很有帮忙！！！

3.2 1.4.4. HashSet 如何查看反复

当你把对象退出 HashSet 时，HashSet 会先计算对象的 hashcode 值来判断对象退出的地位，同时也会与其余退出的对象的 hashcode 值作比拟，如果没有相符的 hashcode，HashSet 会假如对象没有反复呈现。然而如果发现有雷同 hashcode 值的对象，这时会调用 equals() 办法来查看 hashcode 相等的对象是否真的雷同。如果两者雷同，HashSet 就不会让退出操作胜利。——《Head fist java》第二版

1. Map 接口

4.1 HashMap 与 HashTable、HashSet、HashMap 等的区别

4.1.1 HashMap 与 HashTable

• 数据结构：HashMap JDK1.8 当前在解决哈希抵触时有了较大的变动，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以缩小搜寻工夫，不过在转为红黑树前会判断，如果数组长度小于 64，还是会优先进行数组扩容（哈希表对键进行散列，Map 构造即映射表寄存键值对），而 HashTable 没有这种非凡的机构。
• 线程平安：HashMap 是非线程平安的，而 HashTable 属于线程平安的（办法增加了 synchronized 润饰），因而，HashMap 效率也会略高，通常认为，HashTable 相似 Vector 是一个 Java 遗留类，根本不做应用。想保障线程平安，能够思考应用 ConcurrentHashMap。
• Null 的解决：HashMap 的键和值都能够存储为 null 的类型，然而只能有一个 null 类型的键，然而 null 类型的值能够有多个。HashTable 的键和值都不容许有 null 类型呈现，否则会抛出空指针异样。
• 扩容机制：不指定初始值的时候，HashMap 初始值为 16，之后每次扩容，容量会成为原先的两倍，HashTable 初始值为 11，扩容会使得容量成为原先的 2n + 1。若指定了初始值，HashMap 会将其裁减为 2 的幂次方大小，而 HashTable 会间接应用你给的初始值。

4.1.2 HashMap 与 HashSet

• HashMap 实现了 Map 接口，HashSet 实现了 Set 接口。
• HashMap 贮存键值对，HashSet 仅仅存储对象。
• 应用 put() 办法将元素放入 map 中 应用 add() 办法将元素放入 set 中，但 add() 办法理论调用的还是 HashMap 中的 put() 办法。
• HashMap 中应用键对象来计算 hashcode 值 HashSet 应用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能雷同，所以 equals() 办法用来判断对象的相等性，如果两个对象不同的话，那么返回 false。
• HashMap 比拟快，因为是应用惟一的键来获取对象，HashSet 较 HashMap 来说比较慢。

4.1.3 HashMap 与 TreeMap

• 程序问题：HashMap 中的元素是没有程序的，TreeMap 中所有的元素都是有某一固定程序的。
• 线程平安：HashMap 和 TreeMap 都不是线程平安的
• 继承问题：HashMap 继承 AbstractMap 类；笼罩了 hashcode() 和 equals() 办法，以确保两个相等的映射返回雷同的哈希值。TreeMap 继承 SortedMap 类，放弃键的有序程序。
• 调优问题：HashMap 基于哈希表实现的，应用 HashMap 要求增加的键类明确定义了 hashcode() 和 equals()（能够重写该办法）；为了优化 HashMap 的空间应用，能够调优初始容量和负载因子。而 TreeMap 基于红黑树实现，所以 TreeMap 就没有调优选项，因为红黑树总是处于均衡的状态。
• 实用场景：HashMap 实用于 Map 插入，删除，定位元素，TreeMap 实用于按天然程序或自定义程序遍历键（key）。

4.2 HashMap 的长度为什么是 2 的幂次方

HashSet 因为底层应用 哈希表（链表联合数组）实现，存储时 key 通过一些运算后得出本人在数组中所处的地位。咱们在 hashCoe 办法中返回到了一个等同于自身值的散列值，然而思考到 int 类型数据的范畴：-2147483648~2147483647，着很显然，这些散列值不能间接应用，因为内存是没有方法放得下，一个 40 亿长度的数组的。所以它应用了对数组长度进行 取模运算 ，得余后再作为其数组下标，indexFor() ——JDK7 中，就这样呈现了，在 JDK8 中 indexFor() 就隐没了，而全副应用上面的语句代替，原理是一样的。

// JDK8 中
(tab.length - 1) & hash；复制代码

// JDK7 中
bucketIndex = indexFor(hash, table.length);

static int indexFor(int h, int length) {return h & (length - 1);
}
复制代码

能够看到其本质计算方法都是 (length - 1) & hash 提一句，为什么取模运算时咱们用 & 而不必 % 呢，因为位运算间接对内存数据进行操作，不须要转成十进制，因而处理速度十分快，这样就导致位运算 & 效率要比取模运算 % 高很多。

最要害的内容来了，如果咱们用更容易了解的取余（%），length % hash == (length - 1) & hash 这个公式想要成立的前提，就必须满足 length 是 2 的 n 次方

简略的说：HashMap 的长度为什么是 2 的幂次方的起因就是，咱们为了应用更加高效的 & 运算而不是 % 运算，但又为了保障运算的后果，依然是取余操作。

4.3 hash() 中的扰动函数如何解决 Hash 抵触 ※

003-HashMap 源码剖析（含散列表和红黑树介绍）

其中【3.1 hash() 中的扰动函数如何解决 Hash 抵触 ※】具体叙述了扰动函数的执行流程和作用，请跳转查阅。

4.4 简略谈谈 HashMap 中的底层原理

4.4.1 JDK 1.8 之前

JDK1.8 之前 HashMap 底层是数组 + 链表，HashMap 会应用 hashCode 以及扰动函数解决 key，而后获取一个 hash 值，而后通过 (length- 1) & hash 判断以后元素应该寄存的地位，如果这个地位存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否雷同，如果雷同的话，间接笼罩，不雷同就通过拉链法解决抵触。

扰动函数在 4.3 中讲述的应该很分明了

拉链法的解释，同样能够参考 003-HashMap 源码剖析（含散列表和红黑树介绍）

4.4.2 JDK 1.8

JDK 8 做了一些较大的调整，当数组中每个格子里的链表，长度大于阈值（默认为 8）时，将链表转化为红黑树，就能够大大的缩小搜寻工夫，不过在转为红黑树前会判断，如果数组长度小于 64，还是会优先进行数组扩容。

4.5 HashMap 中加载因子的了解

• 加载因子就是示意哈希表中元素填满的水平，当表中元素过多，超过加载因子的值时，哈希表会主动扩容，个别是一倍，这种行为能够称作 rehashing（再哈希）。
• 加载因子的值设置的越大，增加的元素就会越多，的确空间利用率的到了很大的晋升，然而毫无疑问，就面临着哈希抵触的可能性增大，反之，空间利用率造成了节约，但哈希抵触也缩小了，所以咱们心愿在空间利用率与哈希抵触之间找到一种咱们所能承受的均衡，通过一些试验，定在了 0.75f。

4.6 ConcurrentHashMap 和 Hashtable 的区别

HashTable 尽管也满足线程平安，然而相似 Vector，是一个 Java 遗留类，根本不做应用。想保障线程平安，能够思考应用 ConcurrentHashMap。

数据结构：JDK 1.7 中，ConcurrentHashMap 底层采纳分段数组 + 链表实现，在 JDK 1.8 中，ConcurrentHashMap 中的数据结构与 HashMap 统一，都是数组 + 链表或红黑树。而 Hashtable 采纳的是数组 + 链表的模式（数组为主体，链表用来解决哈希抵触）

线程平安：ConcurrentHashMap 在 JDK 1.7 的时候，有一个分段锁的概念，也就是对整个数组进行宰割开来（这就是 Segment 的概念），每一把锁，只负责整个锁分段中的一部分，而如果多线程拜访不同数据段的数据，锁的竞争也就不存在了，拜访并法律也因而进步。而在 JDK 1.8 的时候，间接用 Node 数组 + 链表或红黑树实现，通过 synchronized（JDK 1.6 后优化了很多）和 CAS 进行并发的管制。Hashtable 就是用一把锁 synchronized 来保障线程平安，效率不是很高，多线程下，很可能会陷入阻塞轮询状态。

• 注：尽管 JDK 1.8 的源码中还能看到 Segment，然而次要也只是为了兼容旧版本了

参考：《2020 最新 Java 根底精讲视频教程和学习路线！》
链接：https://juejin.cn/post/693561…