集合笔记部分（下）
LinkHashSet（了解）
唯一、有次序（存储顺序），没有下标
在HashSet的基础上额外添加一个链表，底层基于LinkedHashMap
性能上比HashSet低
使用场景不多(浏览记录)
LinkedHashSet set = new LinkedHashSet();
set.add("hello");
set.add("abc");
set.add("hello");
set.add("bbb");
System.out.println(set);//[hello, abc, bbb] 唯一、有次序（存储顺序）
Map接口
特征：
1：）Map存储的是Key/value键值对，key可以是任意的数据类型，实际开发中key一般是String类型，value可以是任意数据类型.
2：）key唯一，value可以重复
3：）如果往Map中添加新的数据的key已经存在，那么新的数据的value会覆盖该key对应的之前的value值
4：）Map里面的key可以为null,但是只能有一个，多个的时候，后面的会覆盖前面的
实现类
HashMap(线程不安全的), HashTable(老版本，基本不用，线程安全)
TreeMap,
Properties(配置文件，key/value都是String类型)
HashMap
数据结构：数组+链表/红黑树（哈希表）
JDK1.7及之前：数组+链表
JDK1.8及之后，引入红黑树，提高查询效率，数组+链表/红黑树
面试题：三大集合的特征
（1）List：是一个有序，元素可以重复，元素有下标的集合。常用的实现类有 ArrayList、LinkedList等。
（2）Set：是一个无序，不可以存储重复元素，元素没有下标，允许存入的元素为null但是只能存在一个，Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。
（3）Map是一个键值对的集合，存储键、值和之间的映射。 Key无序，唯一；value 不要求有序，允许重复。key,value可以是任意数据类型，key一般为String类型。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。Map 的常用实现类：HashMap、TreeMap等。
构造方法
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-n7hsw274-1660188869748)(D:\飞思实训三\博客\我的\7.集合\assets\image-20220808092035662.png)]
HashMap hashMap = new HashMap();//默认初始容量16，加载因子0.75
HashMap hashMap1 = new HashMap(25);//指定初始容量（不是说长度就是25） 容量是2的幂次方，传入容量，调用tableSizeFor方法，经过计算，得出32 不设置加载因子
System.out.println(tableSizeFor(25));//32
static int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : n + 1;
}
容量：
数组的长度，设置为2的幂次方 11–> 16 5–>8
加载因子：
扩容的指标， 扩容的阈值 = 容量**加载因子 例如 16* * 0.75 = 12，也就是说长度为16的数组，当使用到第12个时，自动扩容
例如，1000个元素 1024*0.75 = 768（数组有768个位置已经有元素时扩容）
面试题：为什么默认的加载因子是0.75？
为什么需要加载因子?
HashMap的底层是一个哈希表（散列表），存储的是键值对，需要通过计算得出元素在哈希表中存放的位置。一般的数据结构要么是插入快要么是查询快，而HashMap是一种一种插入慢、查询快的数据结构。
这种数据结构容易产生两种问题：
1：如果空间的利用率高，那么经过计算之后得出的新元素的存储位置可能已经有元素了（哈希冲突）
2：如果为了降低哈希冲突发生的概率而去增大数组的容量，就会导致空间的利用率不高。
加载因子表示的是Hash表中元素的填满程度。加载因子=填入表中的元素个数/散列表的长度。
加载因子越大，填满的元素越多，空间的利用率越高，因此发生哈希冲突的概率也会增大；加载因子越小，填满的元素越少，发生冲突的概率也会降低，但是会浪费更多的空间,而且发生扩容的次数也会增多
那么如何在“哈希冲突”与“空间利用率”之间达到相对的平衡
可以将冲突元素的位置构造成一个链表，如果添加的元素哈希地址与表上的元素冲突了，就把新元素放在这个链表上。（链地址法）
这种做法的优点是：
1.处理冲突的方式简单，没有元素堆集的现象，平均查找长度较短
2.由于各链表的结点空间是动态申请的，所以它很适合不知道具体的表长时来使用
3.删除节点操作简单，只要删除链表上的相应节点即可
缺点：需要额外的存储空间
由于HashMap的底层是由数组+链表/红黑树构成的，当链表的长度大于8时，判断数组的长度是否大于64，如果大于，这个链表就转换成红黑树
为什么默认的加载因子是0.75？而不是0.8， 0.6？
我们知道，HashMap的底层是哈希表，而解决冲突的方法是链地址法。
HashMap的初始容量大小默认是16，为了减少冲突发生的概率，当HashMap的数组长度到达一个临界值的时候，就会触发扩容，把所有元素rehash之后再放在扩容后的容器中，这是一个相当耗时的操作。
而这个临界值就是由加载因子和当前容器的容量大小来确定的：
临界阈值 = 容量*加载因子
即默认情况下是16x0.75=12时，就会触发扩容操作。
那么为什么选择了0.75作为HashMap的加载因子呢？这个跟一个统计学里很重要的原理——泊松分布有关（这里不细说，感兴趣的可以自行百度一下）。
总结就是：HashMap中除了哈希算法之外，有两个参数影响了性能：初始容量和加载因子。将常数0.5作为参数，加载因子0.75作为一个条件代入泊松分布来计算后可以最大限度的减少扩容的操作次数。因此，选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择。
常用方法
添加元素：put(key,value) 如果key不存在，添加元素；key存在，覆盖value
删除元素：remove(Object key) 根据key删除，返回被删除元素的value值
清空：clear()
查询：get(Object key) 根据key得到value ,如果key不存在，返回null
V getOrDefault(Object key,V defaultValue)//如果key不存在, 返回你设置defaultValue
判断key，value是否存在
boolean containsKey(Object key)
boolean containsValue(Object value)
(重点)遍历Map:
Set keySet()//获取Map所有的key
Collection values()//获取Map所有的value
Set entrySet()//得到Map所有的entry对象（键值对）(JDK1.7及之前–Entry Jdk1.8及之后Node)
1.第一种: 得到hashMap所有的key集合: ketSet(), 遍历key的set集合, 得到value
//第一种遍历方式
Set keys = map.keySet();
//简写forEach循环
for(Object key:keys){
//根据key获取value
Object value = map.get(key);
System.out.println("key:"+key+"-value:"+value);
}
//使用迭代器
Set keys = map.keySet();
Iterator iterator = keys.iterator();
while(iterator.hasNext()){
Object key = iterator.next();
Object val = map.get(key);
}
2.第二种: 得到map所有value的集合, 但是, 无法通过value得到key
Collection values = map.values();
//简写forEach循环
for(Object value:values){
//获取value
System.out.println("-value:"+value);
}
//使用迭代器
Collection values = map.values();
Iterator iterator = values.iterator();
while(iterator.hasNext()){
Object value = iterator.next();
}
得到map的所有key/value 的set集合, entrySet(); 开发中最常用最推荐的方式
//Entry: key/value对
Set entrys = map.entrySet();
//使用迭代器
//简写forEach循环
for(Object entryObj : entrys){
Map.Entry entry = (Map.Entry)entryObj;
//获取key, value
Object key = entry.getKey();
Object value = entry.getValue();
System.out.println("key:"+key+"-value:"+value);
}
//迭代器方式
Set entrySet = map.entrySet();
Iterator iterator = entrySet.iterator();
while(iterator.hasNext()){
Map.Entry entry = (Map.Entry)iterator.next();
Object key = entry.getKey();
Object value = entry.getValue();
}
HashMap原理（源码8-8下午）
jdk1.8: 数组+链表/红黑树
※ 如果某个桶的链表的长度>=8 ,进行转换红黑树, 前提是先判断（数组）table[]的长度 是否>=64,如果大于, 进行红黑树转换, table长度 < 64, 进行扩容, 每次扩容2倍
hashMap什么时候扩容？
达到扩容阈值时 即容量 * 加载因子
put()方法
1：）底层调用key的hashCode()方法得到一个hash值
hash计算过程：key的hashCode的低16位与hashCode的高16位异或
※ 目的：减少hash碰撞（ 例如key不一样, 但 是hashcode值一样, 或者key不一样,hashCode值不一样,但是计算得到下标一样，减小上述两种情况的发生的概率）让插入的元素尽量散列在不同的桶上
- key为null的hash值为0
- table数组 在第一次添加元素的时候进行初始化, 调用resize()方法
- 每次扩容,扩大为原来的的2倍 newCap = oldCap << 1;（相当于oldCap*2的一次方）
2：）通过哈希表函数/哈希算法，将hash值转换成数组的下标. hash%容量 (容量必须是2的幂次方)
3：）下标位置上如果没有任何元素，就创建一个新Node节点,并添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着key和链表上每个节点的key进行equals()比较。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。
重要的属性:
Node[] table; //数组
int threshold; //扩容阈值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//第一次的数组初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 要求: hashMap的容量必须2的幂次方
// (n - 1) & hash 等价于: hash % n 得到位于数组那个下标, 位于哪个桶
// tab[14] == null 这个桶没有元素
if ((p = tab[i = (n - 1) & hash]) == null)
// 把新的key/value变成node节点对象, 添加到桶上
tab[i] = newNode(hash, key, value, null);
// 这个桶上有元素
else {
Node<K,V> e; K k;
//桶上的元素, 桶上有一个元素key与添加的新的元素key相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //把找到相同key的元素 赋值给e
//如果桶上的第一个元素key与添加的key不一样
// 桶是否是红黑树
else if (p instanceof TreeNode)
//如果是红黑树, 调用putTreeVal() 找
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果桶上的第一个元素key与添加的key不一样
//桶是单向链表
for (int binCount = 0; ; ++binCount) {
//循环链表, 判断链表上是否有key相同
//如果下一个元素为空, 到了链表的末尾
if ((e = p.next) == null) {
// 把新的key/value 添加链表的末尾 jdk1.8 尾插入 jdk1.7: 头插入
p.next = newNode(hash, key, value, null);
//当链表的长度=8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//准备进行红黑树转换, 先判断数组长度>=64 满足,进行红黑树转换,如果不满足, 进行扩容
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//覆盖value
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
HashMap的tables数组什么时候初始化?
第一次添加元素的时候，调用resize()方法（不是在构造方法）
面试：hashMap的容量为什么一定要是2的幂次方
泛型
泛型的使用
使用jdk已经定义好的泛型类或泛型方法 例如: 集合类都是jdk已经定义好的泛型类
注意：
1：）泛型没有继承关系，前面的泛型变量的值必须与后面的一样 ArrayList list = new ArrayList(); 这种是错误的
2：）泛型可以限制集合只能存储指定类型的数据，但是泛型赋值数据类型只能是类类型,不能是基本数据类型
3：）集合使用泛型 获取元素不需要向下转型了
4：) Map集合可以指定两个泛型； List不行，只能指定一个
5：）泛型变量没有赋值: 就是Object
//List<String> list = new ArrayList<String>();
List<String> list = new ArrayList<>();//JDK1.7之后可以省略后面的<>里的数据类型，但是<>不能省略
list.add("hello");
list.add("word");
String s = list.get(1);//使用了泛型 不需要向下转型
//Object o = list.get(1);//没有使用泛型
//map的泛型使用
Map<String,Integer> map = new HashMap<>();
map.put("key1",1);
map.put("key2",2);
map.put("key3",3);
Integer integer = map.get("key1");
Set<Map.Entry<String, Integer>> entries = map.entrySet();//set集合也需要指定泛型 默认ObjectMap.Entry<Object,Object>
for (Map.Entry<String,Integer> entry:entries){//Entry对象也需要指定泛型
String key = entry.getKey();
Integer value = entry.getValue();
}
泛型的定义
定义泛型类或泛型接口
泛型变量可以在类的 构造方法,非静态方法的参数 ，非静态方法的返回值，属性的数据类型使用，注意：不能在静态方法上使用
public class Demo2<T> {
//存储的数据
T stu;//泛型变量可以在属性上用
public void fun1(T t){泛型变量可以作为参数
}
public T fun2(T t){//泛型变量可以在非静态方法上用
return t;
}
/*public static T fun3(){//静态方法不能使用类泛型变量
return null;
}*/
public static <E> E fun3(E e){//静态方法使用泛型，需要在静态方法上自定义泛型类型
return e;
}
}
// <E> 声明一个泛型变量
// E 使用这个泛型变量
使用泛型类
Demo2<String> demo2 = new Demo2<>();//T 泛型类泛型变量赋值方法一：在创建对象时赋值
demo2.fun2("aa");//T
Demo2.fun3(1);//E 静态方法的泛型类型由传入的参数类型确定
给泛型类的泛型变量赋值
方法一：在创建对象时赋值
public class Page<T> {}
Page<String> page = new Page<>();
方法二：子类继承这个泛型类, 给泛型变量赋值
public class SubPage extends Page<Integer> {}
方法三：如果子类不清楚给父类的泛型变量赋什么类型 那就把自己变成一个泛型类,
public class SubPage2<T> extends Page<T>{}
SubPage2<String> subPage2 = new SubPage2<>();
泛型通配符 ？ 可以是任意类型
定义一个方法, 接收一个泛型类类型的变量, 不确定泛型类的泛型变量类型, 这个参数不能是类<Object>,因为泛型没有继承, 所以要使用?通配符
注意：
1：）通配符只能作为方法的参数使用
2：）使用通配符的泛型变量, 只能只读的
/**
* 定义一个方法,能遍历所有类型的ArrayList集合
* 这时候我们不知道ArrayList集合使用什么数据类型,可以泛型的通配符?来接收数据类型
*/
public static void printArray(ArrayList<?> list){
Iterator<?> iterator = list.iterator();
while(iterator.hasNext()){
Object obj = iterator.next();
System.out.println(obj);
}
如何限制通配符？传入的数据类型
上限
- 格式:
类型名称<? extends 类> 对象名称 - 意义: 只能接收该类型及其子类
public static void fun1(List<? extends Number> list){}
下限
- 格式:
类型名称<? super 类> 对象名称 - 意义:只能接收该类型及其父类类型
public static void fun2(List<? super Number> list){}
public static void fun1(List<? extends Number> list){}
public static void fun2(List<? super Number> list){}
public static void main(String[] args) {
List<Integer> list1 = new ArrayList<>();
List<String> list2 = new ArrayList<>();
List<Number> list3 = new ArrayList<>();
List<Object> list4 = new ArrayList<>();
fun1(list1);//只能接收Number及其子类
fun1(list2); //String报错
fun1(list3);
fun1(list4); //Object报错
fun2(list1); //报错
fun2(list2); //报错
fun2(list3);
fun2(list4);
}
集合工具类Collections 与Arrays
Collections: 集合的工具类
Arrays: 数组的工具类
位于java.util包中，方法都是静态的
可变参数
格式：数据类型… 变量名 （本质就是一个数组）
作用：替换数组，方便调用
限制：
一个方法只能有一个可变参数，并且可变参数要位于参数列表的最后面
//数组作为参数
public int add(int[] arr){
//遍历数组
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
//使用可变参数作为参数
public int add1(int... num){
//遍历数组
int sum = 0;
for (int i = 0; i < num.length; i++) {
sum += num[i];
}
return sum;
}
//参数需要传多个数组
public void fun(int[] arr1, String[] arr2,String a）{}
//可变参数 可变参数要位于参数列表的最后面
public void fun1( String arr2,int... arr1）{}
测试：
int[] arr = new int[]{1,2,3,4,5};
System.out.println(new Demo3().add(arr));
//调用可变参数的方法
System.out.println(new Demo3().add1(1,2,3,4,5));//1,2,3,4,5本质上就是转换成了数组
Arrays常用方法
static List asList(T… t)方法 将数组转换为List集合
返回的ArrayList是Arrays内部的ArraysList,是只读的，不可以修改，也就是不能使用List的add() remove() clear()…等方法
Integer arr[] = new Integer[]{1,2,3,4,5};
List<Integer> list = Arrays.asList(arr);
//Arrays.asList(1,2,3,4,5);也可以这样写1,2,3,4,5自动转换成数组
list.add(6);//UnsupportedOperationException 抛出异常，list是只读的
System.out.println(list.get(1));//可以读取
//解决办法
List<Integer> list1 = new ArrayList<>(list);
list1.add(6);//此时可以读写
System.out.println(list1);//[1, 2, 3, 4, 5, 6]
copyOf(旧数组, 新长度) 创建一个新数组, 拷贝旧数组的元素到新数组
arr = Arrays.copyOf(arr,10);
arr[5] =100;
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
fill(数组，值) 给数组的所有元素填充一样的值
Integer[] arr2 = new Integer[10];//null
Arrays.fill(arr2,0);
for (Integer i : arr2) {
System.out.println(i);
}
Collections常用方法
1：）static boolean addAll(Collection<? super T> c, T… elements) //把数组的元素添加到集合
2：）static void reverse(List<?> list) //把List集合的元素反转
3：）static void shuffle(List<?> list) //随机打乱List集合元素的顺序
4：）static <T extends Comparable<? super T>> void sort(List list) //自然排序
5：）static void sort(List list, Comparator<? super T> c) //指定排序
6：）max(集合，new Cpmparator(){}),
Integer arr[] = new Integer[]{1,9,3,7,5,8,1,3};
List<Integer> list = new ArrayList<>();
//把数组的元素添加到集合中
Collections.addAll(list,arr);
System.out.println(list);//[1, 9, 3, 7, 5, 8, 1, 3]
//将集合翻转
Collections.reverse(list);
System.out.println(list);//[3, 1, 8, 5, 7, 3, 9, 1]
//打乱
Collections.shuffle(list);
System.out.println(list);//[5, 8, 3, 3, 7, 1, 9, 1]每次执行的结果都不一样
//排序 默认升序（自然排序）
Collections.sort(list);
System.out.println(list);//[1, 1, 3, 3, 5, 7, 8, 9] 允许重复
//排序 降序
Collections.sort(list, new Comparator<Integer>() {//降序
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
System.out.println(list);//[9, 8, 7, 5, 3, 3, 1, 1]允许重复
//找年龄最大的学生
Student maxAgeStu = Collections.max(stuList, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o1.getAge() - o2.getAge();
}
});
System.out.println(maxAgeStu);
le(list);
System.out.println(list);//[5, 8, 3, 3, 7, 1, 9, 1]每次执行的结果都不一样
//排序 默认升序（自然排序）
Collections.sort(list);
System.out.println(list);//[1, 1, 3, 3, 5, 7, 8, 9] 允许重复
//排序 降序
Collections.sort(list, new Comparator() {//降序
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
System.out.println(list);//[9, 8, 7, 5, 3, 3, 1, 1]允许重复
```java
//找年龄最大的学生
Student maxAgeStu = Collections.max(stuList, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o1.getAge() - o2.getAge();
}
});
System.out.println(maxAgeStu);