集合进阶-20210912

集合基础

集合创建：

int[] arr = new int[3];

int [] = {};

Student[] stu = new Student[3];

赋值操作：

arr[0] = stu1; 

arr[1] = stu2; 

arr[2] = stu3; 

ArrayList集合

java.util

List接口的大小可变数组的实现

ArrayList构造方法：

1. ArrayList()   构造一个初始容量为10的空列表。
2. ArrayList(Collection<? extends E> c)  构造一个包含指定collection的元素的列表，这些元素是按照该collection的迭代器返回他们的顺序排列。
3. ArrayList(int initialCapacity)   构造一个具有指定初始容量的空列表

ArrayList常用的成员方法

1. remove(Object o)  删除指定的元素，返回删除是否成功

2. remove(int index)  删除指定索引处的元素，返回被删除的元素

3. set(int intdex, E element)    修改指定索引处的元素，返回被修改的元素

4. get(int index)  返回指定索引处的元素

5. size()  返回集合中的元素个数

遍历集合的通用格式

for(int i=0;i<集合对象.size();i++){

		集合对象.get(i);   // 就是指定索引处的元素

}

单列集合

List集合

Set集合

Set集合概述和特点

特点：

• 可以去除重复
• 存取顺序不一致
• 没有带索引的方法，不能使用普通for循环来遍历，也不能通过索引来操作元素

什么是存取顺序？

就是你存储的时候放的顺序是张三、李四、王五

但是你取出来的顺序就不一定了

Set集合的基本使用

public class MySet {
    public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("aaa");
        set.add("aaa");
        set.add("bbb");
        set.add("ccc");
        //迭代器
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            String element = it.next();
            System.out.println(element);
        }
        //增强for
        for (String s : set) {
            System.out.println(s);
        }
        //aaa
        //bbb
        //ccc
    }
}

TreeSet集合

TreeSet集合特点

• 不包含重复元素的集合
• 没有带索引的方法
• 可以将元素按照规则进行排序

public class MySet2 {
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet();
        set.add(8);
        set.add(2);
        set.add(6);
        set.add(3);
        set.add(2);
        for (Integer e : set) {
            System.out.println(e);
        }
        System.out.println(set);
    }
}
 	//2
    // 3
    // 6
    // 8
    // [2, 3, 6, 8]

注意：要想使用TreeSet集合必须制定排序规则

自然排序Comparable使用

该接口对实现它的每个类的对象强加一个整体排序，这个排序被称为类的自然排序

实现此接口的对象列表（和数组）可以自动排序Collections.sort（和Arrays.sort）

比较器Comparator

• TreeSet带参构造方法使用的是比较器排序对元素进行排序
• 比较器排序，就是让集合构造方法接收Comparator的实现类对象，重写compare(T o1,T o2)方法
• 重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写

数据结构-树

二叉树

度：每个节点的子节点个数

二叉树中任意一个子节点的度要小于等于2

树的高度就是树的层数

二叉查找树

每个节点的左左子节点都比自己小，右子节点都比自己大

二叉查找树又称二叉排序树或者二叉搜索树

特点：

1. 每个节点上最多有两个子节点
2. 每个节点的左子节点都小于自己
3. 每个节点的右子节点都大于自己

平衡二叉树

• 二叉树左右两子树高度差不超多1
• 任意节点的左右两子树都是一颗平衡二叉树

左旋、右旋

触发机制：当添加一个节点后，该树不是一颗平衡二叉树

左左、左右、右右、右左

左左：当根节点的左子树的左子树有节点插入，导致二叉树不平衡

左右：当根节点的左子树的右子树有节点插入，导致二叉树不平衡

右右：当根节点的右子树的右子树有节点插入，导致二叉树不平衡

右左：当根节点的右子树的左子树有节点插入，导致二叉树不平衡

红黑树

红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构

又被称为二叉平衡B树，是一种特殊的二叉查找树，红黑树每个节点上都有存储位表示节点的颜色

每个节点可以是红或者黑，红黑树不是高度平衡的，它的平衡是通过红黑规则来实现的

红黑树和平衡二叉树的区别：

平衡二叉树

平衡二叉树是高度平衡的

条件：当左右子树高度差超过1时，旋转

红黑树

红黑树是一个二叉查找树，但是不是高度平衡的

条件：自己的红黑规则，旋转

红黑规则

1. 每个节点都是红色的或者黑色的
2. 根节点必须是黑色
3. 如果一个节点没有子节点或者父节点，该节点相应的指针属性为Nil，这些Nil节点视为叶子节点，每个叶节点都是黑色的
4. 如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
5. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

添加节点时，默认颜色为红色添加效率高

小技巧：

1. 其父节点是黑色，不需要做任何操作
2. 其父节点是红色，叔叔节点也是红色
   1. 将父节点设为黑色，叔叔节点设为黑色
   2. 将祖父节点设为红色
   3. 如果祖父节点为根节点，则将根节点再次变为黑色
3. 其父节点是红色，叔叔节点是黑色
   1. 将父节点设为黑色
   2. 将祖父节点设为红色
   3. 以祖父节点为支点进行旋转

总结：

HashSet

基本使用

HashSet<String> set = new HashSet<>();
set.add("hello");
set.add("world");
set.add("java");
set.add("java");
set.add("java");
//迭代器
Iterator<String> it = set.iterator();
while (it.hasNext()){
    String next = it.next();
    System.out.println(next);
}
System.out.println("-----------------------------");
//增强for
for(String s : set){
    System.out.println(s);
}
//result
world
java
hello
-----------------------------
world
java
hello

哈希值

HashSet底层是hash表结构的，哈希表里面有个重要属性hash值

哈希值：是JDK根据对象的地址或者属性值，算出来的int类型整数

Object类中有一个方法可以获取hash值

public int hashCode() ：根据对象的地址值计算出来的hash值

对象的hash值特点

• 如果没有重写hashCode方法，那么是根据对象的地址值计算的hash值

  同一个对象调用多次hashCode方法计算出来的hash值是一样的

  不同对象的hash值是不一样的

• 如果重写了hashCode方法，一般是通过对象的属性值计算出hash值

  如果不同对象的属性值是一样的，那么计算出来的hash值也是一样的

常见的数据结构哈希表

HashSet1.7版本原理解析

HashSet<String> hm = new HashSet<>();

1. 创建一个默认长度为16，默认加载因子为0.75的数组，数组名table
2. 根据元素的哈希值和数组的长度计算出应存入的位置
3. 判断当前位置是否为null，如果是null就直接存入
4. 如果存入的位置不是null，表示有元素，则调用equals方法比较属性值
5. 如果一样则不存，如果不一样则存入数组，老元素挂在新元素下面

HashSet1.8版本原理解析

为什么要变？

因为原来是链表结构，需要调用equals方法依次去比较，效率比较低

当长度为8的时候会自动转为红黑树

底层结构：哈希表 （数组、链表、红黑树的结合体）

当挂在下面的元素过多不宜添加，也不利于查询，所以在8以后转为红黑树

结论：

如果hashSet集合要存储自定义对象，那么必须重写hashCode和equals方法

小结：

Set集合：

1. 无序
2. 无索引
3. 不可以重复

Map

单列集合一次只能存一个元素

双列集合每一次可以添加两个元素，也可以说是一对数据

左边一列称为键，是唯一的，不能重复的。右边一列称为值，是可以重复的。

一个键和一个值我们称为键值对，键值对对象，或者是Entry对象

interface Map<K,V>

• k:键的数据类型；v：值的数据类型

• 键不能重复，值可以重复

• 键和值是一一对应的关系，每个键只能找到自己对应的值

• （键+值）这个整体我们称为键值对，键值对对象，或者是Entry对象

map的基本使用

public static void main(String[] args) {
    Map<String,String> map = new HashMap<>();
    map.put("xaiomei","22");
    map.put("xiaohei","25");
    map.put("dapan","23");
    System.out.println(map);
}
//{xiaohei=25, dapan=23, xaiomei=22}

常用方法

1. 添加元素put方法

   map.put("xaiomei","22");
   map.put("xiaohei","25");

   注意：

   如果要添加的键不存在，那么会把键值对都添加到集合中

   如果要添加的键是存在的，那么会覆盖原先的值，把原先值当做返回值进行返回

2. remove方法 根据键删除键值对整体 有个返回值，返回的是删除键值对的值

   Map<String,String> map = new HashMap<>();
   map.put("xaiomei","22");
   map.put("xiaohei","25");
   map.put("dapan","23");
   String dapan = map.remove("dapan");
   System.out.println(dapan);
   System.out.println(map);
   //
   23
   {xiaohei=25, xaiomei=22}
   

3. void clear() 移除所有的键值对元素

4. boolean containsKey(Object key) 判断集合是否包含指定的键

   Map<String,String> map = new HashMap<>();
   map.put("xaiomei","22");
   map.put("xiaohei","25");
   map.put("dapan","23");
   System.out.println(xaiomei);
   //true
   

5. boolean containsValue(Object key) 判断集合是否包含指定的值

   Map<String,String> map = new HashMap<>();
   map.put("xaiomei","22");
   map.put("xiaohei","25");
   map.put("dapan","23");
   boolean b = map.containsValue("22");
   boolean c = map.containsValue("55");
   System.out.println(b);//true
   System.out.println(c);//false
   

6. boolean isEmpty(); 判断集合是否为空

   Map<String,String> map = new HashMap<>();
   map.put("xaiomei","22");
   map.put("xiaohei","25");
   map.put("dapan","23");
   boolean empty = map.isEmpty();
   System.out.println(empty);//false
   map.clear();
   System.out.println(empty);//true
   

7. int size(); 集合的长度，也就是集合中键值对的个数

   Map<String,String> map = new HashMap<>();
   map.put("xaiomei","22");
   map.put("xiaohei","25");
   map.put("dapan","23");
   int size = map.size();
   System.out.println(size);//3
   

遍历map集合

第一种方式：键+值

public static void main(String[] args) {
    Map<String,String> map = new HashMap<>();
    //创建集合并添加元素
    map.put("1号丈夫","1号妻子");
    map.put("2号丈夫","2号妻子");
    map.put("3号丈夫","3号妻子");
    map.put("4号丈夫","4号妻子");
    map.put("5号丈夫","5号妻子");
    //获取到所有的键
    Set<String> keys = map.keySet();
    //遍历set集合获取到每一个值
    for (String key : keys) {
        //通过每一个key来获取对应的值
        String value = map.get(key);
        System.out.println(key + "----" + value);
    }
}
//结果
1号丈夫----1号妻子
2号丈夫----2号妻子
5号丈夫----5号妻子
4号丈夫----4号妻子
3号丈夫----3号妻子

第二种方式：键值对Entry

public static void main(String[] args) {
    Map<String,String> map = new HashMap<>();
    //创建集合并添加元素
    map.put("1号丈夫","1号妻子");
    map.put("2号丈夫","2号妻子");
    map.put("3号丈夫","3号妻子");
    map.put("4号丈夫","4号妻子");
    map.put("5号丈夫","5号妻子");
   //获取到所有键值对对象
    Set<Map.Entry<String, String>> entries = map.entrySet();
    for (Map.Entry<String, String> entry : entries) {
        System.out.println(entry.getKey() + "----" + entry.getValue());
    }
}
//结果
1号丈夫----1号妻子
2号丈夫----2号妻子
5号丈夫----5号妻子
4号丈夫----4号妻子
3号丈夫----3号妻子

Hashmap

原理解析

底层：首先创建了一个长度为16默认加载因子为0.75的数组，0.75是扩容时机，当16*0.75=12时，数组就要扩容为原先的两倍32

添加数据是通过put方法来添加的，是通过Entry对象来放键值对

通过hashCode方法计算键的哈希值，和值无关

小结：

第三种遍历方式：forEach方法

public static void main(String[] args) {
    Map<String,String> map = new HashMap<>();
    //创建集合并添加元素
    map.put("1号丈夫","1号妻子");
    map.put("2号丈夫","2号妻子");
    map.put("3号丈夫","3号妻子");
    map.put("4号丈夫","4号妻子");
    map.put("5号丈夫","5号妻子");
   //获取到所有键值对对象
   map.forEach((String key,String value)->{
       System.out.println(key + "----" + value);
   });
}
//结果
1号丈夫----1号妻子
2号丈夫----2号妻子
5号丈夫----5号妻子
4号丈夫----4号妻子
3号丈夫----3号妻子

TreeMap

可变参数

可变参数：就是方法中形参的个数是可以变化的

• 格式：修饰符 返回值类型 方法名（数据类型...变量名）{ }
• 范例：public static int sum(int..a){}

可变参数注意事项

• 这里的变量其实是一个数组
• 如果一个方法有多个参数，包含可变参数，可变参数要放在最后

创建不可变集合

作用：可以实现集合的批量添加

注意：是JDK9才引入的of方法

List<String>  list = List.of("a","b","c","d");

ArrayList<String>  list2 = new ArrayList<>( List.of("a","b","c","d"));//[a,b,c,d]

方法解读：

1. 首先是通过List.of()方法来创建一个不可变集合，of方法的形参就是一个可变参数
2. 再创建一个Arraylist集合，并把这些不可变集合中的所有数据，都添加到Arraylist中

注意：

在使用set集合时，传递的参数中，不能存在重复的元素

集合进阶-20210912

原文：https://www.cnblogs.com/he-peng/p/collection_20210912.html