1. 数据结构
1.1.1 Collection接口
- Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。
1.1.2 Map接口
- Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。
1.1.3 Map接口和Collection接口区别
- Collection和Map接口之间的主要区别在于：Collection中存储了一组对象，而Map存储关键字/值对。
1.2 HashMap和HashSet
1.2.1 HashMap
- HashMap就是一种Key-Value的方式进行数据存储的数据结构。
- JDK 1.7 中 HashMap 的底层数据结构是数组 + 链表，使用 Entry 类存储 Key 和 Value；
- JDK 1.8 中 HashMap 的底层数据结构是数组 + 链表/红黑树，使用 Node 类存储 Key 和 Value。
- Entry 和 Node 是一样的
- HashMap的真实数据结构：
- 当table数组大于64且链表的长度大于8的时候，就会扩容。
HashMap元素存储的过程
- 根据key会计算出一个hash值，然后根据这个hash值在对应的数组里面进行插入操作。如果这个数据索引下已经有了一个元素，并且不等于插入元素，就会使用链表进行尾插法的操作。
扩容的步骤
- 扩容 resize 分为两步：
- 1）扩容：创建一个新的 Entry/Node 空数组，长度是原数组的 2 倍
- 2）ReHash：遍历原 Entry/Node 数组，把所有的 Entry/Node 节点重新 Hash 到新数组
- ReHash的原因：
- hash的计算原理是：index = HashCode(key) & (Length - 1)
- 因为数组的长度改变以后，Hash 的规则也随之改变。所以需要重新hash
JDK1.8以后使用尾插法的原因
- 因为采用头插法会导致循环链表的问题
- 由于 JDK 1.7 中 HashMap 使用头插会改变链表上元素的的顺序，在旧数组向新数组转移元素的过程中修改了链表中节点的引用关系，因此 JDK 1.8 改成了尾插法，在扩容时会保持链表元素原本的顺序，避免了链表成环的问题。
为什么链表转化为红黑树的长度限制为8
- 因为红黑树所占的空间是普通链表节点的两倍，但是查找的时间复杂度低，所以只有当节点特别多时，红黑树的优点才能体现出来。至于为什么是8，是通过数据分析统计出来的一个结果，链表长度到达8的概率很低，综合链表和红黑树性能情况，就设置为了8。
- 链表转化为红黑树，除了要满足长度大于8之外，数组还要长度大于64。
怎么解决哈希冲突
- 拉链法：将相同的hash值对象放在Node中，然后挂在数组后面。
- hash函数：key的hash值经过两次扰动，key的hashCode值与key的hashCode值的右移16位进行异或，然后对数组的长度取余，降低冲突，使数据分布平均
- 红黑树：提高搜索速度。
1.2.2 HashSet
实现原理
- HashSet的实现原理：
- 是基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。
- 当我们试图把某个类的对象当成 HashMap的 key，或试图将这个类的对象放入 HashSet 中保存时，重写该类的equals(Object obj)方法和 hashCode() 方法很重要，而且这两个方法的返回值必须保持一致：当该类的两个的 hashCode() 返回值相同时，它们通过 equals() 方法比较也应该返回 true。通常来说，所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。
- HashSet的其他操作都是基于HashMap的。
- 但是HashSet所实现的接口是Set接口，是在Collection接口下的。
1.2.3 HashSet和HashMap的区别
| HashSet | HashMap |
|---|
| 实现了Set接口 | 实现了Map接口 |
| 仅存储对象 | 以键值对的形式存储 |
| 使用add方法添加元素 | 使用put方法添加对象 |
| 使用对象整体来计算Hash值 | 使用键对象来计算hash值 |
| 相较于Map查询慢 | 使用唯一键值来查询，速度快 |
1.2.4 ConcurrentHashMap
底层原理
- 在1.7的环境之下
- JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即 ConcurrentHashMap 把哈希桶数组切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。
- 如下图所示，首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。
- 在1.8的环境下
- 在数据结构上， JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的Node数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用CAS + synchronized实现更加细粒度的锁。
- 将锁的级别控制在了更细粒度的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点（红黑树的根节点），就不会影响其他的哈希桶数组元素的读写，大大提高了并发度。
1.3 ArrayList
- 继承了List接口。ArrayList的底层原理是使用一个数组来实现的。
- ArrayList类封装了一个动态的、允许再分配的Object[]数组，这个对象表明可以接收任何类型的数据，ArrayList对象使用initCapacity参数来设置该数组的长度，当向ArrayList集合中添加数据元素超过了该数组的长度时，它们的initCapacity会自动增加。自动增加的过程就是ArrayList扩容机制，底层实现是使用一个新的数组，将原数组的内容拷贝到新的数组中，并覆盖原有的数长度组的。扩容的长度是原来长度的1.5倍。是线程不安全的。
构造方法
- ArrayList的三个构造方法，使用三种方法都可以创建一个ArrayList集合，但是它们还是有一些区别：
ArrayList(int initialCapacity);
ArrayList();
ArrayList(Collection c);
- 使用第一个构造方法， 直接创建了指定大小的Object[]数组来创建集合;
- 使用第二个构造方法，创建的是一个空的数组，是将一个已经创建好的，使用static final 修饰的数组的引用赋值给了elementData ,此时的长度为零，当添加元素时， elementData = Arrays.copyOf(elementData, newCapacity);完成了elementData新的初始化工作，此时的长度才为10;
- 第三种构造方法是将集合转化为ArrayList,在底层实现中，先调用集合的toArray()方法，并赋值给elementData ， 然后进行类型的判断，是如果类型不是Object[]类型，那么将使用反射生成一个Object[]的数组，并重新赋值给elementData。
扩容机制
- 数组的特点是：一旦创建，容量无法改变。所以在往数组中添加指定元素之前，应该考虑数组容量空间是否已满，如果再进行数据的插入时，数组已满，则必须对其进行扩容操作。扩容操作的实质就是创建一个容量更大的新数组，再将旧数组的元素复制到新数组中去。
- ArrayList 内部数组扩容的过程:
- 首先，ArrayList扩容发生在add()方法调用的时候，它是调用ensureCapacityInternal()来扩容的，通过方法calculateCapacity(elementData, minCapacity)获取需要扩容的长度，ensureExplicitCapacity方法可以判断是否需要扩容，ArrayList扩容的关键方法grow(): 获取到ArrayList中elementData数组的内存空间长度 扩容至原来的1.5倍，调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间，从此方法中我们可以清晰的看出其实ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。
ArrayList和LinkedList的区别
- ArrayList和LinkedList都是线程不安全的。
- ArrayList底层使用数组，LinkedList底层使用双向链表
- ArrayLisr会存在一定的空间浪费，因为每次扩容都是之前的1.5倍；LinkedList中每个元素都需要存在前驱和后继的节点，因此空间需要更大。
- ArrayList是数组，因此适合多读少增删的场景；LinkedList是双向链表，适合多增删，少读写的场景。
ArrayList和Vector的区别
- 两者均实现了List接口，均使用数组实现功能
- Vector使用了Synchronized来实现线程同步，所以是线程安全的。
- ArrayList每次扩容为1.5倍，Vector是2倍