21. 集合 - 阿狗工具

21. 集合

2024-04-09 20:50:09 阅读数 1175

参考链接：

[https://blog.csdn.net/zhangqunshuai/article/details/80660974]

[(https://blog.csdn.net/zhangqunshuai/article/details/80660974)

https://blog.csdn.net/t_testview/article/details/89014863

参考书籍： Offer来了（Java面试核心知识点）王磊电子工业出版社

1、概述

List , Set, Map都是接口，前两个继承至Collection接口，Map为独立接口

Set下有HashSet，LinkedHashSet，TreeSet

List下有ArrayList，Vector，LinkedList

Map下有Hashtable，LinkedHashMap，HashMap，TreeMap

Collection接口下还有个Queue接口，有PriorityQueue类

Java中集合类是放在java.util中，是一个用来存放对象的容器。 1、只能存放对象，不能存放int等类型，存的是对应的是Integer等对象 2、存的是对象的引用，对象本身是放在堆内存中 3、可以存放不同类型的对象（因为实现的时候使用了泛型），不建议使用。

注意：

Queue接口与List、Set同一级别，都是继承了Collection接口。

看图你会发现,LinkedList既可以实现Queue接口,也可以实现List接口.只不过呢, LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。

SortedSet是个接口，它里面的（只有TreeSet这一个实现可用）中的元素一定是有序的。

2、Connection接口（所有集合类的根接口）

image.png

2.1 List集合

特点：有序,可重复

ArrayList 优点: 底层数据结构是数组，查询快；定义时不需要定义数组大小，如果数组大小不够，会创建一个新的更大的数组将原来的元素复制过去。 缺点: 线程不安全；增删慢。（元素必须连续存储，因此如果在中间位置添加或删除元素，需要其后面所有元素进行移动，不适合随机插入和删除，更适合随机查找和遍历操作）
Vector 优点: 底层数据结构是数组，查询快；线程安全，支持线程同步（即同一时刻只允许一个线程对Vector进行写操作，以保证多线程下数据的一致性） 缺点: 增删慢；读写效率比ArrayList低（因为需要频繁的对Vector对象进行加锁和释放锁操作）
LinkedList 优点: 底层数据结构是双向链表，增删快（链表操作，增删只需要移动对应指针）。 缺点: 线程不安全，效率高，查询慢（需要从头到尾遍历）

2.2 Queue队列

ArrayBlockingQueue:基于数组数据结构实现的有界阻塞队列。
LinkedBlockingQueue:基于链表数据结构的有界阻塞队列。
PriorityBlockingQueue:支持优先级排序的无界阻塞队列。
DelayQueue:支持延迟操作的无界阻塞队列。
SynchronousQueue:用于线程同步的阻塞队列。
LinkedTransferQueue:基于链表数据结构实现的无界阻塞队列。
LinkedBlockingQueue:基于链表数据结构实现的双向阻塞队列。

2.3 Set 集合

特点：不可重复，无序

（1）HashSet

特点：底层数据结构是哈希表。(无序,唯一)

如何来保证元素唯一性?

依赖两个方法：hashCode()和equals()

（2）LinkedHashSet（HashTable实现数据存储，双向链表记录顺序）

特点：底层数据结构是链表和哈希表。(FIFO插入有序,唯一)

1.由链表保证元素有序

2.由哈希表保证元素唯一

（3）TreeSet

特点：底层数据结构是红黑树。基于二叉树的原理对新添加的对象按照指定的顺序排序（升序或降序），每添加一个对象都会进行排序，并将对象插入二叉树的指定位置。(唯一，有序)

1）.如何保证元素唯一性的呢?

根据比较的返回值是否是0来决定

2）. 如何保证元素排序的呢?

① 自然排序

需要排序的类中实现 Comparable接口
重写Comparable接口中的Compareto方法

代码演示：

把用户类按照名字长度排序，长度相等的按照名字的hash值，如果hash值相等则名字相等，按照年龄排序。

User类：

public class User implements Comparable<User> {
    private String name;
    private int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        User other = (User) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    @Override
    public int compareTo(User o) {
        // return -1; //-1表示放在红黑树的左边,即逆序输出
        // return 1; //1表示放在红黑树的右边，即顺序输出
        // return 0; //表示元素相同，仅存放第一个元素
        // 主要条件 姓名的长度,如果姓名长度小的就放在左子树，否则放在右子树
        int num = this.name.length() - o.name.length();
        // 姓名的长度相同，不代表内容相同,如果按字典顺序此 String 对象位于参数字符串之前，则比较结果为一个负整数。
        // 如果按字典顺序此 String 对象位于参数字符串之后，则比较结果为一个正整数。
        // 如果这两个字符串相等，则结果为 0
        int num1 = num == 0 ? (this.name.hashCode() - o.name.hashCode()) : num;
        // 姓名的长度和内容相同，不代表年龄相同，所以还要判断年龄
        int num2 = num1 == 0 ? this.age - o.age : num1;
        return num2;

    }

    @Override
    public String toString() {
        return "User [name=" + name + ", age=" + age + "]";
    }

}

测试类：

import java.util.TreeSet;

public class Demo {
    public static void main(String[] args) {
        User user1 = new User("zhanggengying", 18);
        User user2 = new User("zhoufan", 21);
        User user3 = new User("zhoufan", 20);

        TreeSet<User> ts = new TreeSet<User>();
        ts.add(user1);
        ts.add(user2);
        ts.add(user3);

        for (User user : ts) {
            System.out.println(user);
        }
    }
}

结果：

User [name=zhoufan, age=20]
User [name=zhoufan, age=21]
User [name=zhanggengying, age=18]

② 比较器排序

比较器排序步骤：

单独创建一个比较类，这里以MyComparator为例，并且要让其继承Comparator接口。
重写Comparator接口中的Compare方法。

代码案例：和上述案例相同，不过是另一种实现方式

//用户类

package com.company.project.test09;

public class User {
    private String name;
    private int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        User other = (User) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "User [name=" + name + ", age=" + age + "]";
    }

}

//自己写的比较器

package com.company.project.test09;

import java.util.Comparator;

public class MyComparator implements Comparator<User> {

    @Override
    public int compare(User s1, User s2) {
        // 姓名长度
        int num = s1.getName().length() - s2.getName().length();
        // 姓名内容
        int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
        // 年龄
        int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2;
        return num3;
    }

}

//测试类

package com.company.project.test09;

import java.util.TreeSet;

//TreeSet的自然排序
//实现Comparable接口，重写compareTo方法
public class Demo {
    public static void main(String[] args) {
        User user1 = new User("zhanggengying", 18);
        User user2 = new User("zhoufan", 21);
        User user3 = new User("zhoufan", 20);

        TreeSet<User> ts = new TreeSet<User>(new MyComparator());
        ts.add(user1);
        ts.add(user2);
        ts.add(user3);

        for (User user : ts) {
            System.out.println(user);
        }
    }
}

（4）TreeSet, LinkedHashSet and HashSet 的区别

1）介绍：

TreeSet, LinkedHashSet and HashSet 在java中都是实现Set的数据结构
TreeSet的主要功能用于排序
LinkedHashSet的主要功能用于保证FIFO即有序的集合(先进先出)
HashSet只是通用的存储数据的集合，通过传入的数据，计算出哈希值，存入哈希表中。

2）相同点

Duplicates elements: 因为三者都实现Set interface，所以三者都不包含duplicate elements
Thread safety: 三者都不是线程安全的，如果要使用线程安全可以Collections.synchronizedSet()

3）不同点

Performance and Speed: HashSet插入数据最快，其次LinkHashSet，最慢的是TreeSet因为内部实现排序
Ordering: HashSet不保证有序，LinkHashSet保证FIFO即按插入顺序排序，TreeSet安装内部实现排序，也可以自定义排序规则
null:HashSet和LinkHashSet允许存在null数据，但是TreeSet中插入null数据时会报NullPointerException

代码：

package com.company.project.test07;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.TreeSet;

//TreeSet, LinkedHashSet and HashSet的区别
public class Demo {
    public static void main(String[] args) {
        HashSet<Integer> hashSet = new HashSet<>();
        LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();
        TreeSet<Integer> treeSet = new TreeSet<>();

        for (Integer data : Arrays.asList(5, 4, 3, 6, 8, 9, 10, 50, 30, 90, 111)) {
            // hashSet.add(data);
            hashSet.add(data);
            linkedHashSet.add(data);
            treeSet.add(data);
        }

        // 不保证有序
        System.out.println("Ordering in HashSet :" + hashSet);

        // FIFO保证安装插入顺序排序
        System.out.println("Order of element in LinkedHashSet :" + linkedHashSet);

        // 内部实现排序
        System.out.println("Order of objects in TreeSet :" + treeSet);

    }

}

结果：

Ordering in HashSet :[50, 3, 4, 5, 6, 8, 9, 10, 90, 30, 111]
Order of element in LinkedHashSet :[5, 4, 3, 6, 8, 9, 10, 50, 30, 90, 111]
Order of objects in TreeSet :[3, 4, 5, 6, 8, 9, 10, 30, 50, 90, 111]

2.4 总结

针对Collection集合我们到底使用谁呢?(掌握)

image.png

3. Map接口（映射接口，存放键值对）

image.png

特点：

以键值对的形式存放对象。key-value。一般是key为String类型，value为Object的类型。

Map接口有四个比较重要的实现类，分别是HashMap、TreeMap、LinkedHashMap和HashTable。

3.1 Map集合

HashMap（数组+链表/红黑树，线程不安全）

HashMap的数据结构，内部为数组，数组的每个元素又是一个单向链表，如果单链表的元素超过8个，HashMap又会将链式结构变为红黑树来提高查找效率。

如果想要线程安全，可以用Collections的synchronizedMap方法使HashMap具有线程安全，或者使用ConcurrentHashMap。

image.png

HashMap数组+链表结构

image.png

HashMap数组+红黑树结构

2.ConcurrentHashMap(分段锁实现，线程安全)

采用分段锁的思想实现并发操作，因此线程安全。

ConcurrentHashMap由多个Segment组成（Segment的数量是锁的并发度），每个Segment都是继承ReentrantLock并单独加锁，所有每次加锁操作是锁住的都是一个Segment，这样只要保证每个Segment都是线程安全的，也就实现了全局的线程安全。

image.png

ConcurrentHashMap数组+单向链表结构

image.png

ConcurrentHashMap数组+红黑树结构

3.HashTable(线程安全，哈希表)

继承Dictionary类，同一时刻只有一个线程能写HashTable,并发性不如ConcurrentHashMap

4.TreeMap(二叉树数据结构，有序)

实现了SortedMap接口保证元素顺序存储，默认按键值升序存储，也可自定义比较器（实现Comparable接口或者自定义比较器）

5.LinkedHashMap（基于HashTable数据结构，使用链表保存插入顺序）

LinkedHashMap是HashMap的子类，内部使用链表保存元素的插入顺序，通过Iterator遍历LinkedHashMap时，会按照元素的插入顺序访问元素。

（1）HashMap、TreeMap、LinkedHashMap的区别：

image.png

（2）Hashtable和HashMap的区别：

Hashtable的方法是同步的，HashMap的方法不是同步的。这是两者最主要的区别。
Hashtable是线程安全的，HashMap不是线程安全的。
HashMap效率较高，Hashtable效率较低。
Hashtable不允许null值，HashMap允许null值（key和value都允许，HashMap允许多条记录的值为null）
父类不同：Hashtable的父类是Dictionary，HashMap的父类是AbstractMap

（3）如何选择Hashtable和HashMap？

如果对同步性或与遗留代码的兼容性没有任何要求，建议使用HashMap。查看Hashtable的源代码就可以发现，除构造函数外，Hashtable的所有 public 方法声明中都有 synchronized关键字，而HashMap的源码中则没有。

（4）所有带hash的前缀的Map集合的存储原理：

通过 new 关键字在 Heap 堆中申请空间
保存其中元素的空间，按照hash码，预设好一个个的空间，这个空间就是 Hash Bucket(哈希桶)
每个桶有自己的Hash编号，一开始有少量的 Hash Bucket
当程序试图将一个 key-value(Entry) 放入 HashMap 中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的Bucket位置。
如果该Bucket为空，直接存放入该Bucket;
如果该Bucket不为空，使用 equals 比较两个Entry 的 Key；
if(true){新 value 将覆盖 Entry 原 value，key 不变}
if(false){新 Entry 将与 Bucket中原 Entry 形成 Entry 链，而且新 Entry 位于 Entry 链的头部}

3.2 Map集合的遍历：

1、通过内部类Entry进行遍历

2、通过迭代器进行遍历，先获得Entry的Set集合

3、通过keySet方法获得键的Set集合，通过遍历键取值

4、通过map.values()获得所有值，但是不能获得键

代码演示：

package com.company.project.test1001;

import java.util.HashMap;
import java.util.Map;

//Map集合的遍历
public class Demo {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>();
        map.put("A", "北京");
        map.put("D", "上海");
        map.put("C", "广东");

        for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println(entry);
        }

    }
}

结果：

A=北京
C=广东
D=上海