Collection集合体系
Collection集合包括有List和Set两种，是单列集合，每个元素包含一个值。
Collection集合
Collection集合特点
List集合：添加的元素有序（存入数据与取出数据顺序相同）、可重复、有索引
ArrayList、LinekdList：有序、可重复、有索引 Set集合：添加元素无序（存入数据与取出数据顺序可能）、不重复、无索引
HashSet：无序、不重复、无索引LinkedHashSet：有序、不重复、无索引TreeSet：按照大小默认升序排序、不重复、无索引
Collection提供常用方法（同样也是List、Set常用方法）
方法描述add(E e)添加元素，成功返回truec1.addAll(Collection c2)将c2全部元素添加到c1，c1、c2数据应相同clear()清空集合元素isEmpty()判断集合是否为空size()获取集合大小contains(Object obj)精确判断集合中是否包含某个元素remove(E e)删除某个元素，存在多个重复元素删除第一个otArray()集合转数组interator()获取集合中的迭代器对象
Collection集合遍历方式
迭代器
迭代器（Interator）遍历集合的专用方法。
Collection集合获取迭代器方法
方法作用Iterator iterator()返回集合中的迭代器对象，该迭代器对象默认指向当前集合的第一个元素。
Iterator迭代器常用方法
方法作用hasNext()判断当前位置是否有元素存在，存在返回truenext()获取当前位置元素，同时将迭代器指向下一个元素处
注：使用next()获取元素时，如果当前位置无元素（发生越界），程序会报NoSuchElementException异常
使用迭代器遍历集合
Iterator
while(iterator.hasNext()) { //使用while循环，当迭代器所在位置没有元素时，结束循环
String element = iterator.next(); //获取当前位置元素，同时将迭代器指向下一个元素处
// 对获取的元素执行操作
System.out.println(element);
}
增强for循环
for(元素数据类型 变量名 : 集合或数据) {
//对集合或数组内元素进行操作
}
注：增强for循环，本质是迭代器遍历集合的简化写法
Lambda遍历循环
使用Collection的方法forEach(Consumer action)方法结合Lamdba对集合对象遍历
// 简化前
collection.forEach(new consumer
@Override
public void accept(String s) { //s为获取到的集合中的元素
//对s进行操作
}
});
// 简化后
collection.forEach(s -> {
//对s进行操作
});
// forEach(Consumer action)源代码
default void forEach(Consumer action) {
Object.requireNonNull(action); // 判断传递过来的参数是否为空
// 增强for循环遍历
for(T t : this) {
action.accept(t);
}
}
集合存储对象原理
当创建集合时，会在堆内存中创建一个容器用来存放集合内元素地址。栈内存中的变量movices存放容器地址当调用add(E e)方法添加元素时，会在堆内存中创建一个空间来存放元素信息，同时将空间地址交给容器
List集合
List集合特点
List集合特点：有序、可重复、有索引ArrayList集合特点：有序、可重复、有索引LinkedList集合特点：有序、可重复、有索引ArrayList和LinkedList底层实现不同，适合场景不同
List集合特有方法
方法说明add(int index, E e)在指定索引位置index添加元素eremove(int index)删除指定索引处的元素，并返回被删除的元素get(int index)获取指定索引处的元素set(int index, E e)修改指定索引处的元素为e，修改成功后，返回指定位置的原本数据
List集合遍历方式
普通for循环迭代器增强for循环Lambda遍历循环
ArrayList集合底层实现原理
底层基于数组实现
利用无参构造器创建的集合，在底层创建一个默认长度为0的数组添加第一个元素时，底层创建一个新的长度为10的数组当数组存放的元素满时，扩容1.5倍；如果一次添加多个数据且扩容1.5倍容量后依然放不下，新创建数组长度以实际为准 优点：
查询速度快：根据地址值+索引定位数据，查询数据耗时相同适用于查询操作频繁的场景 缺点：
添加、删除效率低：需要移动索引在添加/删除元素后面的元素。如果是添加操作，可能还需要对数组进行扩容 适用场景：
适合查询操作较多，删除、添加操作较少的场景
LinkedList集合底层实现原理
基于双链表实现
链表中的节点是独立的对象，在内存中是不连续的。每个节点包含下一个节点和上一个节点的地址值以及自己存放的数据 优点：
增加元素快：添加元素后，修改新增节点前后节点存放地址值就可以了，让前节点指向下一个节点的地址指向新增节点，后节点指向前一个节点的地址指向新增节点，同时让新增节点指向前节点和后节点删除元素快：删除元素后，修改删除节点前后节点存放地址值就可以了，让前节点指向下一个节点的地址指向删除节点的后节点，让后节点指向前一个节点的地址指向删除节点的前节点，最后删除掉要删除的节点就可以了 缺点：
查询慢：无论查询那个数据都要从头开始找
LinkedList新增方法
方法说明addFirst(E e)在列表开头添加指定元素addLast(E e)在列表末尾添加指定元素getFirst()获取列表第一个元素getLast()获取列表最后一个元素removeFirst()从列表删除第一个元素removeLast()从列表删除最后一个元素
LinkedList应用场景
设计栈、队列
Set集合
Set集合整体特点
Set集合特点：无序、不重复、无索引
HashSet集合特点：无序、不重复、无索引
LinkedHashSet集合特点：有序、不重复、无索引
TreeSet集合特点：排序、不重复、无索引
HashSet
HashSet集合特点：无序、不重复、无索引
哈希值
哈希值是一个int类型的数值，每一个Java对象都有一个哈希值Java的所有对象都可以调用Object类提供的hashCode方法返回该对象的哈希值同一个对象多次调用hashCode()方法返回哈希值相同不同对象哈希值一般不同，但也可能会相同（哈希碰撞）
底层实现原理
基于哈希表实现哈希表是一种对数据进行增删改查性能都较好的数据结构在JDK8以前，哈希表由 数组 + 链表 组成，JDK8以后，哈希表由 数组 + 链表 + 红黑树 组成
实现流程
创建HashSet集合时，默认创建一个加载因子为0.75，长度为16的数组当向集合存入元素时，用元素的哈希值对数组长度取余，得到元素存放位置当得到的位置为null时，直接存入如果得到的位置有元素，用equals方法对当前位置所有元素（当前位置的 数组 + 链表 上所有元素）进行判断，如果相等存入数组
JDK8以前，新元素存入数组，老元素以链表的形式挂在新元素下面JDK8以后，新元素以链表的形式挂在老元素下面 当数组存放元素 = 数组长度 * 加载因子时，对数组进行扩容操作，同时将原本数组存放的元素转移到新数组中JDK8以后，当链表长度超过8，并且数组长度>= 64时，将链表转换为红黑树
红黑树：一种自平衡的二叉查找树，时间复杂度为 O(logN)
去重机制
注意：HashSet 默认不能对内容相同的两个不同对象去重
原因：不同对象哈希值一般不同
解决：让内容相同的两个对象的哈希值相同
方法：重新对象的equals()和hashCode()方法
LinkedHashSet
LinkedHashSet集合特点：有序、不重复、无索引
底层实现原理
基于哈希表实现每个元素额外添加双链表机制来记录前后节点的位置
TreeSet
TreeSet集合特点：排序（默认按照元素大小升序排序）、不重复、无索引
底层实现原理
基于红黑树实现
对于数值类型，默认按照数值本身大小升序排序对于字符串类型：默认按照首字符编号升序排序对自定义的对象，默认无法直接排序 自定义排序规则
方法一：让自定义类实现Comparable接口，重写compareTo方法指定排序规则
public class People implements Comparable
private String name;
private int age;
@Override
public int compareTo(People people) {
//左边对象比右边大返回正整数
return this.age - people.age; //按照年龄升序排序
}
}
方法二：通过TreeSet集合调用有参构造器，设置Comparator对象指定比较规则
Set
@Override
public int compareTo(People people1, People people2) {
//左边对象比右边大返回正整数
return people1.getAge() - people2.getAge(); //按照年龄升序排序
}
});
//简化
Set
Map集合
Map集合是双列集合，以键值对的形式存储数据，一次需要存一对数据做为元素Map集合所有键不允许重复，但值可以重复。键和值一一对应，每个键只可以找到自己对应的值应用场景：购物车：一个商品一个键，商品信息为值
Map集合体系
注意：K：键类型，V：值类型
Map集合特点：
Map系列集合特点由键决定，值不做要求HashMap：无序、不重复、无索引LinkedHashMap：有序、不重复、无索引TreeMap：默认按照大小升序排序，不重复，无索引
Map集合常用方法
方法作用put(Object key, Object value)向Map集合中添加一个键get(Object key)根据键获取对应值clear()清空Map集合containKey(Object key)判断Map集合是否包含某个键（精确匹配）containValue(Object value)判断Map集合是否包含某个值（精确匹配，判断值和类型）isEmpty()判断是否为空remove(Object key)根据键删除是键值对，同时返回值size()获取Map集合长度keySet()获取所有键，以Set集合类型返回values()获取Map集合所有值，以Collection集合类型返回map1.putAll(map2)将其他map2集合数据导入当面map1集合
Map集合遍历方式
键找值
先获取所有的Map键，再通过遍历键来找值
方法说明keySet()获取所有键get(Object key)根据键找值
Map
map.put("hhhh","1234");
map.put("hhh","123");
map.put("hh","14");
Set
for(String key : keys) {
String value = map.get(key); //获取键对应的值
System.out.println（key + "--->" + value);
}
键值对
将所有键值对看作一个整体进行遍历
方法说明Set
Map
map.put("hhhh","1234");
map.put("hhh","123");
map.put("hh","14");
Set
for(map.Entry
String key = entry.getKey();
String value = entry.getValue();
System.out.println(key + "----->" + value);
}
Lambda
方法说明forEach(BiConsumer action)结合Lambda遍历Map集合
Map
map.put("hhhh","1234");
map.put("hhh","123");
map.put("hh","14");
//简化前,forEach内部基于 键值对 的查找方式实现
map.forEach(new BiConsumer
@Override
public void accept(String key, String value) {
System.out.println(k + "------>" + v);
}
});
//简化后
map.forEach((k, v) -> {
System.out.println(k + "------>" + v);
});
HashMap底层原理
基于哈希表实现，数组+链表，数组+链表+红黑树
特点：无序、无重复、无索引
对象元素默认可重复（不同元素Hash值一般不同），可以重写hashCode()和equals()方法解决。
注: HashSet集合其实是一个HashMap集合，只保存键，未保存值
LinkedHashMap底层原理
基于哈希表+双链表实现，数组+链表，数组+链表+红黑树
特点：有序、无重复、无索引
对象元素默认可重复（不同元素Hash值一般不同），可以重写hashCode()和equals()方法解决。
注: HashSet集合其实是一个HashMap集合，只保存键，未保存值
TreeMap底层原理
基于红黑树实现，数组+链表，数组+链表+红黑树
特点：默认按照从小到大顺序排序（只会对key排序）、无重复、无索引
注: HashSet集合其实是一个HashMap集合，只保存键，未保存值
对对象进行排序有两种方法：
在类中实现Comparable接口并重写compareTo()方法
public class People implements Comparable
private String name;
private int age;
@Override
public int compareTo(People people) {
//左边对象比右边大返回正整数
return this.age - people.age; //按照年龄升序排序
}
}
使用有参构造器声明TreeMap集合，声明集合时指定比较器对象
Map
@Override
public int compareTo(People people1, People people2) {
//左边对象比右边大返回正整数
return people1.getAge() - people2.getAge(); //按照年龄升序排序
}
});
//简化
Map