常见的集合有哪些？
Java 集合类主要由两个接口 Collection 和 Map 派生出来的，Collection 有三个子接口：List、
Set、Queue。
Java 集合框架图如下：
List 代表了有序可重复集合，可直接根据元素的索引来访问；Set 代表无序不可重复集合，只能
根据元素本身来访问；Queue 是队列集合。Map 代表的是存储 key-value 对的集合，可根据元
素的 key 来访问 value。
集合体系中常用的实现类有 ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap 等实
现类。
#List 、Set 和 Map 的区别
� List 以索引来存取元素，有序的，元素是允许重复的，可以插入多个 null；
� Set 不能存放重复元素，无序的，只允许一个 null；
� Map 保存键值对映射；
� List 底层实现有数组、链表两种方式；Set、Map 容器有基于哈希存储和红黑树两种方
式实现；
� Set 基于 Map 实现，Set 里的元素值就是 Map 的键值。
#ArrayList 了解吗？
ArrayList 的底层是动态数组，它的容量能动态增长。在添加大量元素前，应用可以使用
ensureCapacity 操作增加 ArrayList 实例的容量。ArrayList 继承了 AbstractList ，并实现了 List
接口。
#ArrayList 的扩容机制？
ArrayList 扩容的本质就是计算出新的扩容数组的 size 后实例化，并将原有数组内容复制到新数
组中去。默认情况下，新的容量会是原容量的 1.5 倍。以 JDK1.8 为例说明:
public boolean add(E e) {
//
判断是否可以容纳
e
，若能，则直接添加在末尾；若不能，则进行扩容，然后再把
e
添加在末尾
ensureCapacityInternal(size + 1);
// Increments modCount!!
//
将
e
添加到数组末尾
elementData[size++] = e;
return true;
}
//
每次在
add()
一个元素时，
arraylist
都需要对这个
list
的容量进行一个判断。通过
ensureCapacityInternal()
方法确保当前
ArrayList
维护的数组具有存储新元素的能力，经过处理之后将元素
存储在数组
elementData
的尾部
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//
如果传入的是个空数组则最小容量取默认容量与
minCapacity
之间的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//
若
ArrayList
已有的存储能力满足最低存储要求，则返回
add
直接添加元素；如果最低要求的存储
能力
>ArrayList
已有的存储能力，这就表示
ArrayList
的存储能力不足，因此需要调用
grow();
方法进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
//
获取
elementData
数组的内存空间长度
int oldCapacity = elementData.length;
//
扩容至原来的
1.5
倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//
校验容量是否够
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//
若预设值大于默认的最大值，检查是否溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//
调用
Arrays.copyOf
方法将
elementData
数组指向新的内存空间
//
并将
elementData
的数据复制到新的内存空间
elementData = Arrays.copyOf(elementData, newCapacity);
}
#怎么在遍历 ArrayList 时移除一个元素？
foreach 删除会导致快速失败问题，可以使用迭代器的 remove() 方法。
Iterator itr = list.iterator();
while(itr.hasNext()) {
if(itr.next().equals("jay") {
itr.remove();
}
}
#Arraylist 和 Vector 的区别
1. ArrayList 在内存不够时扩容为原来的 1.5 倍，Vector 是扩容为原来的 2 倍。
2. Vector 属于线程安全级别的，但是大多数情况下不使用 Vector，因为操作 Vector 效率
比较低。
#Arraylist 与 LinkedList 的区别
1. ArrayList 基于动态数组实现；LinkedList 基于链表实现。
2. 对于随 机 index 访问的 get 和 set 方法，ArrayList 的速度要优 于 LinkedList。因 为
ArrayList 直接通过数组下标直接找到元素；LinkedList 要移动指针遍历每个元素直到找
到为止。
3. 新增和删除元素，LinkedList 的速度要优于 ArrayList。因为 ArrayList 在新增和删除元素
时，可能扩容和复制数组；LinkedList 实例化对象需要时间外，只需要修改指针即可。
#HashMap
HashMap 使用数组+链表+红黑树（JDK1.8 增加了红黑树部分）实现的， 链表长度大于 8
（ TREEIFY_THRESHOLD ） 时 ， 会 把 链 表 转 换 为 红 黑 树 ， 红 黑 树 节 点 个 数 小 于 6
（UNTREEIFY_THRESHOLD）时才转化为链表，防止频繁的转化。
#解决 hash 冲突的办法有哪些？HashMap 用的哪种？
解决 Hash 冲突方法有：开放定址法、再哈希法、链地址法。HashMap 中采用的是 链地址法 。
� 开放定址法基本思想就是，如果 p=H(key)出现冲突时，则以 p 为基础，再次 hash，p1=H(p),
如果 p1 再次出现冲突，则以 p1 为基础，以此类推，直到找到一个不冲突的哈希地址
pi。 因此开放定址法所需要的 hash 表的长度要大于等于所需要存放的元素，而且因为
存在再次 hash，所以只能在删除的节点上做标记，而不能真正删除节点。
� 再哈希法提供多个不同的 hash 函数，当 R1=H1(key1)发生冲突时，再计算 R2=H2(key1)，
直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。
� 链地址法将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈
希表的第 i 个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常
进行插入和删除的情况。
#使用的 hash 算法？
Hash 算法：取 key 的 hashCode 值、高位运算、取模运算。
h=key.hashCode() //
第一步
取
hashCode
值
h^(h>>>16) //
第二步
高位参与运算，减少冲突
return h&(length-1); //
第三步
取模运算
在 JDK1.8 的实现中，优化了高位运算的算法，通过 hashCode()的高 16 位异或低 16 位实现的：
这么做可以在数组比较小的时候，也能保证考虑到高低位都参与到 Hash 的计算中，可以减少冲
突，同时不会有太大的开销。
#为什么建议设置 HashMap 的容量？
HashMap 有扩容机制，就是当达到扩容条件时会进行扩容。扩容条件就是当 HashMap 中的元
素个数超过临界值时就会自动扩容（threshold = loadFactor * capacity）。
如果我们没有设置初始容量大小，随着元素的不断增加，HashMap 会发生多次扩容。而 HashMap
每次扩容都需要重建 hash 表，非常影响性能。所以建议开发者在创建 HashMap 的时候指定初
始化容量。
#扩容过程？
1.8 扩容机制：当元素个数大于 threshold 时，会进行扩容，使用 2 倍容量的数组代替原有数组。
采用尾插入的方式将原数组元素拷贝到新数组。1.8 扩容之后链表元素相对位置没有变化，而
1.7 扩容之后链表元素会倒置。
1.7 链表新节点采用的是头插法，这样在线程一扩容迁移元素时，会将元素顺序改变，导致两个
线程中出现元素的相互指向而形成循环链表，1.8 采用了尾插法，避免了这种情况的发生。
原数组的元素在重新计算 hash 之后，因为数组容量 n 变为 2 倍，那么 n-1 的 mask 范围在高位
多 1bit。在元素拷贝过程不需要重新计算元素在数组中的位置，只需要看看原来的 hash 值新增
的那个 bit 是 1 还是 0，是 0 的话索引没变，是 1 的话索引变成“原索引+oldCap”（根据 e.hash &
oldCap == 0 判断） 。这样可以省去重新计算 hash 值的时间，而且由于新增的 1bit 是 0 还是 1
可以认为是随机的，因此 resize 的过程会均匀的把之前的冲突的节点分散到新的 bucket。
#put 方法流程？
1. 如果 table 没有初始化就先进行初始化过程
2. 使用 hash 算法计算 key 的索引
3. 判断索引处有没有存在元素，没有就直接插入
4. 如果索引处存在元素，则遍历插入，有两种情况，一种是链表形式就直接遍历到尾端插
入，一种是红黑树就按照红黑树结构插入
5. 链表的数量大于阈值 8，就要转换成红黑树的结构
6. 添加成功后会检查是否需要扩容
