Collection

单列集合

List

有序可重复

Vector

数组结构，线程安全

ArrayList

数据结构，非线程安全

ArrayList底层的实现原理是什么?

底层是用动态数组实现的。
初始容量为0，当第一次添加数据的时候才会初始化容量为10。
进行扩容的时候是原来的1.5倍，每次扩容都需要拷贝数组。
添加数据时候：
- 确保size + 1后能存储下下一个数据。
- 计算数组容量，如果size + 1大于当前的数组容量，调用grow方法扩容。
- 确保新增的数据有地方存放后，则将新元素加到对应的位置上。
- 放回true。

ArrayList list = new ArrayList(10)中的list扩容了几次？

答：没有扩容，只是指定了一个容量为10的Object数组。

如何实现数组与List之间的转换

List转数组

使用List.toArray(T[] a): T[]。

数组转List

Arrays.asList(T ... a): List<T>。

使用Arrays.asList转List后，修改数组内容，List受影响吗？

受影响。他使用的Arrays类中的ArrayList内部类来构造的集合，在这个集合的构造器中，只是将传入的集合保证了而已，最终指向的内存地址是同一个。

List用toArray转数组后，如果修改了List内容，数组受影响吗？

不受影响。内部使用System.arraycopy方法进行了数组复制。

LinkedList

链表结构。非线程安全

ArrayList和LinkedList的区别是什么？

底层数据结构

ArrayList底层使用动态数组实现的，而LinkedList底层是用双向链表实现的。
操作数据效率

在随机访问方面，ArrayList优于LinkedList。

在查找方面，两者时间复杂度一致。

在插入删除操作方面，都需要先找到插入或删除的位置，故而时间复杂度一致。假设已经知道了插入或删除的位置，位置若在ArrayList尾部，则ArrayList时间复杂度为 $O(1)$ ，若在中间，平均时间复杂度为 $O(n)$ 。对于LinkedList来说，无论在何处，时间复杂度都是 $O(1)$ 。
空间方面

ArrayList优于LinkedList。由于ArrayList底层使用的是数组，内存是连续的，故而可以直接找到前驱和后继，而LinkedList使用的双向链表，需要额外存储前驱和后继的引用。
线程安全

都不是线程安全的。

如何保证线程安全呢？
- 在方法中时间，局部变量不存在线程安全问题。
- 使用Collections.synchronizedList(List<T> list)让其变成线程安全的。

Set

无须，唯一

HashSet

哈希表结构

LinkedHashSet

哈希表和链表结构

TreeSet

红黑树结构

Map

双列集合

HashTable

哈希表结构，线程安全

Properties

HashMap

哈希表结构，非线程安全。

HashMap是懒惰加载的，再创建对象时并没有初始化数组。

在无参的构造函数中，设置了默认的加载因子是0.75。

实现原理

使用的Hash表数据结构，使用链表或红黑树解决hash冲突。

调用put方法的时候，利用key的hashCode重新计算出当前元素在数组中的下标。
存储时，如果出现hash冲突，此时有两种情况
- key相同，则覆盖。
- key不同，将当前key-value存入链表或红黑树中。
获取时，直接找到hash值对应的下标，再进一步判断key是否相同，从而找到对应的值。

1.8之前和1.8及之后有什么区别？

1.8之前处理hash冲突仅使用了链表。

1.8及之后处理hash冲突使用的链表或红黑树。当链表长度大于8且数组长度大于64时，链表会转换成红黑树。当链表长度小于等于6时，红黑树会转换成链表。

put流程

判断数组是否为空，若为空则执行resize()进行扩容（初始化）。
判断key计算hash值得到数组下标i。
若table[i] == null，直接新建节点添加。
若table[i] != null
1. table[i].Key == Key，覆盖并跳过下面的步骤。
2. 判断table[i]是为红黑树节点，是则直接走红黑树添加流程。
3. 遍历table[i]，使用尾插法。然后判断是否可以链表转红黑树。
插入成功后判断是否需要扩容。