1. 总体结构

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。

• Map 接口和 Collection 接口是所有集合框架的父接口
• Collection 接口的子接口包括：Set 接口和 List 接口
• Map 接口实现：
  • HashMap：线程不安全，键值可为 null
  • LinkedHashMap：双向链表，元素默认按插入顺序排序
  • TreeMap：实现 SortedMap 接口，默认按键值升序排序，可指定排序的比较器
  • Hashtable：键值都不可为null，线程安全，Synchronized 关键字实现
  • ConcurrentHashMap：1.7 和 1.8 的实现不同
    • 1.7 Segment 数组 + HashEntry + Unsafe 实现
    • 1.8 移除 Segment，Synchronized + CAS + Node + Unsafe 实现，使锁粒度更小
  • Properties
• List接口实现：
  • ArrayList 初始容量10，扩容为原来的1.5倍。非线程安全，随机查询快
  • Vector 线程安全，使用了 sychronized
  • LinkedList 链表结构，新增和删除快
• Set接口实现：
  • HashSet 无序不重合集合
  • TreeSet 基于红黑树的可排序集合
  • LinkedHashSet 基于 hash 实现的有序集合

2. 设计模式

参考

2.1. 迭代器模式

Collection 继承了 Iterable 接口，其中的 iterator() 方法能够产生一个 Iterator 对象，通过这个对象就可以迭代遍历 Collection 中的元素。

从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String item : list) {
    System.out.println(item);
}

2.2. 适配器模式

java.util.Arrays#asList() 可以把数组类型转换为 List 类型。

@SafeVarargs
public static <T> List<T> asList(T... a)

应该注意的是 asList() 的参数为泛型的变长参数，不能使用基本类型数组作为参数，只能使用相应的包装类型数组。

Integer[] arr = {1, 2, 3};
List list = Arrays.asList(arr);

也可以使用以下方式调用 asList()：

List list = Arrays.asList(1, 2, 3);

3. 主要类具体分析

3.1. 基本类型不能做为 HashMap 的键值

• Java中是使用泛型来约束 HashMap 中的 key 和 value 的类型的，HashMap<K, V>
• 泛型在Java的规定中必须是对象 Object 类型的，基本数据类型不是 Object 类型，不能作为键值
• map.put(0, “test”)中编译器已将 key 值 0 进行了自动装箱，变为了 Integer 类型

3.2. ArrayList 和 Vector 的联系和区别

相同点：

• 底层都使用数组实现
• 功能相同，实现增删改查等操作的方法相似
• 长度可变的数组结构

不同点：

• Vector 是早期 JDK 版本提供，ArrayList 是新版本替代 Vector 的
• Vector 的方法都是同步的，线程安全；ArrayList 非线程安全，但性能比 Vector 好
• 默认初始化容量都是10，Vector 扩容默认会翻倍，可指定扩容的大小；ArrayList 只增加 50%

3.3. 4.HashMap详解

3.3.1. 内部数据结构

Jdk1.8之前，内部使用数组 + 链表，链表插入使用头插法，可能会有环的问题
Jdk1.8，内部使用数组 + 链表红黑树，链表插入使用尾插法

3.3.2. 插入原理

1.先判断数组是否为空，为空初始化；

2.不为空，计算 key 的 hash 值，通过 (n-1) & hash 计算应当存放在数组中下标 index；

3.查看 table[index] 是否存在数据，没有数据就构造一个 Node 节点放在 table[index] 中；

4.存在数据，说明 hash 冲突，判断 key 是否相等。相等的话用新的 value 替换原数据；

5.key 不相等判断当前节点类型是不是树型节点，如果是树节点，创造节点插入红黑树中（判断是树型节点表示当前已是红黑树了）；

6.节点如果不是树型节点，创建普通 Node 加入链表中；判断链表长度是否大于8并且数组长度大于64，条件成立的话链表转为红黑树；

7.插入完成之后判断当前节点是否大于阈值，如果大于就开始扩容为原数组的二倍

3.3.3. HashMap初始容量

new HashMap() 默认大小是16，负载因子是0.75，如果传入初始值 n，初始化大小为大于n的数字，满足2的整数次方。比如传的是10，小大为16.

3.3.4. HashMap的hash函数如何设计

hash 函数先是拿到 key 的 hashcode，是一个32位 int 值，然后让 hashcode 的高16位和低16位进行异或操作

//1.8版本，比1.7觉得扰动做一次就够了
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//确定数组 table 下标
/*tab[i = (n - 1) & hash]
其中 (n - 1) & hash 的 n 是 tab 长度，此操作相当于 hash % (n-1) 取余数，位运算计算比取余数快
*/

//1.7版本，做了四次移位和四次异或
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

3.3.5. 为什么这样做异或操作

1.尽可能降低 hash 碰撞，越分散越好；

2.算法尽可能高效，高频操作，采用位运算。

3.3.6. 为什么采用 hashcode 的高16位和低16位异或能降低 hash 碰撞？hash 函数能不能直接用 key 的 hashcode？

int 范围 -2^32 ~ 2^32-1，区间太大，接近40亿长度数组内存放不下。HashMap 的初始长度为16，将高半区和低半区做异或，混合哈希码的高位和低位，加大随机性，混合后低位掺杂了高位的部分特征，高位信息也被变相保留下来。

3.3.7. JDK1.8 版本除了 hash 函数做优化，还有其他哪些优化

1.数组+链表改成了数组+链表或红黑树，时间复杂度由链表 O(n) 降低为红黑树 O(logn)

2.链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为新节点的后继节点，1.8遍历链表，将元素放置到链表的最后

3.扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小

4.在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容

3.3.8. JDK1.8 版本做的优化的原因

1.防止发生 hash 冲突时，链表长度过长，将时间复杂度由链表O(n)降低为红黑树O(logn)

2.头插法扩容时，会使链表发生反转，多线程环境下会产生环

3.扩容的时候为什么1.8 不用重新hash就可以直接定位原节点在新数据的位置呢？
这是由于扩容是扩大为原数组大小的2倍，用于计算数组位置的掩码仅仅只是高位多了一个1
扩容前长度为16，用于计算(n-1) & hash 的二进制n-1为0000 1111，扩容为32后的二进制就高位多了1，为0001 1111
如果第四位高位为0，重新 hash 数值不变，第四位为1，重新hash数值比原来大16（旧数组的容量）

3.3.9. HashMap是线程安全的吗？

不是，在多线程环境下，1.7 会产生死循环（环形链）、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题

3.3.10. 解决HashMap是线程不安全问题

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。

HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个数组，粒度比较大，Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；ConcurrentHashMap 使用分段锁，降低了锁粒度，让并发度大大提高。

3.3.11. ConcurrentHashMap 的分段锁的实现原理

ConcurrentHashMap 成员变量使用 volatile 修饰，免除了指令重排序，同时保证内存可见性，另外使用 CAS 操作和 synchronized 结合实现赋值操作，多线程操作只会锁住当前操作索引的节点。

3.3.12. 链表转红黑树是链表长度达到阈值，这个阈值是多少？

阈值是8，红黑树转链表阈值为6。经过概率计算，在 hash 函数设计合理的情况下，发生 hash 碰撞8次的几率为百万分之6。至于为什么转回来是6，因为如果 hash 碰撞次数在8附近徘徊，会一直发生链表和红黑树的互相转化，为了预防这种情况的发生。