一、集合的概述
1.Java集合大概可以分为Set,List,Map,Queue四种体系，其中Set是无序唯一的（不可重复），List是有序不唯一的（可以重复）
2.Java集合主要有Collection和Map接口，这两个集合框架又包含了一些子类接口的实现
二、toArray()方法和toString()方法1.toArray()：不管Collection是否使用了泛型，toArray()的返回值总是Object[]，后来新增加了一个toArray(IntFunction)方法后，当Collection使用了泛型后返回的类型为特定类型的数组
2.toString()一次性的输出集合中所有的元素
三、几种遍历 1、使用lambda表达式import java.util.ArrayList;
import java.util.List;
//集合容器
public class Test {
public static void main(String[] args) {
ArrayList list = new ArrayList<>();
list.add("lpf");
list.add("sjp");
System.out.println(list.toString());
list.forEach((item->{
System.out.println(item);
}));
}
}
2、使用Iterator遍历元素--迭代器
定义了四个方法
1.Boolean hasNext():如果被迭代的元素中还没有被遍历完，返回true
2.Object next()：返回集合的下一个元素
3.void remove():删除集合里上一次next方法返回的元素
4.void forEachRemaining(Consumer action):java8默认的方法，使用lambda表达式来遍历
注意的是：Iterator迭代器采用的是快速失败（fail-fast）机制，一旦集合被修改立即引发ConcurrentModificationException异常
import java.awt.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
//集合容器
public class Test {
public static void main(String[] args) {
HashSet h = new HashSet<>();
h.add("java");
h.add("python");
h.add("Linux");
//使用iterator获取iterator对象
Iterator iterator=h.iterator();
while(iterator.hasNext()){
//泛型给出的对象类型
String item=(String) iterator.next();
System.out.println(item);
if(item.equals("python")){
//使用iterator迭代过程中不可以修改集合的元素
//h.remove(item)；
}
}
}
}
3、使用forEach遍历集合元素
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
//集合容器
public class Test {
public static void main(String[] args) {
for(String item:h){
System.out.println(item);
if(item.equals("python")){
//引发异常
//h.remove(item)；
}
}
}
}
4.for循环遍历
import java.util.ArrayList;
//集合容器
public class Test {
public static void main(String[] args) {
ArrayList list = new ArrayList<>();
list.add("lpf");
list.add("sjp");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}
四、Set集合
1.HashSet类
HashSet按照Hash算法来存储集合中的元素因此具有很好的存取和查找功能
特点1.不能保证元素的排列顺序（无序性）
2.HashSet不是同步的，如果多个线程访问HashSet,假设有两个或两个以上的线程同时修改集合中的元素，则必须通过代码来同步
3.集合中的元素可以为null
HashSet判断两个元素相等的标准：通过equals（）方法比较相等，并且两个对象的hashCode()方法的返回值也相等
说一下 HashSet 的实现原理？HashSet速度快的原因：我们都知道数组通过索引来快速的查找元素，但是HashSet没有索引这一概念，所以借助hash算法的功能，根据元素的hashcode计算出元素的位置，之所以不适用数组是因为数组的长度不可变，无法增加长度，所以才使用HashSet,因此，从HashSet中访问元素时，先计算改元素的hashcode值（调用该对象的hashcode()方法的返回值），然乎直接用hashcode的值所对应的位置取出元素
HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap的value统一为PRESENT，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，HashSet 不允许重复的值。
HashSet如何检查重复？HashSet是如何保证数据不可重复的？向HashSet 中add ()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结合equles 方法比较。 HashSet 中的add ()方法会使用HashMap 的put()方法。
HashMap 的 key 是唯一的，由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V。所以不会重复（ HashMap 比较key是否相等是先比较hashcode 再比较equals ）。
hashCode（）与equals（）的相关规定：如果两个对象相等，则hashcode一定也是相同的
两个对象相等,对两个equals方法返回true
两个对象有相同的hashcode值，它们也不一定是相等的
综上，equals方法被覆盖过，则hashCode方法也必须被覆盖
hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。
==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
==是指对内存地址进行比较 equals()是对字符串的内容进行比较
==指引用是否相同 equals()指的是值是否相同
| HashMap | HashSet |
|---|---|
| 实现了Map接口 | 实现Set接口 |
| 存储键值对 | 仅存储对象 |
| 调用put（）向map中添加元素 | 调用add（）方法向Set中添加元素 |
| HashMap使用键（Key）计算Hashcode | HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false |
| HashMap相对于HashSet较快，因为它是使用唯一的键获取对象 | HashSet较HashMap来说比较慢 |
HashSet类的子类，他将会按照添加元素顺序访问元素（顺序的一致性）
import java.awt.*;
import java.util.*;
//集合容器
public class Test {
public static void main(String[] args) {
linkedHashSet ls = new linkedHashSet<>();
ls.add("完美世界");
ls.add("斗罗大陆");
ls.add("吞噬星空");
System.out.println(ls);//[完美世界, 斗罗大陆, 吞噬星空]
ls.remove("斗罗大陆");
ls.add("紫川");
System.out.println(ls);//[完美世界, 吞噬星空, 紫川]
}
}
3.TreeSet类
TreeSet中的元素时有序的
TreeSet是采用红黑树的数据结构来存储元素集合的
import java.awt.*;
import java.util.*;
import java.util.List;
//集合容器
public class Test {
public static void main(String[] args) {
TreeSet it= new TreeSet<>();
it.add(10);
it.add(-20);
it.add(15);
it.add(-1);
it.add(45);
it.add(-8);
//输出元素(有序性)
System.out.println(it);//[-20, -8, -1, 10, 15, 45]
//输出集合里的第一个元素
System.out.println(it.first());//-20
//输出集合里的最后一个元素
System.out.println(it.last());//45
//输出小于10的子集,不包含10
System.out.println(it.headSet(10));//[-20, -8, -1]
//输出大于10，包含10
System.out.println(it.tailSet(10));//[10, 15, 45]
//输出一个范围(大于等于-8，小于45)
System.out.println(it.subSet(-8,45));//[-8, -1, 10, 15]
}
}
五、List集合
1.List集合代表一个有序，可重复的集合，集合中每个元素都有对应的顺序索引 0 1 2 .......
2.通过get()方法一般使用for循环来遍历集合
ArrayList集合package day05;
import java.util.ArrayList;
//list接口
public class Test1 {
public static void main(String[] args) {
ArrayList list = new ArrayList<>();
list.add("斗罗大陆");
list.add("吞噬星空");
list.add("斗破苍穹");
System.out.println(list);//[斗罗大陆, 吞噬星空, 斗破苍穹]
//在第二个元素中插入不良人
list.add(1,"不良人");
System.out.println(list);//[斗罗大陆, 不良人, 吞噬星空, 斗破苍穹]
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
//移除第一个
list.remove(0);
System.out.println(list);//[不良人, 吞噬星空, 斗破苍穹]
//输出指定元素的位置indexOf()
System.out.println(list.indexOf("不良人"));//0
//将第二个元素替换称为xxxx
list.set(1,"画江湖系列");
System.out.println(list);//[不良人, 画江湖系列, 斗破苍穹]
//截取子集和(不包含右区间)
System.out.println(list.subList(1,2));
}
}
linkedList集合
import java.util.linkedList;
public class Test7 {
public static void main(String[] args){
linkedList linkedList = new linkedList();
//add方法插入元素默认是在链表的尾部追加元素
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
linkedList.add("E");
linkedList.add("G");
//头部插入，速度极快，因为不需要元素的后移，只需要链接节点
linkedList.addFirst("a");
//尾部插入和头部插入一样，速度极快
linkedList.addLast("i");
//中间插入，通过循环（从头部和尾部开始，看离头部和尾部哪个近）找第五个节点，插入元素，不涉及前移和后移
linkedList.add(5,"j");
for (int i = 0; i < linkedList.size(); i++) {
//linkedList虽然支持get（）方法取数据，但是linkedList不是基于下标，而是循环迭代，性能慢
System.out.println(linkedList.get(i));
}
}
}
主义的是，对于linkesList集合应该采用Iterator来遍历
Array与ArrayList的区别
| Array | ArrayList | |
| 容量 | 数组容器在数组初始化时就已经定死 | 在添加元素的时候，会判断容量是否到达临界值,如果到达临界值就会扩容,判断依据是size+1 / length > 0,扩容策略是每次扩容1.5倍的容量 |
| 存储的数据类型 | 单个数组可以存储的数据类型是单一的 | 单个ArrayList可以存储任意类型的数据,因为其底层是Object类型的数组。 |
ArrayList和linkedList区别
| ArrayList | linkedList | |
| 底层数据结构 | Object类型的数组 | 双向指针链表 |
| 读的速度(从容器中取出指定位置的元素) | 基于下标快速定位到元素,极快 | 需要通过循环找到指定位置的元素,慢 |
| 写的速度 | 1.尾部添加的速度极快,通过下标快速找到,然后插入 2.头部和中间插入速度较慢,因为设计插入后,后面的元素要后移 | 1.首尾插入的速度都极快 2.中间插入的速度快于ArrayList,因为他没有元素后移的操作,只是找到元素后改变双向指针即可 |
ArrayList（不同步的）
* 原因：底层是数组，数组有下标，通过下标可以随机访问
ArrayList arrayList1 = new ArrayList();//无参：默认初始容量是ArrayList arrayList2= new ArrayList(100); //有参：默认初始容量是100
linkedList（不同步的）
数组转 List：使用 Arrays. asList(array) 进行转换。
数组转字符串Arrays.toString(array)
List 转数组：使用 List 自带的 toArray() 方法。
package day05;
import java.util.ArrayList;
import java.util.Arrays;
public class Test2 {
public static void main(String[] args) {
ArrayList list = new ArrayList<>();
list.add("123");
list.add("456");
System.out.println(list.toArray());
String[] s={"123","456","789"};
//数组转字符串
System.out.println(Arrays.toString(s));//[123, 456, 789]
//数组转list
System.out.println(Arrays.asList(s));//[123, 456, 789]
}
}
多线程场景下如何使用 ArrayList？
ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样：
package day05;
import java.lang.reflect.Array;
import java.util.*;
public class Test2 {
public static void main(String[] args) {
ArrayList list = new ArrayList<>();
list.add("123");
list.add("456");
System.out.println(list.toArray());
String[] s={"123","456","789"};
//数组转字符串
System.out.println(Arrays.toString(s));//[123, 456, 789]
//数组转list
System.out.println(Arrays.asList(s));//[123, 456, 789]
//list是线程不安全的，使用collections提供的synchronizedList方法来实现线程安全
List list1 = Collections.synchronizedList(list);
list1.add("love");
list1.add("lpf");
Iterator iterator=list1.iterator();
while(iterator.hasNext()){
String item=(String)iterator.next();
System.out.println(item);
}
}
}
六、Map集合
1.Map集合用于保存具有映射关系的数据，因此Map集合里保存着两组值，一组用于保存Map里的key,另一组用于保存Map里的value，key和value都可以是任意的引用数据类型，而且Map里的key是不允许重复的
2.key和value之间存在着单项的一对一的关系
3.所有的key放在一块组成了Set(key是没有顺序的而且不能重复)
4.Map中包含了一个内部类Entry,该类封装了一个key-value对，包含如下三个方法
1)Object getKey():返回Entry包含的key值
2）Object getValue()返回Entry包含的value值
3）Object setValue(V value)设置改Entry里包含的value值并返回新设置的value值
HashMap 的实现原理？HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
HashMap的数据结构： 在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
HashMap 基于 Hash 算法实现的
当我们往Hashmap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中
获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。
需要注意Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)
package day05;
import java.util.HashMap;
import java.util.Map;
//Map集合
public class Test3 {
public static void main(String[] args) {
Map map =new HashMap<>();
map.put("斗罗大陆",6);
map.put("不良人",4);
map.put("星程变",7);
//key不允许重复但value可以
map.put("斗破苍穹",7);
map.put("斗罗大陆",5);//输出value==6
System.out.println(map);//{星程变=7, 斗罗大陆=5, 斗破苍穹=7, 不良人=4}
//containsKey查询Map中是否包含指定的key
System.out.println(map.containsKey("斗罗大陆"));//true
//containsValue查询Map中是否包含指定的value
System.out.println(map.containsValue(5));//true
//keySet()返回该Map中所有的key组成的集合
for(String item:map.keySet()){
//Map提供的get(key)来获取指定key对应的value
System.out.println("key:"+item+"-->value:"+map.get(item));
}
}
}
JDK1.8之前
JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
JDK1.8之后
相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
HashMap的扩容操作是怎么实现的？①.在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容；
②.每次扩展的时候，都是扩展2倍；
③.扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。
在putVal()中，我们看到在这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上
HashMap是怎么解决哈希冲突的？答：在解决这个问题之前，我们首先需要知道什么是哈希冲突，而在了解哈希冲突之前我们还要知道什么是哈希才行；
什么是哈希？
Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
什么是哈希冲突？
当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。
HashMap的数据结构
在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突：
总结简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：
1. 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
2. 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
3.引入红黑树进一步降低遍历的时间复杂度，使得遍历更快
HashMap 与 HashTable 有什么区别？线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。
初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。
1.对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。
2.treeMap:就是一个红黑树数据结构，每个key-value对即作为红黑树的节点，treeMap存储key-value对时需要根据key对节点进行排序
Collection 和 Collections 有什么区别？
java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。
Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。
TreeMap 和 TreeSet 在排序时如何比较元素？Collections 工具类中的 sort()方法如何比较元素？TreeSet 要求存放的对象所属的类必须实现 Comparable 接口，该接口提供了比较元素的 compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。
Collections 工具类的 sort 方法有两种重载的形式，
第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较；
第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator 接口的子类型（需要重写 compare 方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java 中对函数式编程的支持）
