Java 集合 学习总结（附代码示例）🏷️

1
==========================Student==========================
2

3
public class Student implements Comparable<Student>{
4
    //定义学生属性
5

6
    //定义名字
7
    String name;
8
    //定义年龄
9
    int age;
10

11
    //定义构造方法
12
    public Student() {
13
    }
14

15
    public Student(String name, int age) {
16
        this.name = name;
17
        this.age = age;
18
    }
19

20
    //定义方法
21

22
    public String getName() {
23
        return name;
24
    }
25

26
    public void setName(String name) {
27
        this.name = name;
28
    }
29

30
    public int getAge() {
31
        return age;
32
    }
33

34
    public void setAge(int age) {
35
        this.age = age;
36
    }
37

38
    //重写方法
39

40
    @Override
41
    public boolean equals(Object o) {
42
        if (o == null || getClass() != o.getClass()) return false;
43
        Student student = (Student) o;
44
        return age == student.age && Objects.equals(name, student.name);
45
    }
46

47
    @Override
48
    public int hashCode() {
49
        return Objects.hash(name, age);
50
    }
51

52
    @Override
53
    public String toString() {
54
        return "Student{" +
55
                "name='" + name + '\'' +
56
                ", age=" + age +
57
                '}';
58
    }
59

60
    /*
61
        方式一：
62
            默认的排序规则/自然排序
63
            Student实现comparable接口，重写里面的抽象方法，再指定比较规则
64
    */
65
    //this：表示当前添加的数据
66
    //o：表示红黑树中存在的数据
67

68
    //返回值
69
    //返回值为正数：表示当前要添加的元素是大的，存右边
70
    //返回值为负数：表示当前要添加的元素是小的，存左边
71
    //返回值为0：表示当前要添加的元素是已存在的，舍弃
72

73
    @Override
74
    public int compareTo(Student o) {
75
        //指定排序的规划
76
        //只看年龄按照从小到大排序
77
        return this.getAge() - o.getAge();
78
        //如果是从大到小那么反过来就行了
79
    }
80
}
81

82

83
==========================test==========================
84

85
public class TreeSetDemo {
86
    static void main() {
87
        /*
88
            需求：创建TreeSet集合，并添加3个学生对象
89
            学生对象属性：            姓名，年龄。            要求按照学生的年龄进行排序            同年龄按照姓名字母排列（暂不考虑中文）            同姓名，同年龄认为是同一个人            方式一：            默认的排序规则/自然排序
90
            Student实现comparable接口，重写里面的抽象方法，再指定比较规则
91
        */
92
        //创建对象
93
        TreeSet<Student> ts = new TreeSet<>();
94
        //添加数据
95
        ts.add(new Student("XiXi",20));
96
        ts.add(new Student("KiXi",23));
97
        ts.add(new Student("WiXi",25));
98
        ts.add(new Student("IiXi",27));
99
        //打印数据
100
        System.out.println(ts);
101
    }
102
}

1
public class TreeSetDemo {
2
    public static void main() {
3
        /*
4
            需求：请自行选择比较器排序和自然排序两种方式；
5
            要求：存入四个字符串，“c”，“ab”，“df”，“qwer”
6
            按照长度排序，如果一样长则按照首字母排序
7
            采取第二种排序方式：比较器排序
8
            如果原本自带的排序方法不满足当前条件，那么可以使用Comparator的实现类更改规则
9
        */
10
        //创建对象(比较器)
11
        //如果嫌长还可以用Lambda表达式
12
        TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
13
            //o1表示插入的元素 o2表示红黑树里的元素
14
            //返回值的规则和第一种排序方式一样
15
            @Override
16
            public int compare(String o1, String o2) {
17
                //按照长度排序，如果长度一样则按照首字母排序(也就是原本自带的排序)
18
                int i = o1.length() - o2.length();
19
                //判断该执行哪种排序
20
                if (i == 0){
21
                    //如果长度一样那么使用原方法排序
22
                    return o1.compareTo(o2);
23
                }
24
                //如果不是一样长那么按照长度大小排序
25
                return i;
26
            }
27
        });
28

29
        //添加元素
30
        ts.add("c");
31
        ts.add("ad");
32
        ts.add("df");
33
        ts.add("qwer");
34

35
        //打印
36
        System.out.println(ts);
37
    }
38
}

1
public class MapDemo1 {
2
    public static void main() {
3
        /*
4
            Map集合的第一种遍历方式
5
            练习一：            利用键找值的方式遍历map集合，要求：装着键的单列集合使用增强for的形式进行遍历
6
            练习二：            利用键找值的方式遍历map集合，要求：装着键的单列集合使用迭代器的形式进行遍历
7
            练习三：            利用键找值的方式遍历map集合，要求：装着键的单列集合使用Lambda表达式的形式进行遍历
8
        */
9
        //利用多态创建对象
10
        Map<String, Integer> map = new HashMap<>();
11

12
        //添加元素
13
        map.put("茜特菈莉", 500);
14
        map.put("芙宁娜", 500);
15
        map.put("桑多涅", 500);
16

17
        //把键存到单列集合中
18
        Set<String> s = map.keySet();
19

20
        //使用迭代器方法遍历
21
        Iterator<String> iterator = s.iterator();
22
        while (iterator.hasNext()) {
23
            String str = iterator.next();
24
            //通过键找到值
25
            int value = map.get(str);
26
            System.out.println(str + "=" + value);
27
        }
28

29
        System.out.println("____________________");
30

31
        //使用增强for遍历
32
        for (String string : s) {
33
            int value = map.get(string);
34
            System.out.println(string + "=" + value);
35
        }
36

37
        System.out.println("____________________");
38

39
        //使用Lambda表达式
40
        s.forEach(new Consumer<String>() {
41
            @Override
42
            public void accept(String string) {
43
                int value = map.get(string);
44
                System.out.println(string + "=" + value);
45
            }
46
        });
47

48
        System.out.println("____________________");
49

50
        //Lambda简化版
51
        s.forEach(string -> {
52
            int value = map.get(string);
53
            System.out.println(string + "=" + value);
54
        });
55
    }
56
}

1
public class MapDemo2 {
2
    public static void main() {
3
        /*
4
            Map集合的第二种遍历方式
5
            练习一：            通过键值对对象进行遍历map集合，要求：装着键值对对象的单列集合使用增强for的形式进行遍历
6
            练习二：            通过键值对对象进行遍历map集合，要求：装着键值对对象的单列集合使用迭代器的形式进行遍历
7
            练习三：            通过键值对对象进行遍历map集合，要求：装着键值对对象的单列集合使用Lambda的形式进行遍历
8
        */
9
        //利用多态创建对象
10
        Map<String, Integer> map = new HashMap<>();
11

12
        //添加元素
13
        map.put("茜特菈莉", 500);
14
        map.put("芙宁娜", 500);
15
        map.put("桑多涅", 500);
16

17
        //把键值对对象存到单列集合中
18
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
19

20
        //使用迭代器方法遍历
21
        Iterator<Map.Entry<String, Integer>> iterator = entries.iterator();
22
        while (iterator.hasNext()) {
23
            //获取每一个键值对对象
24
            Map.Entry<String, Integer> entry = iterator.next();
25
            //用键值对对象获取键跟值
26
            String key = entry.getKey();
27
            Integer value = entry.getValue();
28
            //打印
29
            System.out.println(key + "=" + value);
30
        }
31

32
        System.out.println("____________________");
33

34
        //使用增强for遍历
35
        for (Map.Entry<String, Integer> entry : entries) {
36
            //用键值对对象获取键跟值
37
            String key = entry.getKey();
38
            Integer value = entry.getValue();
39
            //打印
40
            System.out.println(key + "=" + value);
41
        }
42

43
        System.out.println("____________________");
44

45
        //使用Lambda表达式
46
        entries.forEach(new Consumer<Map.Entry<String, Integer>>() {
47
            @Override
48
            public void accept(Map.Entry<String, Integer> stringIntegerEntry) {
49
                //用键值对对象获取键跟值
50
                String key = stringIntegerEntry.getKey();
51
                Integer value = stringIntegerEntry.getValue();
52
                //打印
53
                System.out.println(key + "=" + value);
54
            }
55
        });
56

57
        System.out.println("____________________");
58

59
        //Lambda简化版
60
        entries.forEach(stringIntegerEntry -> {
61
            //用键值对对象获取键跟值
62
            String key = stringIntegerEntry.getKey();
63
            Integer value = stringIntegerEntry.getValue();
64
            //打印
65
            System.out.println(key + "=" + value);
66
        });
67
    }
68
}

1
public class MapDemo3 {
2
    static void main() {
3
        /*
4
            Map集合的第三种遍历方式
5
        */
6
        //利用多态创建对象
7
        Map<String, Integer> map = new HashMap<>();
8

9
        //添加元素
10
        map.put("茜特菈莉", 500);
11
        map.put("芙宁娜", 500);
12
        map.put("桑多涅", 500);
13

14
        //使用Lambda表达式进行遍历
15
        //底层：
16
        //forEach其实就是利用第二种方式进行遍历(增强for),依次得到每一个键跟值
17
        //然后调用accept方法
18
        map.forEach(new BiConsumer<String, Integer>() {
19
            @Override
20
            public void accept(String string, Integer integer) {
21
                //第一个参数是键，第二个参数是值
22
                System.out.println(string + "=" + integer);
23
            }
24
        });
25

26
        System.out.println("___________________________");
27

28
        //Lambda表达式简化版
29
        //第一个参数是键，第二个参数是值
30
        map.forEach((string, integer) -> System.out.println(string + "=" + integer));
31
    }
32
}

1
1.看源码之前需要了解的一些内容
2
Node<K,V>[] table   哈希表结构中数组的名字
3

4
DEFAULT_INITIAL_CAPACITY：   数组默认长度16
5

6
DEFAULT_LOAD_FACTOR：        默认加载因子0.75
7

8
HashMap里面每一个对象包含以下内容：
9
1.1 链表中的键值对对象
10
    包含：
11
        int hash;    //键的哈希值
12
        final K key;    //键
13
        V value;    //值
14
        Node<K,V> next;    //下一个节点的地址值
15
1.2 红黑树中的键值对对象
16
        包含：
17
            int hash;    //键的哈希值
18
            final K key;    //键
19
            V value;    //值
20
            TreeNode<K,V> parent;    //父节点的地址值
21
            TreeNode<K,V> left;    //左子节点的地址值
22
            TreeNode<K,V> right;    //右子节点的地址值
23
            boolean red;    //节点的颜色
24
2.添加元素
25
HashMap<String,Integer> hm = new HashMap<>();
26
hm.put("aaa" , 111);
27
hm.put("bbb" , 222);
28
hm.put("ccc" , 333);
29
hm.put("ddd" , 444);
30
hm.put("eee" , 555);
31

32
添加元素的时候至少考虑三种情况：
33
2.1 数组位置为null
34
2.2 数组位置不为null，键不重复，挂在下面形成链表或者红黑树
35
2.3 数组位置不为null，键重复，元素覆盖
36

37

38

39
//参数一：键
40
//参数二：值
41
//返回值：被覆盖元素的值，如果没有覆盖，返回null
42
public V put(K key, V value) {
43
    return putVal(hash(key), key, value, false, true);
44
}
45

46
//利用键计算出对应的哈希值，再把哈希值进行一些额外的处理
47
//简单理解：返回值就是返回键的哈希值
48
static final int hash(Object key) {
49
    int h;
50
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
51
}
52

53
//参数一：键的哈希值
54
//参数二：键
55
//参数三：值
56
//参数四：如果键重复了是否保留
57
//    true，表示老元素的值保留，不会覆盖
58
//    false，表示老元素的值不保留，会进行覆盖
59
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
60
    //定义一个局部变量，用来记录哈希表中数组的地址值。
61
    Node<K,V>[] tab;
62

63
    //临时的第三方变量，用来记录键值对对象的地址值
64
    Node<K,V> p;
65

66
    //表示当前数组的长度
67
    int n;
68

69
    //表示索引
70
    int i;
71

72
    //把哈希表中数组的地址值，赋值给局部变量tab
73
    tab = table;
74

75
    if (tab == null || (n = tab.length) == 0){
76
        //1.如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组
77
        //2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件
78
            //如果没有达到扩容条件，底层不会做任何操作
79
            //如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中
80
        tab = resize();
81
        //表示把当前数组的长度赋值给n
82
        n = tab.length;
83
    }
84

85
    //拿着数组的长度跟键的哈希值进行计算，计算出当前键值对对象，在数组中应存入的位置
86
    i = (n - 1) & hash;//index
87
    //获取数组中对应元素的数据
88
    p = tab[i];
89

90
    if (p == null){
91
        //底层会创建一个键值对对象，直接放到数组当中
92
        tab[i] = newNode(hash, key, value, null);
93
    }else {
94
        Node<K,V> e;
95
        K k;
96

97
        //等号的左边：数组中键值对的哈希值
98
        //等号的右边：当前要添加键值对的哈希值
99
        //如果键不一样，此时返回false
100
        //如果键一样，返回true
101
        boolean b1 = p.hash == hash;
102

103
        if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){
104
            e = p;
105
        } else if (p instanceof TreeNode){
106
            //判断数组中获取出来的键值对是不是红黑树中的节点
107
            //如果是，则调用方法putTreeVal，把当前的节点按照红黑树的规则添加到树当中。
108
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
109
        } else {
110
            //如果从数组中获取出来的键值对不是红黑树中的节点
111
            //表示此时下面挂的是链表
112
            for (int binCount = 0; ; ++binCount) {
113
                if ((e = p.next) == null) {
114
                    //此时就会创建一个新的节点，挂在下面形成链表
115
                    p.next = newNode(hash, key, value, null);
116
                    //判断当前链表长度是否超过8，如果超过8，就会调用方法treeifyBin
117
                    //treeifyBin方法的底层还会继续判断
118
                    //判断数组的长度是否大于等于64
119
                    //如果同时满足这两个条件，就会把这个链表转成红黑树
120
                    if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);
121
                    break;
122
                }
123
                //e：0x0044  ddd  444
124
                //要添加的元素： 0x0055   ddd   555
125
                //如果哈希值一样，就会调用equals方法比较内部的属性值是否相同
126
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
127
                    break;
128
                }
129

130
                p = e;
131
            }
132
        }
133

134
        //如果e为null，表示当前不需要覆盖任何元素
135
        //如果e不为null，表示当前的键是一样的，值会被覆盖
136
        //e: 0x0044  ddd  555
137
        //要添加的元素： 0x0055   ddd   555
138
        if (e != null) {
139
            V oldValue = e.value;
140
            if (!onlyIfAbsent || oldValue == null){
141
                //等号的右边：当前要添加的值
142
                //等号的左边：0x0044的值
143
                e.value = value;
144
            }
145
            afterNodeAccess(e);
146
            return oldValue;
147
        }
148
    }
149

150
    //threshold：记录的就是数组的长度 * 0.75，哈希表的扩容时机  16 * 0.75 = 12
151
    if (++size > threshold){
152
        resize();
153
    }
154

155
    //表示当前没有覆盖任何元素，返回null
156
    return null;
157
}

1
1.TreeMap中每一个节点的内部属性
2
        K key;  //键
3
        V value;    //值
4
        Entry<K, V> left;   //左子节点
5
        Entry<K, V> right;  //右子节点
6
        Entry<K, V> parent; //父节点
7
        boolean color;  //节点的颜色
8

9

10
2.TreeMap类中中要知道的一些成员变量
11

12
public class TreeMap<K, V> {
13

14
    //比较器对象
15
    private final Comparator<? super K> comparator;
16

17
    //根节点
18
    private transient Entry<K, V> root;
19

20
    //集合的长度
21
    private transient int size = 0;
22

23

24

25
3.空参构造
26

27
    //空参构造就是没有传递比较器对象
28
    public TreeMap() {
29
        comparator = null;
30
    }
31

32

33

34
4.带参构造
35

36
    //带参构造就是传递了比较器对象。
37
    public TreeMap(Comparator<? super K> comparator) {
38
        this.comparator = comparator;
39
    }
40

41

42
5.添加元素
43

44
    public V put(K key, V value) {
45
        return put(key, value, true);
46
    }
47

48
    参数一：键
49
    参数二：值
50
    参数三：当键重复的时候，是否需要覆盖值
51
        true：覆盖
52
        false：不覆盖
53

54
    private V put(K key, V value, boolean replaceOld) {
55
        //获取根节点的地址值，赋值给局部变量t
56
        Entry<K, V> t = root;
57
        //判断根节点是否为null
58
        //如果为null，表示当前是第一次添加，会把当前要添加的元素，当做根节点
59
        //如果不为null，表示当前不是第一次添加，跳过这个判断继续执行下面的代码
60
        if (t == null) {
61
            //方法的底层，会创建一个Entry对象，把他当做根节点
62
            addEntryToEmptyMap(key, value);
63
            //表示此时没有覆盖任何的元素
64
            return null;
65
        }
66
        //表示两个元素的键比较之后的结果
67
        int cmp;
68
        //表示当前要添加节点的父节点
69
        Entry<K, V> parent;
70

71
        //表示当前的比较规则
72
        //如果我们是采取默认的自然排序，那么此时comparator记录的是null，cpr记录的也是null
73
        //如果我们是采取比较去排序方式，那么此时comparator记录的是就是比较器
74
        Comparator<? super K> cpr = comparator;
75
        //表示判断当前是否有比较器对象
76
        //如果传递了比较器对象，就执行if里面的代码，此时以比较器的规则为准
77
        //如果没有传递比较器对象，就执行else里面的代码，此时以自然排序的规则为准
78
        if (cpr != null) {
79
            do {
80
                parent = t;
81
                cmp = cpr.compare(key, t.key);
82
                if (cmp < 0)
83
                    t = t.left;
84
                else if (cmp > 0)
85
                    t = t.right;
86
                else {
87
                    V oldValue = t.value;
88
                    if (replaceOld || oldValue == null) {
89
                        t.value = value;
90
                    }
91
                    return oldValue;
92
                }
93
            } while (t != null);
94
        } else {
95
            //把键进行强转，强转成Comparable类型的
96
            //要求：键必须要实现Comparable接口，如果没有实现这个接口
97
            //此时在强转的时候，就会报错。
98
            Comparable<? super K> k = (Comparable<? super K>) key;
99
            do {
100
                //把根节点当做当前节点的父节点
101
                parent = t;
102
                //调用compareTo方法，比较根节点和当前要添加节点的大小关系
103
                cmp = k.compareTo(t.key);
104

105
                if (cmp < 0)
106
                    //如果比较的结果为负数
107
                    //那么继续到根节点的左边去找
108
                    t = t.left;
109
                else if (cmp > 0)
110
                    //如果比较的结果为正数
111
                    //那么继续到根节点的右边去找
112
                    t = t.right;
113
                else {
114
                    //如果比较的结果为0，会覆盖
115
                    V oldValue = t.value;
116
                    if (replaceOld || oldValue == null) {
117
                        t.value = value;
118
                    }
119
                    return oldValue;
120
                }
121
            } while (t != null);
122
        }
123
        //就会把当前节点按照指定的规则进行添加
124
        addEntry(key, value, parent, cmp < 0);
125
        return null;
126
    }
127

128

129
    private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {
130
        Entry<K, V> e = new Entry<>(key, value, parent);
131
        if (addToLeft)
132
            parent.left = e;
133
        else
134
            parent.right = e;
135
        //添加完毕之后，需要按照红黑树的规则进行调整
136
        fixAfterInsertion(e);
137
        size++;
138
        modCount++;
139
    }
140

141

142
    private void fixAfterInsertion(Entry<K, V> x) {
143
        //因为红黑树的节点默认就是红色的
144
        x.color = RED;
145

146
        //按照红黑规则进行调整
147

148
        //parentOf:获取x的父节点
149
        //parentOf(parentOf(x)):获取x的爷爷节点
150
        //leftOf:获取左子节点
151
        while (x != null && x != root && x.parent.color == RED) {
152

153

154
            //判断当前节点的父节点是爷爷节点的左子节点还是右子节点
155
            //目的：为了获取当前节点的叔叔节点
156
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
157
                //表示当前节点的父节点是爷爷节点的左子节点
158
                //那么下面就可以用rightOf获取到当前节点的叔叔节点
159
                Entry<K, V> y = rightOf(parentOf(parentOf(x)));
160
                if (colorOf(y) == RED) {
161
                    //叔叔节点为红色的处理方案
162

163
                    //把父节点设置为黑色
164
                    setColor(parentOf(x), BLACK);
165
                    //把叔叔节点设置为黑色
166
                    setColor(y, BLACK);
167

168
                    //把爷爷节点设置为红色
169
                    setColor(parentOf(parentOf(x)), RED);
170

171
                    //把爷爷节点设置为当前节点
172
                    x = parentOf(parentOf(x));
173
                } else {
174

175
                    //叔叔节点为黑色的处理方案
176

177

178
                    //表示判断当前节点是否为父节点的右子节点
179
                    if (x == rightOf(parentOf(x))) {
180

181
                        //表示当前节点是父节点的右子节点
182
                        x = parentOf(x);
183
                        //左旋
184
                        rotateLeft(x);
185
                    }
186
                    setColor(parentOf(x), BLACK);
187
                    setColor(parentOf(parentOf(x)), RED);
188
                    rotateRight(parentOf(parentOf(x)));
189
                }
190
            } else {
191
                //表示当前节点的父节点是爷爷节点的右子节点
192
                //那么下面就可以用leftOf获取到当前节点的叔叔节点
193
                Entry<K, V> y = leftOf(parentOf(parentOf(x)));
194
                if (colorOf(y) == RED) {
195
                    setColor(parentOf(x), BLACK);
196
                    setColor(y, BLACK);
197
                    setColor(parentOf(parentOf(x)), RED);
198
                    x = parentOf(parentOf(x));
199
                } else {
200
                    if (x == leftOf(parentOf(x))) {
201
                        x = parentOf(x);
202
                        rotateRight(x);
203
                    }
204
                    setColor(parentOf(x), BLACK);
205
                    setColor(parentOf(parentOf(x)), RED);
206
                    rotateLeft(parentOf(parentOf(x)));
207
                }
208
            }
209
        }
210

211
        //把根节点设置为黑色
212
        root.color = BLACK;
213
    }
214

215

216
1.TreeMap添加元素的时候，键是不需要重写hashCode和equals方法？
217

218
2.在HashMap的底层，默认是利用哈希值的大小关系来创建红黑树的，所以，HashMap的键不需要实现Compareable接口或者传递比较器对象。
219

220
3.TreeMap和HashMap谁的效率更高？
221
    如果是最坏情况，添加了8个元素，这8个元素形成了链表，此时TreeMap的效率要更高，但是这种情况出现的几率非常的少。
222
    一般而言，还是HashMap的效率要更高。
223

224
4.在Map集合中，如果键重复了，不会覆盖的put方法：
225
    思想：代码中的逻辑都有两面性，如果我们只知道了其中的A面，而且代码中还发现了有变量可以控制两面性的发生，那么该逻辑一定会有B面。
226
    习惯：
227
    boolean类型的变量控制，一般只有AB两面，因为boolean只有两个值
228
    int类型的变量控制，一般至少有三面，因为int可以取多个值。
229
    第一种方法：
230

231
    V putIfAbsent(K key, V value)，仅当键不存在时，才会将键值对插入Map，返回Map中该键原本关联的值（若原本不存在则返回null）。
232
    第二种方法：自定义Map实现，
233

234
    继承现有Map类并重写put()方法，但要注意线程安全问题。
235

236
5.三种双列集合的使用建议：
237
    默认：HashMap（效率最高）
238
    如果要保证存取有序：LinkedHashMap
239
    如果要进行排序：TreeMap