1.

概述
1.1 接口继承关系
1. 除了以 Map 结尾的类之外， 其他类都实现了 Collection 接口。

2. 以 Map 结尾的类都实现了 Map 接口

1.2 集合的特点

1.3 List
List 是有序的 Collection。Java List 一共三个实现类： 分别是 ArrayList、Vector 和 LinkedList
1.3.1 ArrayList（数组）

1. 数组实现的

2. 允许快速访问，但元素之间不能有间隔

3. 插入或删除需要复制/移动整个数组，代价高

4. 适合随机查找和遍历，不适合插入和删除

1.3.2 Vector(数组实现，线程同步)

1. 数组实现

2. 线程同步，线程安全

3. 因为只有一个线程可写，导致性能比ArrayList差

1.3.3 LinkList(链表实现)

1. 链表实现

2. 适合动态插入删除

3. 随机访问和遍历慢

4. 适合操作头尾元素，当队列，堆来用

1.4 Set
值不能重复，对象相等性通过hashCode 值判断（根据内存地址计算）

如果想要让两个不同的对象视为相等的，就必须覆盖 Object 的 hashCode 方法和 equals 方 法。

1.4.1 HashSet(Hash 表)

1. 元素的哈希值是通过元素的 hashcode 方法来获取的

2. HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较 equals 方法 如果 equls 结果

为 true ，HashSet 就视为同一个元素。如果 equals 为 false 就不是 同一个元素。

3. 哈希值相 同的元素放在一个哈希桶中，HashSet 通过 hashCode 值来确定元素在内存中的位置。

一个 hashCode 位置上可以存放多个元 素。

左边hashCode 不同， 右边HashCode同，equals不同

1.4.2 TreeSet（底层使用红黑树）

1. ，每增加一个对象都会重新排序

2. 自定义的类必须实现 Comparable 接口，并且覆写相应的 compareTo()函数，才能正常用

3. OverWrite compare()函数时，要返回相应的值才能使 TreeSet 按照一定的规则来排序

4. 比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整 数、零或
正整数。

1.4.3 LinkHashSet（HashSet+LinkedHashMap）

1. 于 LinkedHashSet 而言，它继承与 HashSet、又基于 LinkedHashMap 来实现的。

2. t 底层使用 LinkedHashMap 来保存所有元素

3. ，在相关操 作上与父类 HashSet 的操作相同，直接调用父类 HashSet 的方法即可

1.5 Map
1.5.1 HashMap(数组+链表+红黑树)

1. HashMap 根据键的 hashCode 值存储数据，访问速度快，但遍历顺序却是不确定的。

2. HashMap 最多只允许一条记录的key为 null，允许多条value的值为 null

3. 线程不安全，想安全用ConcurrentHashMap或者 synchronizedMap方法

实现：

[Link] Java 7 实现

HashMap 里面是一个数组，然后数组中每个元素是一个单向链表.

每个绿色 的实体是嵌套类 Entry 的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表的

next。

注意：

1. capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。
2. loadFactor：负载因子，默认为 0.75。
3. . threshold：扩容的阈值，等于 capacity * loadFactor

缺陷：

查找的时候，根据 hash 值我们能够快速定位到数组的 具体下标，但是之后的话，需要顺着链表一个个

比较下去才能找到我们需要的，时间复杂度取决 于链表的长度，为 O(n)。
[Link] Java 8实现 (由 数组+链表+红黑 树)

当链表中的元素超过了 8 个以后， 会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复

杂度为 O(logN)。

1.5.2 ConcurrentHashMap

1. Segment 段

整个 ConcurrentHashMap 由一个个 Segment 组成

Segment 代表”部分“或”一段“的 意思

所以很多地方都会将其描述为分段锁。

2. 线程安全（Segment 继承 ReentrantLock 加锁）

ConcurrentHashMap 是一个 Segment 数组

Segment 通过继承 ReentrantLock 来进行加锁

所以每次需要加锁的操作锁住的是一个 segment

这样只要保证每 个 Segment 是线程安全的，也就实现了全局的线程安全。

3. 并行度concurrencyLevel 默认为16

说 ConcurrentHashMap 有 16 个 Segments

理论上，最多可以同时支 持 16 个线程并发写

但是一旦初始化以后，它是不可以扩容的
1.5.3 HashTable（线程安全）

1. Hashtable 是遗留类，的常用功能与 HashMap 类似，但承自 Dictionary 类

2. 线程安全

3. 任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap

4. Hashtable 不建议在新代码中使用，不需要线程安全 的场合可以用 HashMap 替换，需要线程安全

的场合可以用 ConcurrentHashMap 替换。
1.5.4 TreeMap

1. 实现 SortedMap 接口，能够把它保存的记录根据键排序

2. 默认是按键值的升序排序， 也可以指定排序的比较器

3. Iterator 遍历 TreeMap 时，得到的记录是排过序的。

4. 用排序的映射，建议使用 TreeMap

5. key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator，否则会在运行

时抛出 [Link] 类型的异常。

1.5.5 LinkHashMap （记录插入顺序）

1. 是 HashMap 的一个子类

2. 保存记录的插入顺序

3. Iterator遍历时。得到的记录是先插入的

2. 集合的对比
2.1 List Set Map的区别
1. List (对付顺序的好帮手)： 存储的元素是有序的、可重复的。

2. Set (注重独一无二的性质): 存储的元素是无序的、不可重复的。

3. Map (用 Key 来搜索的专家): 使用键值对（kye-value）存储，每个键最多映射到一个值。Key 是无

序的、不可重复的，value 是无序的、可重复的

2.2 Arraylist 与 LinkedList 区别

1. 是否保证线程安全

都不保证

2. 底层数据结构

Arraylist 底层使⽤的是 Object 数组； LinkedList 底层使⽤的是 双向链表 数据结构

3. . 插⼊和删除是否受元素位置的影响

ArrayList 采⽤数组存储，所以插⼊和删除元素 的时间复杂度受元素位置的影响。

LinkedList 采⽤链表存储，插⼊，删除元素时间复杂 度不受元素位置的影响，近似 O（1）

但是，如果是要在指定位置 i 插⼊和删除元素的话 （ (add(int index, E element) ） 时间复杂度近

似为 o(n)) 因为需要先移动到指定位置 再插⼊。

4. 是否支持快速随机访问 get(int index)

LinkedList 不⽀持⾼效的随机元素访问，⽽ ArrayList ⽀持

5. 内存占用

ArrayList 浪费的空间主要是list链表结尾会浪费一些空间

LinkedList 的浪费主要是每个元素都会需要比ArrayList更多一些的空间

ArrayList 实现了 RandomAccess 接⼝。不是实现RandomAccess 就可以随机访问，而是数组天然⽀持

随机访问。
2.3 ArrayList 和 Vector区别，为什么Vector被ArrayList取代
1. Vector所有方法线程安全

2. Vector单线程访问比较耗时，因为有锁

3. ArrayList线程不安全

2.4 ArrayList扩容的核心方法 grow()

/**
* 要分配的最大数组大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
* ArrayList扩容的核心方法。
*/
private void grow(int minCapacity) {
// oldCapacity为旧容量，newCapacity为新容量
int oldCapacity = [Link];
//将oldCapacity 右移一位，其效果相当于oldCapacity /2，
//我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5
倍，
int newCapacity = oldCapacity + (oldCapacity >> 1);
//然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数
组的新容量，
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较
minCapacity 和 MAX_ARRAY_SIZE，
//如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则
为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = [Link](elementData, newCapacity);
}

int newCapacity = oldCapacity + (oldCapacity >> 1)

所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右

（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！

奇偶不同，比如 ：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

">>"（移位运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity

明显右移了 1 位所以相当于 oldCapacity /2。

2.5 HashMap 和 Hashtable 的区别

1. 线程安全：

HashMap 是⾮线程安全的

HashTable 是线程安全的
 HashTable 里的方法都synchronized 过了
2. 效率

HashMap 效率更高

但是不要用HashTable

3. Null key和 Null Value的支持

HashMap可以有一个null key, 多个null value

HashTable 有一个null key就报错

4. 初始容量

HashMap 默认的初始化⼤⼩为16。之后每次扩充，容量变为原来的2倍。

Hashtable 默认 的初始⼤⼩为11，之后每次扩充，容量变为原来的2n+1

给定了容量初始值：

HashMap 会扩充为2的幂次⽅⼤⼩

Hashtable 会直接使⽤ 你给定的⼤⼩

5. 底层数据结构

HashMap 在链表长度大于 8 时 将链表转为红黑树

HashTable 无此机制

下⾯这个⽅法保证了 HashMap 总是使⽤2的幂作为哈希表的⼤⼩

/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n åã MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY
: n + 1;
}

2.6 HashMap 和 HashSet区别

1. HashSet 底层就是基于 HashMap 实现

2. （HashSet 的 源码⾮常⾮常少，因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet ⾃

⼰不得不 实现之外，其他⽅法都是直接调⽤ HashMap 中的⽅法。
2.7 HashSet 如何查重
1. HashSet会先计算对象的 hashcode 值来判断对象加⼊的位置

2. 与其他加⼊的对象的hashcode值作比较

3. 如果没有相符的hashcode，HashSet会假设对象没有重复出现

4. 如果发现有相同hashcode值的对象，这时会调⽤ equals（）方法

5. 如果两者相同，HashSet就不会让加⼊操作成功

2.8 HashMap的底层实现
1. Java 7

1. 数组和链表

2. HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值

3. 然后通过 (n - 1) & hash 判断当前元素存放的位置

4. 如果当前位置存在元素的话，就判断该元素与要存⼊的元素的 hash 值以及 key 是否相同

5. 如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

扰动函数：

指的就是 HashMap 的 hash ⽅法，使⽤ hash ⽅法也就是扰动函数是为了防⽌⼀些实现 ⽐较差的

hashCode() ⽅法

减少碰撞
拉链法：

将链表和数组相结合。

也就是说创建⼀个链表数组，数组中每⼀格就是⼀个链表。

若遇到哈希冲突，则将冲突的值加到链表中即可。

2. Java 8

当链表⻓度⼤于阈值（默认为8） 时，将链表转化为红⿊树，以减少搜索时间。

TreeMap、TreeSet以及Java 8之后的HashMap底层都⽤到了红⿊树

红黑树解决了二叉查找树在某些情况下退化为线性结构的缺陷

2.9 HashMap 的⻓度为什么是2的幂次⽅

生成的Hash用数组放不下，需要取余

1. 这个数组下标的计算⽅法是“ (n - 1) & hash ”。（n代表数组⻓ 度）。

2. 这也就解释了 HashMap 的⻓度为什么是2的幂次⽅。

详细解释：

为了能让 HashMap 存取⾼效，尽量减少碰撞，也就是要尽量把数据分配均匀。

Hash 值的范围值-2147483648到2147483647，前后加起来⼤概40亿的映射空间，只要哈希函数映射 得
比较均匀松散，⼀般应⽤是很难出现碰撞的。但问题是⼀个40亿⻓度的数组，内存是放不下的。

⼆进制位操作 &，相对于%能够提⾼运算效率，这就解释了 HashMap 的⻓度 为什么是2的幂次⽅。

2.10 HashMap 多线程死循环的问题原因

1. 并发下的Rehash 会造成元素之间会形成⼀个循环链表，Java 8解决

2. 并发环境下推荐使⽤ ConcurrentHashMap
2.11 ConcurrentHashMap 和 Hashtable 的差别
1. 底层数据结构

ConcurrentHashMap 在 Java8之前 底层是分段数组+链表。 Java 8 之后是数组+链表/红黑树

Hashtable 一直都是数组+链表 链表为解决哈希冲突而生

2. 线程安全的实现：

ConcurrentHashMap 在 Java 8之前使用分段锁

对整个桶数组进⾏了分割分段(Segment)，每⼀把锁只锁容器其中⼀部分数据，多线程访问容
器⾥不同数 据段的数据，就不会存在锁竞争，提⾼并发访问率。

ConcurrentHashMap 在 Java 8之后使用Node 数组+链表+红⿊树的数据结构来实现

并发控制使⽤ synchronized 和 CAS 来操作

Hashtable(同⼀把锁)

使⽤ synchronized 来保证线程安全，效率⾮常低下。

当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进⼊阻塞或轮询状态

3. 数据结构示意图

ConcurrentHashMap Java 8之前

ConcurrentHashMap 在 Java 8之后

JDK1.8的ConcurrentHashMap（TreeBin: 红⿊⼆叉树节点 Node: 链表节点）：

 HashTable:

全表锁非常垃圾，效率低下

2.12 ConcurrentHashMap线程安全的具体实现⽅式/底层具体实现
Java 8 之前

1. 先将数据分为⼀段⼀段的存储，然后给每⼀段数据配⼀把锁

2. 当⼀个线程占⽤锁访问其中⼀个段数据 时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是⼀种可重⼊锁，扮演锁的⻆⾊。

HashEntry ⽤于存储 键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable

{
}

Java 8之后

1. 取消了Segment分段锁

2. 采⽤CAS和synchronized来保证并发安全

3. Java 8在链表⻓度超过⼀定阈值（8）时将链表（寻 址时间复杂度为O(N)）转换为红⿊树

（寻址时间复杂度为O(log(N))）
2.13 Comparable 接口和 Comparator接口的区别
1. comparable 接口 来自[Link] 包，有compareTo(Object obj) 方法用于排序

2. comparator接口出自[Link]包，有compare(Object obj1, Object obj2) ⽅法⽤来排序

自定义排序都要重写这两个Overwirte

2.13.1 重写Comparable 接口的 compareTo 例子

// person对象没有实现Comparable接口，所以必须实现，这样才不会出错，才可以使treemap中的数据按
顺序排列
// 前面一个例子的String类已经默认实现了Comparable接口，详细可以查看String类的API文档，另外其
他
// 像Integer类等都已经实现了Comparable接口，所以不需要另外实现了
public class Person implements Comparable<Person> {
private String name;
private int age;

public Person(String name, int age) {

super();
[Link] = name;
[Link] = age;
}

public String getName() {

return name;
}

public void setName(String name) {

[Link] = name;
}

public int getAge() {

return age;
}

public void setAge(int age) {

[Link] = age;
}

/**
* T重写compareTo方法实现按年龄来排序
*/
@Override
public int compareTo(Person o) {
if ([Link] > [Link]()) {
return 1;
}
if ([Link] < [Link]()) {
return -1;
}
return 0;
}
}
 public static void main(String[] args) {
TreeMap<Person, String> pdata = new TreeMap<Person, String>();
[Link](new Person("张三", 30), "zhangsan");
[Link](new Person("李四", 20), "lisi");
[Link](new Person("王五", 10), "wangwu");
[Link](new Person("小红", 5), "xiaohong");
// 得到key的值的同时得到key所对应的值
Set<Person> keys = [Link]();
for (Person key : keys) {
[Link]([Link]() + "-" + [Link]());

}
}

Output：

5-小红
10-王五
20-李四
30-张三

2.13.2 Comparator 定制排序

ArrayList<Integer> arrayList = new ArrayList<Integer>();

[Link](-1);
[Link](3);
[Link](3);
[Link](-5);
[Link](7);
[Link](4);
[Link](-9);
[Link](-7);
[Link]("原始数组:");
[Link](arrayList);
// void reverse(List list)：反转
[Link](arrayList);
[Link]("[Link](arrayList):");
[Link](arrayList);

// void sort(List list),按自然排序的升序排序

[Link](arrayList);
[Link]("[Link](arrayList):");
[Link](arrayList);
// 定制排序的用法
[Link](arrayList, new Comparator<Integer>() {

@Override
public int compare(Integer o1, Integer o2) {
return [Link](o1);
}
});
[Link]("定制排序后：");
[Link](arrayList);
Output:

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
[Link](arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
[Link](arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后：
[7, 4, 3, 3, -1, -5, -7, -9]

2.14 什么是无序性 什么是不可重复性

1. 无序性：不是随机性，是指数据在底层数组中不是按照数组索引顺序添加，而是由哈希值决定的

2. 不可重复性：指添加元素按照equals()判断时，返回false，需要重写equals()和hashCode()方法

3. 总结
3.1 Collection
3.1.1 List

ArrayList:Object数组

Vector: Object数组

LinkedList: 双向链表

3.1.2 Set

HashSet(无序，唯一)：由HashMap实现，底层使用HashMap保存元素

LinkedHashSet: 继承HashSet,内部通过LinkedHashMap实现

TreeSet(有序，唯一)：红黑树(自平衡的排序二叉树)

3.2 Map
3.2.1 HashMap

Java 8之前

1. 由数组+链表实现

2. 数组是HashMap的主体，链表则是主要为了 解决哈希冲突⽽存在的

3. “拉链法”解决冲突

Java 8 之后

1. 链表⻓度⼤于阈值（默认为8）时，将链表转化为红⿊树

3.2.2 LinkedHashMap

1. 继承HashMap

2. 底层是拉链式散列结构（数组+链表/红黑树）

3. 增加双向链表，保持键值对的插入顺序

4. 可以通过链表实现顺序访问
3.2.3 HashTable

1. 数组+链表实现
2. 数组是HashMap主体，链表为解决哈希冲突存在

3.2.4 TreeMap

红黑树，自平衡的排序二叉树实现

3.3 选用集合的技巧
要用key-value对

1. 需要键值对获取元素用Map

2. 需要排序用TreeMap,不需要用HashMap

3. 需要线程安全用ConcurrenHashMap

只存value

1. 只存value用Collection集合

2. 保证元素唯一用Set，TreeSet或者HashSet

3. 不用唯一用List，如ArrayList或者LinkedList