集合
概念
数据结构：存储数据的某种结构
（1）底层的物理结构
①数组：开辟连续的存储空间，每一个元素使用[下标]进行区别
②链式：不需要开辟连续的存储空间，但是需要“结点”来包装要存储的数据，结点包含两部分内容：
A、数据
B、记录其他结点的地址，例如：next，pre，left，right，parent等
（2）表现出来的逻辑结构：动态数组、单向链表、双向链表、队列、栈、二叉树、哈希表、图等
Collection
因为集合的类型很多，那么我们把它们称为集合框架。
集合框架分为两个家族：Collection（一组对象）和Map（一组映射关系、一组键值对）
Collection
Collection是代表一种对象的集合。它是Collection系列的根接口。
它们虽然：有些可能是有序的，有些可能是无序的，有些可能可以重复的，有些不能重复的，但是它们有共同的操作规范，因此这些操作的规范就抽象为了Collection接口。
常用方法：
（1）boolean add(Object obj)：添加一个
（2）boolean addAll（Collection c）：添加多个
（3）boolean remove(Object obj)：删除一个
（4）boolean removeAll(Collection c )： 删除多个
（5）boolean contains(Object c)：是否包含某个
（6）boolean containsAll(Collection c)： 是否包含所有
（7）boolean isEmpty()：是否为空
（8）int size()：获取元素个数
（9）void clear()：清空集合
（10）Object[] toArray()：获取所有元素
（11）Iterator iterator()： 获取遍历当前集合的迭代器对象
（12）retainAll(Collection c)：求当前集合与c集合的交集
Collection系列的集合的遍历
1、明确使用Iterator迭代器
Collection c =....;
Iterator iter = c.iterator();
while(iter.hashNext()){
Object obj = iter.next();
//...
}
Iterator接口的方法：
（1）boolean hasNext()
（2）Object next()
（3）void remove()
2、foreach
Collection c = ....;
for(Object obj : c){
//...
}
Iterator也是一个接口，它的实现类，通常在集合（容器）类中用内部类实现。并在iterator()的方法中创建它的对象。
public class MyArrayList implements Iterable{
private Object[]data;
private int total;
//其他代码省略....
@Override
public Iterator iterator() {
return new MyItr();
}
private class MyItr implements Iterator{
private int cursor;//游标
@Override
public boolean hasNext() {
return cursor!=total;
}
@Override
public Object next() {
return data[cursor++];
}
}
}
List
List概述
List：是Collection的子接口。
List系列的集合：有序的、可重复的
List系列的常用集合：ArrayList、Vector、LinkedList、Stack
List的API
常用方法：
（1）boolean add(Object obj)：添加一个
（2）boolean addAll（Collection c）：添加多个
（3）void add(int index, Object obj)：添加一个，指定位置添加
（4）void addAll(int index, Collection c）：添加多个
（5）boolean remove(Object obj)：删除一个
（6）Object remove(int index)：删除指定位置的元素，并返回刚刚删除的元素
（7）boolean removeAll(Collection c )： 删除多个
（8）boolean contains(Object c)：是否包含某个
（9）boolean containsAll(Collection c)： 是否包含所有
（10）boolean isEmpty()：是否为空
（11）int size()：获取元素个数
（12）void clear()：清空集合
（13）Object[] toArray()：获取所有元素
（14）Iterator iterator()： 获取遍历当前集合的迭代器对象
（15）retainAll(Collection c)：求当前集合与c集合的交集
（16）ListIterator listIterator()：获取遍历当前集合的迭代器对象，这个迭代器可以往前、往后遍历
（17）ListIterator listIterator(int index)：从[index]位置开始，往前或往后遍历
（18）Object get(int index)：返回index位置的元素
（19）List subList(int start, int end)：截取[start,end)部分的子列表
ListIterator接口
Iterator接口的方法：
（1）boolean hasNext()
（2）Object next()
（3）void remove()
ListIterator是Iterator子接口：增加了如下方法
（4）void add(Object obj)
（5）void set(Object obj)
（6）boolean hasPrevious()
（7）Object previous()
（8）int nextIndex()
（9）int previousIndex()
List的实现类们的区别
ArrayList、Vector、LinkedList、Stack
（1）ArrayList、Vector：都是动态数组
Vector是最早版本的动态数组，线程安全的，默认扩容机制是2倍，支持旧版的迭代器Enumeration
ArrayList是后增的动态数组，线程不安全的，默认扩容机制是1.5倍
（2）动态数组与LinkedList的区别
动态数组：底层物理结构是数组
优点：根据[下标]访问的速度很快
缺点：需要开辟连续的存储空间，而且需要扩容，移动元素等操作
LinkedList：底层物理结构是双向链表
优点：在增加、删除元素时，不需要移动元素，只需要修改前后元素的引用关系
缺点：我们查找元素时，只能从first或last开始查找
（3）Stack：栈
是Vector的子类。比Vector多了几个方法，能够表现出“先进后出或后进先出”的特点。
①Object peek()：访问栈顶元素
②Object pop()：弹出栈顶元素
③push()：把元素压入栈顶
（4）LinkedList可以作为很多种数据结构使用
单链表：只关注next就可以
队列：先进先出，找对应的方法
双端队列(JDK1.6加入)：两头都可以进出，找对应的方法
栈：先进后出，找对应的方法
Set
Set概述
Set系列的集合：不可重复的
Set系列的集合，有有序的也有无序的。HashSet无序的，TreeSet按照元素的大小顺序遍历，LinkedHashSet按照元素的添加顺序遍历。
实现类的特点
（1）HashSet：
底层是HashMap实现。添加到HashSet的元素是作为HashMap的key，value是一个Object类型的常量对象PRESENT。
依赖于元素的hashCode()和equals()保证元素的不可重复，存储位置和hashCode()值有关，根据hashCode()来算出它在底层table数组中的[index]
（2）TreeSet
底层是TreeMap实现。添加到TreeSet的元素是作为TreeMap的key，value是一个Object类型的常量对象PRESENT。
依赖于元素的大小，要么是java.lang.Comparable接口compareTo(Object obj)，要么是java.util.Comparator接口的compare(Object o1, Object o2)来比较元素的大小。认为大小相等的两个元素就是重复元素。
（3）LinkedHashSet
底层是LinkedHashMap。添加到LinkedHashSet的元素是作为LinkedHashMap的key，value是一个Object类型的常量对象PRESENT。
LinkedHashSet是HashSet的子类，比父类多维护了元素的添加顺序。
当且仅当，你既想要元素不可重复，又要保证元素的添加顺序时，再使用它。
Map
Map概述
用来存储键值对，映射关系的集合。所有的Map的key都不能重复。
键值对、映射关系的类型：Entry类型
Entry接口是Map接口的内部接口。所有的Map的键值对的类型都实现了这个接口。
HashMap中的映射关系，是有一个内部类来实现Entry的接口，JDK1.7是一个叫做Entry的内部类实现Entry接口。
JDK1.8是一个叫做Node的内部类实现Entry接口。
TreeMap中的映射关系，是有一个内部类Entry来实现Entry的接口
API
（1）put(Object key, Object value)：添加一对映射关系
（2）putAll(Map m)：添加多对映射关系
（3）clear()：清空map
（4）remove(Object key)：根据key删除一对
（5）int size()：获取有效元素的对数
（6）containsKey(Object key)：是否包含某个key
（7）containsValue(Object value)：是否包含某个value
（8）Object get(Object key)：根据key获取value
（9）遍历相关的几个方法
Collection values()：获取所有的value进行遍历
Set keySet()：获取所有key进行遍历
Set entrySet()：获取所有映射关系进行遍历
Map的实现类们的区别
（1）HashMap：
依据key的hashCode()和equals()来保证key是否重复。
key如果重复，新的value会替换旧的value。
hashCode()决定了映射关系在table数组中的存储的位置，index = hash(key.hashCode()) & table.length-1
HashMap的底层实现：JDK1.7是数组+链表；JDK1.8是数组+链表/红黑树
（2）TreeMap
依据key的大小来保证key是否重复。key如果重复，新的value会替换旧的value。
key的大小依赖于，java.lang.Comparable或java.util.Comparator。
（3）LinkedHashMap
依据key的hashCode()和equals()来保证key是否重复。key如果重复，新的value会替换旧的value。
LinkedHashMap是HashMap的子类，比HashMap多了添加顺序