一、集合概念
1、Java中对于各种数据结构的实现，就是我们用到的集合(集合是能够动态增长长度的容器)。
2.我们之前所学过的容器：
①.变量int a=10;
②.面向对象class Car{
String name;
int price;
}
③.数组(容器)，创建一个指定长度的数组
Car[] cars = new Car[10];
程序运行时，数据数量是变化的，都是数组长度一旦给定，就不能改变。需要频繁的扩容，数组的优点是查询速度快。
然而对数据操作是多种多样的，增删比较多查询较少，链表结构。针对于程序中，这种不同存储操作需求，针对于程序中,这种不同存储操作需求,所以java语言提供了许多不同的存储结构(对底层结构进行包装)：1.数组 2.链表 3.哈希 4.树
二、集合API
-集合体系概述
Java的集合框架是由很多接口、抽象类、具体类组成的，都位于java.util包中。
(Collection List Set Map为接口)
三、Collection接口
1、Collection接口，作为单列集合的顶级接口，里面定义了单列集合共有的方法
。
方法以增，删，改，查，判断，转换为主
2、Collection, ArrayList后面是jdk5之后的语法—泛型
可以通过泛型语法，为集合设置一个类型，这样就只能储存设置的数据类型
（集合中建议储存同一类型数据）。
3、集合是容器，可以存储不同的数据，严格上讲集合是可以存储任何类型的(只能存储引用类型)。
4、方法
boolean add(Object element);
boolean remove(Object element);
void clear();
int size();
boolean isEmpty();
boolean contains(Object element);
boolean retainAll(Collection c);求交集,集合数据发生变化返回true,不变返回false
c.add("a");
c1.addAll(c);//把一个集合添加到另一个集合
// c.clear();//清除集合中的元素
c.equals(c1);//比较两个集合中的内容是否相同
c.retainAll(c1);//在c中保留与c交集元素 若c变化则true 不变化false
System.out.println(c.size());//数组长度length属性，字符串长度length方法，集合长度size();
System.out.println(c1.remove("a"));//从该集合中删除指定元素的单个实例（如果存在返回true）。
System.out.println(c.isEmpty());
System.out.println(c1);
Object[]objs=c.toArray();//将集合转为Object类型数组
System.out.println(Arrays.toString(objs));
String[] sobject = c.toArray(new String[c.size()]);//将集合转为指定类型数组
System.out.println(Arrays.toString(sobject));
四、List接口
1、List继承了Collection接口,有三个实现的类。
List共有的特点：有序(按照添加顺序排序)，可以有重复元素。
(1).ArrayList
底层是通过数组实现的，是可以变长的
查询快，中间增删慢
(2).LinkedList双链表
底层是链表实现
查询慢(必须从头/尾开始查找，直到找到)，中间增删块，只需要改变后继节点位置
(3).Vector
底层是数组实现，是线程安全的
ArrayList底层是数组实现
补充：
add();向集合中添加元素时，底层会默认创建一个长度为10的Object类型数组，当数组装满是，再次添加元素，会创建一个原来数组长度1.5倍的新数组，将原数组内容复制过来，将新数组对象的地址赋给底层的数组。
public boolean add(E e) { ensureCapacityInternal(size + 1);
// Increments modCount!!
elementData[size++] = e;
return true;}
if (minCapacity - elementData.length > 0)
grow(minCapacity);//底层扩展的方法
展开：
ArrayList的常用方法
add(int index, E element)
get(int index)
indexOf(Object o)
lastIndexOf(Object o)
remove(int index) 删除并返回指定位置元素
removeRange(int fromIndex, int toIndex) 删除指定区间的元素(子类继承使用)
set(int index, E element)
list.add(0,"M");//向指定下标位置上添加元素System.out.println(list.get(11));//返回此列表中指定位置的元素。
System.out.println(list.remove(0));//删除并返回指定位置的元素
list.set(2,"k");//替换指定位置的元素System.out.println(list.size());//返回集合中实际存储的元素个数
LinkedList的常用方法
底层也是数组实现，但是是线程安全的(synchronized修饰)
add(int index,Object element)
addFirist(Object element)
addLast(Object element)
get(int index)
removeFirst()
removeLast()
remove(int index)
getFirst()
getLast()
在链表中添加元素使用node节点
双链表：可以从头开始找 也可以从尾开始找
llist.add("a");//向链表中添加元素
System.out.println(llist.get(3));//要找的元素位置小于size/2,从头节点开始找，否则从尾节点开始找
llist.addFirst("X");
llist.addLast("Y");
System.out.println(llist.removeFirst());//从此列表中删除并返回第一个元素
System.out.println(llist.removeLast());//从此列表中删除并返回最后一个元素
System.out.println(llist);
五、List接口集合迭代
● for循环遍历
● 增强for循环的遍历
● 迭代器遍历（Iterator迭代器、ListIterator迭代器(只支持List接口下的实现类)）
1、for循环遍历集合：
for循环遍历集合时可以从中删除元素
注意：删除元素后，索引向后移动，可能出现错漏问题
for (int i = 0; i <= list.size(); i++) {
if (list.get(i).equals("a")) { list.remove(i);
}
}
System.out.println(list);
2、增强for循环遍历集合：
但是在遍历过程中不能删除元素,如果删除会抛出ConcurrentModificationException(并发修改异常)*/
for (String s:list) {
if(s.equals("d")){
list.remove(s);
}
}
System.out.println(list);
3、迭代器遍历List集合
iterator();返回了一个ArrayList中的内部类对象,实现Iterator接口
此内部类,专门用作对集合进行遍历时的控制
hasNext();判断集合中是否还有元素,有返回true,否则返回false
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String s = it.next();
if (s.equals("d")) {
it.remove();//如果需要在遍历中删除元素,请使用迭代器中的remove()
}
}
System.out.println(list);
迭代器遍历List集合
针对List接口下的集合类还提供listIterator()
ListIterator<String> it1 = list.listIterator(2);//从指定的位置开始遍历
while (it1.hasNext()) {
String s = it1.next();
if (s.equals("d")) {
it1.remove();
}
}
System.out.println(list);
ListIterator<String> it2 =list.listIterator(list.size());
while (it2.hasPrevious()) {
String s2 = it2.previous();
System.out.println(s2);//倒序输出
}
六、Set接口
共有特点：不能存储重复元素，无序(不是按照添加顺序排列)。
HashSet:存储的元素顺序不固定 b,c,a hashcode(); equals();
TreeSet:可以按照元素的自然顺序排序(c,a,b-----a,b,c) 添加的元素类型，必须实现排序接口。
1、HashSet
无序且不重复的集合
底层使用的是HashMap实现的
public HashSet() {
map = new HashMap<>();
}
2、有序(可以根据元素自然顺序排序) 且不能存储重复元素
底层用TreeMap实现
public TreeSet() {
this(new TreeMap<E,Object>());
}
HashSet<String> set1 = new HashSet<>(list);//让数组没有重复元素用HashSet System.out.println(set1);
TreeSet<String> set2 = new TreeSet<>(list);//摇完奖排序类型用TreeSet System.out.println(set2);
3.Set接口遍历方式
增强for循环
迭代器遍历
七、Map接口
Map:双列集合 键–→值
1、HashMap
键是无序的
HashMap中元素的key值不能重复，
排列顺序是不固定的,可以存储一个
为null的键。
2、TreeMap
线程安全的map
TreeMap中所有的元素都保持着某种固定的顺序，如果需要得到一个有序的Map就应该使用TreeMap，key值所在类必须实现Comparable接口。
3、HashTable
可以通过键进行排序
4、Map迭代遍历
5、Map接口常用的方法
V put(K key,V value)
V remove(Object key)
void clear()
boolean containsKey(Object key)
boolean containsValue(Object value)
boolean isEmpty()
int size()
V get(Object key)
Collection values()
Set keySet()
Set<Map.Entry<K,V>> entrySet()
//eg:
Collection<String> c = hashMap.values();
System.out.println(c);//输出值
Set<String> set = hashMap.keySet();
System.out.println(set);//输出键
2、Hashtable
HashMap键不能重复，值能重复
键是无序的
不可以储存一个为null的键，也不能存储为null的值
被synchronized修饰，是线程安全的
3、TreeMap
TreeMap键不能重复,值可以重复
键可以排序，作为键类型的类必须实现排序接口
HashMap<Car, String> chm =new HashMap<>();
Car bm1=new Car(1,"baoma1");
Car bm2=new Car(2,"baoma2");
Car bm3=new Car(3,"baoma3");
chm.put(bm1,"a");
chm.put(bm3,"b");
chm.put(bm2,"c");
System.out.println(chm);
public class Car implements Comparable<Car>{
/*@Override
public int compareTo(Car o) {
return this.no-o.no;
}*/
}
Map集合遍历
方式1：根据键找值
? 获取所有键的集合
? 遍历键的集合，获取到每一个键
? 根据键找值
方式2：根据键值对对象找键和值(Map常用)
? 获取所有键值对对象的集合
? 遍历键值对对象的集合，获取到每一个键值对对象
? 根据键值对对象找键和值
Map<String, String> map = new HashMap();
map.put("a", "aa");
map.put("s", "ss");
map.put("b", "bbb");
map.put("x", "x1");
map.put("x", "x2");
Set<Map.Entry<String, String>> entries = map.entrySet();
for (Map.Entry<String, String> entry : entries) { System.out.println("key为：" + entry.getKey() + ";value为：" + entry.getValue());
}
3、TreeMap
TreeMap键不能重复,值可以重复
键可以排序，作为键类型的类必须实现排序接口
TreeMap根据key值排序，key值需要实现Comparable接口，
重写compareTo方法。TreeMap根据compareTo的逻辑，对
key进行排序
键是红黑树结构，可以保证键的排序和唯一性
八、Collections类
Collections是集合类的工具类，与数组的工具类Arrays类似。
addAl l(Col lection<? super T> c, T… elements);
binarySearch(List<? extends Comparable<? super T>> l ist, T key)
sort(List l ist)
sort(List l ist, Comparator<? super T> c)
swap(List<?> l ist, int i, int j)
copy(List<? super T> dest, List<? extends T> src) ; 注意 dest size需大于等于src.size
emptyList() 返回为空的集合,不能添加数据
fill(List<? super T> l ist, T obj) //用指定的元素代替指定列表的所有元素。
max(Col lection<? extends T> col l)
min(Col lection<? extends T> col l)
replaceAl l(List l ist, T oldVal, T newVal)
reverse(List<?> l ist) //逆序输出
shuffle(List<?> l ist) //随机排序
copy(dest,src) //集合复制
九、Hash结构
1、HashSet
HashSet中不能存储重复元素。
Object中的haschcode和equals比较的都是地址，其他类(重写了hashcode方法和equals方法)中的haschcode比较的是哈希值，equals比较的是内容。(哈希值是用内容算出来的，但是不安全，比如"通话"和"重地"的哈希值相同)
先用哈希值判断，若相同再用equals，提高比较效率。
自定义类需要重写Hashcode();和equals();
HashSet set = new HashSet;
2、HashMap
键值对，双列集合，键不可以重复，值可以重复，可以储存一个null键。
底层存储结构：java8
有三种数据结构：
1.数组(哈希表) 2.链表 3.红黑树
添加元素过程：
算出元素哈希值→用Mod %算出位置→将元素封装到一个Node对象中→将对象放到位置上。
哈希数组长度默认16
负载因子设是0.75
(3/4时扩容，为原来的2倍)
链表长度为8且哈希数组长度大于等于64时变成红黑树
3.HashMap源码分析
