集合的特点：
- 存储的数据量可变
- 存储的数据类型可变（通过泛型可以添加不同类型的数据）
- 只能存储引用类型
上述三点都是对应于数组的特点。
集合的分类：
基本接口collection和map
collection实现了Iterable接口，包含list、set、queue
list：可以包含重复元素，取出和放入的顺序一致
set：不包含重复元素，最多包含一个null，取出和放入的顺序不一致
queue：
其中collection继承了Iterable接口，其iterator()方法返回一个迭代器，而该方法乃至迭代器的具体实现在collection的子类中。
迭代器是接口的原因，每种集合的数据结构不一样，其遍历的实现方式不一样，所以抽象为接口，真正的实现是以内部类方式实现。可参见ArrayList中的iterator()方法。这里作为java多态和继承的很好的体现实例
基本方法：
自行查询api，不过有以下注意的点
- addAll(Collection collection)， 实质是将地址值赋值给另一个列表。
- retainAll(Collection collection)，保留与给定集合中共有的元素，如果集合被改变，则返回true。
- toArray() 方法，返回一个包含该集合中所有元素的数组，是新建的数组，原有集合不会对该数组产生引用，所以对集合的操作不会影响该数组。这也是遍历集合的一种解决方案
关键接口：
-
Iterator
Iterator it = list.iterator();
遍历方法除了常见的while(it.hasNext())，还可以是for循环
for(Iterator it = list.iterator();it.hasNext();) {
Student s = (Student) it.next();
//Do something about s;
}
迭代器遍历集合时候，除非使用迭代器的remove方法，不能同时对集合进行增删操作，因为迭代器是基于iterator()方法被创建的，后续对集合的改变不能被同步上。即当多个线程，或多个任务对Collection进行操作时，若其中某一个任务通过Iterator遍历集合时，同时该集合的内容被其他迭代器或者集合自身的方法修改类，会抛出ConcurrentModificationException异常。
此外迭代器中next方法和remove方法是紧紧关联的，remove是删除上次调用next时返回的元素，所以调用remove前没有调用next是非法的。
为什么要使用迭代器？
不同集合的数据结构不一样，比如set，就不能使用for循环。使用迭代器作为接口，在不同集合中根据集合数据结构实现遍历的功能。此外，Iterator访问方式把对不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。再者，Iterator能够让访问者同时遍历并操作列表元素，如使用其remove方法，如果在fori循环中遍历并删除元素，会导致指针偏移。
-
List
有序的collection（存储和取出顺序一致），用户可以控制插入的位置，根据元素索引访问元素，允许重复的元素。
- ListIterator list特有的迭代器，继承了Iterator迭代器，特有逆向遍历功能和其他新特性，但是使用前必须先经过过正向遍历，所以实际用处不大。
- list集合特有用for(int i = 0;i < list.size(); x++)循环功能
根据之前叙说的迭代器遍历数组时修改数组异常——ConcurrentModificationException，一种思路，两种方案，思路就是将修改和遍历合并到一个线程，方案分别是仅仅用迭代器或者仅仅用集合，实践中推荐ListIterator，但修改位置受限（见api），而使用for循环遍历，会有隐藏的风险：
for(int i = 0;i<arrayList2.size(); i++) {
Student student = (Student)arrayList2.get(i);
System.out.println(student.getOfficialName());
System.out.println(arrayList2.size());
if(student.getOfficialName().equals("hugo")) {
arrayList2.remove(1);
}
}//此时原来数组中下标为2的元素将不能被访问到
List的数据结构
- ArrayList 底层实现是数组，查询快，增删慢，线程不安全，效率高
- Vector 底层实现是数组，查询快，增删慢，线程安全，效率低
- LinkedList 底层实现是链表，查询慢，增删快，线程不安全，效率高
如果有很多元素的增加删除，需要用LinkedList，因为用Arraylist会有大量元素的移动，且会遇到扩容的问题
不建议使用Vector，理由如下
- Vector 对每个方法都加上了锁，损耗性能
- 遍历列表时，为保证同步往往通过将不同的方法整合起来，再加锁。Vector同步单个操作的特点并不能保证多线程操作列表时线程安全，此时其锁就成为了负担
- vector容量达到上限时其容量增量是100%，ArrayList是50%，它更耗内存
LinkedList有添加元素的特有方法，add/get~last/first，removeFirst/Last，Vector也有特有addElement(E obj)、elementAt(int index)、elements()功能，被iterator替代
代码示例： 从列表中抽出重复项
ArrayList oldList = new TestClass("ss").mArrayList;
oldList.add("aaaa");
oldList.add("bbbb");
oldList.add("aaaa");
oldList.add("gggg");
oldList.add("cccc");
oldList.add("cccc");
//solution 1
ArrayList<String> newList = new ArrayList<>();
newList.add((String) oldList.get(0));
for (int i = 0; i < oldList.size(); i++) {
boolean shouldAdd = true;
for (int j = 0; j < newList.size(); j++) {
if(oldList.get(i).equals(newList.get(j))) {
shouldAdd = false;
}
}
if(shouldAdd) {
newList.add((String) oldList.get(i));
}
}
// solution 2
Iterator iterator = oldList.iterator();
while(iterator.hasNext()) {
String str = (String) iterator.next();
if(!newList.contains(str)) {
newList.add(str);
}
}
// solution 3
for (int i = 0; i < oldList.size() - 1; i++) {
for (int j = i+1; j < oldList.size(); j++) {
if(oldList.get(i).equals(oldList.get(j))){
oldList.remove(j);
y--;
}
}
}
去除重复元素的方式
//如何利用Comparator工具去除重复元素？？
用LinkedList创建栈结构的集合
private class MyStack extends LinkedList<String> {
private LinkedList<String> mList;
public MyStack() {
mList = new LinkedList<>();
}
public String get() {
return mList.removeFirst();
}
public void addFirst(String string) {
mList.addFirst(string);
}
public boolean isEmpty() {
return mList.isEmpty();
}
}
-
Set
不包含重复元素，最多包含一个null，取出和放入的顺序不一致
常见实现类
HashSet，由一个hash table支持（实际上为hashMap实例），不保证迭代的顺序，特别是不保证每次迭代的顺序都相同。
hashSet添加元素流程
public boolean add(E var1) {
return this.map.put(var1, PRESENT) == null;
//PRESENT是全国人民final的同一代表
}
当你把对象加入HashSet时，HashSet会先计算对象的hashcode值（其实是通过hashCode经过位运算获得的hash值）来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现，直接添加元素。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。不同会添加，这属于处理哈希冲突的范畴；相同，就不能添加。
自定义的hashCode方法必须与equals兼容，如果equals方法返回true，两个对象的hashCode值必须相同。
先看下面这个例子
我们知道不同的对象地址值不同，哪怕其成员完全一致，所以它们的hashCode当然不一样，这是上述所有对象都能被添加的原因。但是如果开发需求类型和成员一致的对象应被视为相同，即equals方法需要被重写，这时候hashCode方法也应该适配。
LinkedhashSet
链表和hash表组成，用于保证数据的有序性和唯一性，底层实现是LinkedHashMap
TreeSet
与散列集类似，但有所改进，能够对元素进行排序，
两种排序方式：
自然排序，子类必须实现Comparable接口，即重写compareTo方法
public class Stuff implements Comparable
自定义的实现了Comparator接口的类,关键在于重写其compare方法
TreeSet<Stuff> treeSet = new TreeSet<Stuff>(new StuffComparator<Stuff>());
具体采用哪种方式取决于构造器
有的类官方设定为Comparable接口实现类，可以进行自然排序，如Integer和String
由此可知，不同于HashMap唯一性主要取决于hashCode和equals方法，TreeMap&TreeSet的排序结果主要取决于子元素的对比方式
TreeSet的实现依赖的是TreeMap，TreeMap是基于红黑树实现的(一种自平衡的二叉树)。
TreeSet的add方法，实现依靠TreeMap的put方法，过程基本是找到根节点，然后二选一排序方式，循环比较最后找到合适插入位置。
获取元素，依靠二叉树里前序遍历方式遍历，
这边截取put方法中的一段
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
依赖TreeSet的添加元素机制能够将玩出的骚操作
将子元素的compareTo方法固定返回一个int值，比如-1，就能让元素一直添加到父元素的left，实现一个单项链表结构。
由此可见，TreeSet的本质是一个TreeMap，
有序性依赖：二叉树结构
唯一性依赖：子元素实现的对比方式
实践中偏向哪种方式——个人倾向重写Comparator接口，因为比较逻辑和bean对象分离，且能使用new Comparator的匿名内部类方式让快捷变换比较逻辑。
Queue
实现在尾部添加，在头部删除一个元素；对于双端队列，可以有效
地同时添加或者删除元素，不支持在队列中间增删元素
Map集合
以键值对出现的数据结构，Map集合键是唯一的，其数据结构与键有关，跟值无关。
特有的方法有
containsKey();
containsValue();
get(Object key); return the value
Collection<V> values()
keySet()
put(K key, V value) 除了添加还可以替换同键的值;
entrySet() ; Returns a Set view of the mappings contained in this map.
运用举例
Map<String, String> map = new HashMap();
map.put("Jay", "Kun");
map.put("Jolin", "???");
map.put("kotlin", "java");
//获取所有键
Set<String> set = map.keySet();
for (String str :
set) {
System.out.println(str+"");
}
//获取所有值
Collection<String> collection = map.values();
for (String str :
collection) {
System.out.println(str);
}
//this set is java.util.HashMap$KeySet
//this collection is java.util.HashMap$Values
//遍历集合
//solution 1
Set<String> set = map.keySet();
for (String str :
set) {
System.out.println(map.get(str));
}
//solution 2
Set<Map.Entry<String, String>> entries = map.entrySet();
for (Map.Entry<String, String> entry :
entries) {
System.out.println(entry);
}
关键实现类
HashMap
hash存储优势在于：对于没有实现RandomAccess接口与的集合，当忘记了数据的位置时，想快速查找一个数据很低效。如果不在意元素的顺序，散列表就可以实现快速查找功能。
hashMap底层实现是hash表，实质是元素为链表的数组，我们习惯把数组元素称为桶（比较形象）
hashMap以键值对的方式存储数据，关键是key要保持唯一，而value虽然功能上是我们真正想要的数据，但在该数据结构的存取中根本没有考虑value的存在，可以当做key的一个附属品来使用。
hashMap添加元素的过程
当你把对象加入hashMap时，hashMap会先计算对象的hashcode值（其实是通过hashCode经过位运算获得的hash值）来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现，直接添加元素。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。不同会添加，这属于处理哈希冲突的范畴；相同，就不能添加。
通过为不同对象生成一个整数，成为hash code（该值能快速生成），不同对象拥有不同的散列码。
java中，散列表用链表数组实现，每个链表被称为桶，要想查找对象的位置，首先计算其散列码，然后与桶的总数取余，结果就是元素所在桶的索引。
实际开发中的一个问题：
hash 冲突：有时候，桶会出现被占满的情况，即不同的对象产生了相同的hash值。解决这个问题通常是两种方法：链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式，链表是单向链表，相同hash值得不同对象存储在同一个槽位的链表中。
hashSet和HashMap在使用的时候，需要保证添加进去的元素是不可变的，api只能保证元素添加进去的时候是不可变的，但无法控制元素后面是否会变
hashMap的get(Object key)方法参数不是泛型，因为只需要用到equals和hashcode方法。返回值类型是泛型类型
实际开发中的另一个问题：
HashSet<Stuff> stuffs = new HashSet<>();
Stuff stuff1 = new Stuff(23,"Leonardo");
Stuff stuff2 = new Stuff(23,"Leonardo");
Stuff stuff3 = new Stuff(24,"Hugo");
stuffs.add(stuff1);
stuffs.add(stuff2);
stuffs.add(stuff3);
for (Stuff employee:stuffs) {
System.out.println(employee.toString());
}
/**
* console:
* Stuff{ID=23, mName='Leonardo'}
Stuff{ID=24, mName='Hugo'}
Stuff{ID=23, mName='Leonardo'}
*/
我们知道不同的对象地址值不同，哪怕其成员完全一致，所以它们的hashCode理论上是不一样的，这是上述所有对象都能被添加的原因。但是如果开发需求类型和成员一致的对象应被视为相同，即equals方法需要被重写，这时候hashCode方法也应该适配，否则会出现equals返回true的两个对象hashCode不同。所以我们要同时自定义hashCode和equals方法——
自定义的hashCode方法必须与equals兼容，如果equals方法返回true，两个对象的hashCode值必须相同。
既然如此，hashCode的生成就不在依赖于第一无二的对象，而是考虑到了成员变量，其变化范围就会缩小，缩小就增加了hash冲突的可能性，导致性能下降，所以又要尽量random化hashCode，看下面的一种方案。
** 核心需求：适配equals同时尽量不会出现hash冲突 **
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (!(o instanceof Stuff))
return false;
Stuff stuff = (Stuff) o;
if (ID != stuff.ID)
return false;
return mName.equals(stuff.mName);
}
@Override
public int hashCode() {
int result = ID;
result = 31 * result + mName.hashCode();
return result;
}
如果散列码分布均匀，桶的数目也足够大，需要比较的次数就少，hashMap的效率就很高；所以想保证性能，就要指定初始桶的数目，太少会增加散列冲突的可能性，一般建议设置为元素个数的75%~150%，如果散列表太满，就需要再散列。
HashMap和HashTable的区别，前者线程不安全，后者方法用synchronized修饰；前者能够出现一个唯一的null键，且可以有多个键对应null值，但后者中键值不能有null;初始容量大小和每次扩充容量大小的不同.
jdk 1.8实现方式稍有不同
相比于之前的版本， JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap
由一个双向链表和hash表组成，具备HashMap键唯一的特点，同时保证存取顺序一致
TreeMap
依赖一个红黑树实现数据唯一和排序
HashMap和Hashtable的区别
- 线程不安全，效率高vs线程安全，效率低；HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）
- 允许使用最多一个null键和多个null值vs不允许使用null作为键值
- 初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。
- JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制
总之，不要使用Hashtable
其他补充
1.遍历集合
使用Lambda表达式遍历集合
public static void main(String[] args) {
List<String> names = new ArrayList<String>();
names.add("aa");
names.add("bb");
names.add("cc");
names.forEach(name -> System.out.println(name));
}
lambda表达式的目标类型是Consumer，并将集合的元素类型作为生成Consumer对象的泛型参数，然后自动将集合元素作为方法参数传递给Consumer对象的accept方法。foreach方法中会调用一个for-each循环。上面这一句代码可以看做是下面代码的极简形式：
Consumer<String> printConsumer= new Consumer<String>() {
public void accept(String name) {
System.out.println(name);
}
};
names.forEach(printConsumer);
其等效于手写一个foreach循环，并没有在线程安全性上做改进。
更多内容，可以参考网页https://www.baeldung.com/foreach-java
2、Collections
对集合进行操作的工具类，有对集合进行二分查找和排序的方法。
public static <T> void sort(List<T> list)默认按照自然顺序排序
public static <T> int binarySearch(List<?> list,T key)二分查找
public static <T> T max(Collection<?> coll)最大值
public static void reverse(List<?> list)翻转
public static void shuffle(List<?> list)洗牌，随机置换
