集合框架
单列集合：
双列集合：
集合和数组的区别
长度：数组固定长度
内容：集合只能是引用类型
元素：数组只能存储同一类型
Collection接口
实现类有些可以重复，有些有序，没有直接实现，而是子接口
//常用方法
list.add(true)//可以添加不同类型
.remove(true)//可以按索引也可以直接删除某个元素
.contains(obj)
.size()
.isEmpty()
.clear()
.addAll(list2)
.containsAll(list2)
.removeAll(list2);//删除多个元素
List接口
元素按索引有序，可以重复
//常用方法
List list = new ArrayList();
list.add(obj)
.add(index, obj)
.addAll(index, Collection eles)//索引位置插入集合
.get(index)
.indexOf(obj)//首次出现的位置
.lastIndexOf(obj)
.remove(index)
.set(index, obj)
.subList(fromIndex, toIndex);//获取下标[fromIndex, toIndex)的子集合
ArrayList
可以存null，底层是可变数组实现，基本等同于Vector，线程不安全，效率高，适合单线程。
底层机制：
transient Object[] elementData;//transient表示瞬间，该属性不会被序列化
扩容机制：
//构造器
new ArrayList();//无参，初始容量为0，空数组{}，第一次添加扩容为10，再次扩容则扩容为1.5倍
new ArrayList(size);//指定大小，初始容量为指定大小，后续扩容为1.5倍
Vector
线程同步，即线程安全，synchronized
LinkedList
底层维护了一个双向链表和双端队列，线程不安全。
添加和删除不是通过数组完成的，相对来说效率高。
集合选择
改查操作多，选择ArrayList（大部分情况选择ArrayList）
增删较多，选择LinkedList
多线程选择Vector
Set接口
无索引存放无序（但取出顺序固定），不可重复，所以最多一个null
遍历：
Set set = new HashSet();
set.add();
//遍历
//1、迭代器
while(set.iterator().hasNext()) {iterator.next()}
//2、增强for
for(Object obj : set) {}
//无get方法
HashSet
1、实现了Set接口，底层实际上是HashMap，源码
public HashSet() {
map = new HashMap<>();
}
2、可以存放一个null
3、不保证存放元素的顺序和取出顺序一致
4、元素不重复（不能加入相同元素）
执行add方法后会返回一个布尔值
经典面试题：
set.add(new String("123"));
set.add(new String("123"));//能重复加入吗?
//不能，因为add方法底层
底层原因：
HashMap底层是数组+链表（+红黑树）
结点存储数据和下一个结点的引用，结点数组称为表，结点形成链表，链表到达一定长度，则链表形成红黑树，提高存储效率。
所以要让两个属性值相同（或部分属性值相同）的对象只存入一个，则重写hashCode方法
@Override
public int hashCode() {
return Objects.hash(Object... values);//hash()源码涉及到“31*任意数是最少重复”
}
LinkedHashSet
继承HashSet
底层是一个LinkedHashMap，底层维护了一个数组+双向链表
因为使用双向链表维护了元素的次序，所以使元素看起来是以插入顺序保存的
效率不如HashSet，但是有序了
TreeSet
区分于HashSet的最大特点：可以排序
使用无参构造器创建TreeSet时，仍然是无序的。
构造器中传入一个比较器，可以指定排序规则，实现在添加元素时按排序规则进行添加。
TreeSet treeSet = new TreeSet(new Comparator() {
@0verride
public int compare(Object o1, Object o2) {
//下面调用String的compareTo方法进行字符串大小比较，实现从小到大排序
return ((String) o1).compareTo((String) o2);//大小相同时不会添加
//长度相同时不会添加
return ((String) o1).length() - ((String) o2).length();
}
});
Map接口
保存key-value键值对，单向一对一对应，key和value可以是任何引用类型。
key不允许重复，key可以为null，常用String类作为key，key是按照hash值来的，key相同时会采用替换策略。
HashSet底层也是键值对，但是值都为private static final Object PRESENT = new Object();
//常用方法
map.put()
.remove()
.get()
.size()
.isEmpty()
.clear()
.containsKey();
遍历：
//1、(最简单)取出所有key，通过key取出对应的value
Map map = new HashMap();
Set keySet = map.keySet();
for(Object key : keySet) {
key;
map.get(key);
}
//2、迭代器
Object key = map.keySet().iterator().next();
map.get(key);
//3、把所有的value取出，遍历values
Collection values = map.values();
for(){}
//4、通过EntrySet
Set entrySet = map.entrySet();
for(Object entry : entrySet) {
//将entry（类型为Node）向下转型转成Map.Entry
Map.Entry m = (Map.Entry) entry;
m.getKey();
m.getValue();
}
HashMap
线程不安全，无序（Hash表），底层是Node类型的数组table+链表（+红黑树），链表结点是HashMap.Node，Node实现了Map.Entry接口。链表长度>8，且table数组达到64，链表就会树化。
底层机制解读：
1、Map存放数据的一对key-value是放在一个HashMap的内部类Node中的。
2、为了方便遍历，还会创建HashMap.EntrySet集合，该集合存放的元素的类型为Map.Entry，而Entry这个数据类型包含key，value。
3、entrySet中的Entry实际上还是HashMap.Node，因为Node<K,V>实现了Entry<K,V>（多态）。即HashMap.Node对象转换成Map.Entry存放到entrySet（地址指向）中，而Map.Entry中提供了getKey()和getValue()方法，故方便程序员对其进行遍历。
扩容机制（和HashSet相同）：
1、创建对象时，将加载因子LoadFactor初始化为0.75。
2、添加key-value时，通过key的哈希值得到数组table的索引，然后判断索引处是否有元素。如果没有元素则直接添加，有元素则继续判断两元素的key是否相等。如果相等则直接替换value，不相等则需要判断是树结构还是链表结构，做出相应处理。如果链表添加时发现容量不够，则需要对table和链表同时进行扩容。
3、第一次添加，扩容table容量为16，临界值threshold为16*LoadFactor=12
4、以后再扩容，则需要扩容table容量为原来的2倍（32），临界值为原来的2倍（24），依此类推。
5、在Java8（JDK8）中，若一条链表的元素个数超过TREEIFY_THRESHOLD（默认为8），并且table的大小>=MIN_TREEIFY_CAPACITY（默认64），就会进行树化。
例：同一hash的key添加到第9个会发生第一次扩容，table容量扩容为32，添加到第10个会发生第二次扩容，table容量扩容为64，添加到第11个就会树化，HashMap$Node变成HashMap$TreeNode。不同Hash的key添加到12（16*LoadFactor）个，则table扩容到32；添加到24（32x0.75）个，则table扩容到64。
Hashtable
key和value都不能为null，否则会抛出空指针异常。线程安全synchronized，较于HashMap效率较低
扩容机制：
1、底层有Hashtable$Entry[]数组，初始大小为11。
2、数组大小超过临界值threshold = 8，则大小newCapacity扩容为(oldCapacity << 1) + 1。
TreeMap
TreeMap treeMap = new TreeMap(new Comparator() {
@0verride
public int compare(Object o1, Object o2) {
//下面调用String的compareTo方法进行字符串大小比较，实现从小到大排序
return ((String) o1).compareTo((String) o2);//大小相同时不会添加
//从短到长排序，长度相同时不会添加
return ((String) o1).length() - ((String) o2).length();
}
});
treeMap.put("", "");
集合的选择
一组对象【单列】：Collection接口
允许重复：List
增删多：LinkedList（双向链表）
改查多：ArrayList（可变数组）
不允许重复：Set
无序：HashSet（HashMap）
排序：TreeSet
插入和取出顺序一致：LinkedHashSet [LinkedHashMap[HashMap]]（数组+双向链表）
一组键值对【双列】：Map接口
键无序：HashMap（数组+链表+红黑树）
键排序：TreeMap
键插入和取出顺序一致：LinkedHashMap
Collections工具类
是一个操作Set、List和Map等集合的工具类。
提供了一系列静态的方法对集合元素进行排序、查询和修改的操作。
//常用静态方法
Collections.reverse(list)
.shuffle(list)//打乱顺序，随机排序
.sort(list)//自然排序（首字母最大）
.sort(list, new comparator() {//指定顺序排序
@0verride
public int compare(Object o1, Object o2) {
if(o1 instanceOf String) {
return ((String) o1).length() - ((String) o2).length();
}
}
})
.swap(list, index1, index2)//指定下标元素交换
.max(list)//自然顺序最大值
.max(list, comparator)
.min(list).min(list, comparator)
.frequency(list, object)//元素出现的频率
.copy(destList, srcList)//srcList中的内容复制到destList，注意要求集合大小相同
.replaceAll(list, oldValue, newValue);//新值替换旧值（所有符合的）