Java基础知识——集合

淩亂°似流年 2023-07-06 11:42 19阅读 0赞

### 简介 ###

在Java中，如果一个Java对象可以在内部持有若干其他Java对象，并对外提供访问接口，我们把这种Java对象称为集合，故Java的数组也可以看作是一种集合。那么即然有了数组，为什么Java还要提供集合类呢，原因：一、数组初始化后大小不可变；二、数组只能按索引顺序存取

### 集合总体框架 ###

Java 集合框架为不同类型的集合定义了大量接口，**集合有两个基本接口：Collection 和 Map**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70]  
下图展示了 Java 类库中的集合，并简要描述了每个集合类的用途（为简单起见， 并未包含线程安全集合java.util.concurrent.\*)。在表中，除了以 Map结尾的类之外， 其他类都实现了Collection接口，而以Map结尾的类实现了Map接口。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 1]  
以下是具体实现与继承图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 3]

### Collection ###

Java标准库自带的java.util包提供了集合类：Collection，它是除Map外所有其他集合类的根接口。Java实现的集合类主要有两个特点，**一是实现了接口和实现类相分离**，例如，有序表的接口是List，具体的实现类有ArrayList，LinkedList等，**二是支持泛型**，我们可以限制在一个集合中只能放入同一种数据类型的元素，**最后，Java访问集合总是通过迭代器（Iterator）来实现**，它最明显的好处在于无需知道集合内部元素是按什么方式存储的。Java的java.util包主要提供了以下三种类型的集合：

*  List：一种有序列表的集合
 *  Set：一种保证没有重复元素的集合
 *  Map：一种通过键值（key-value）查找的映射表集合

此外，由于历史原因，有小部分集合已经不推荐使用了，但是又不能直接从包中删除，因为可能会影响别的基础包，例如：

*  Hashtable：一种线程安全的Map实现；
 *  Vector：一种线程安全的List实现；
 *  Stack：基于Vector实现的LIFO的栈；

为什么不推荐使用呢，**线程安全但是性能不佳，重点是这是最初的实现，现在已被java.util.concurrent包里的集合代替了**，还有不推荐使用的接口Enumeration<E>：已被Iterator取代，还有一个小细节：**链表与泛型集合之间有一个重要的区别，链表是一个有序集合（ordered collection), 每个对象的位置十分重要**。

### List ###

在集合类中，List是最基础的一种集合：**它是一种有序列表**。List的行为和数组几乎完全相同，放入元素的先后顺序存放，每个元素都可以通过索引确定自己的位置，List的索引和数组一样，从0开始。也正是因为这些特性，所以List集合也是用的最多的集合；主要接口有：

在末尾添加一个元素：void add(E e)
    在指定索引添加一个元素：void add(int index, E e)
    删除指定索引的元素：int remove(int index)
    删除某个元素：int remove(Object e)
    获取指定索引的元素：E get(int index)
    获取链表大小（包含元素的个数）：int size()

List接口有两种实现，一种通过数组实现的ArrayLIst，还有一种是通过链表实现的LinkedList，主要区别是：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 4]  
通常选用ArrayList集合，需要经常查找可用ArrayList集合，经常增删就用LinkedList集合

#### List的特点 ####

*  List接口允许我们添加重复的元素
 *  允许添加null

#### List的遍历 ####

我们可以用用for循环根据索引配合get(int)方法遍历，但是不推荐这么使用，原因有两个，一是代码复杂，二是因为get(int)方法只有ArrayList的实现是高效的，换成LinkedList后，索引越大，访问速度越慢。所以，**遍历List集合一定要用迭代器Iterator！**

##### List遍历中的Iterator #####

Iterator本身也是一个对象，但它是由List的实例调用iterator()方法的时候创建的。Iterator对象知道如何遍历一个List，并且不同的List类型，返回的Iterator对象实现也是不同的（List接口定义，子类提供不同的实现），但总是具有最高的访问效率。Iterator对象有两个方法：boolean hasNext()判断是否有下一个元素，E next()返回下一个元素。可能你觉得Iterator访问List的代码还比较复杂，还可以用Java的for each循环，实际上，**只要实现了Iterable接口的集合类都可以直接用for each循环来遍历，Java编译器本身并不知道如何遍历集合对象，但它会自动把for each循环变成Iterator的调用**，原因就在于Iterable接口定义了一个Iterator iterator()方法，强迫集合类必须返回一个Iterator实例。

#### List和Array转换 ####

把List变为Array有三种方法:

*  第一种是调用toArray()方法直接返回一个Object\[\]数组(这种方法会丢失类型信息，所以实际应用很少)

List<String> list = List.of("apple", "pear", "banana");
    Object[] array = list.toArray();

*  第二种方式是给toArray(T\[\])传入一个类型相同的Array，List内部自动把元素复制到传入的Array中,当然也可传该类型的父类

List<Integer> list = List.of(12, 34, 56);
    Integer[] array = list.toArray(new Integer[list.size()]);

*  第三种更简洁的写法是通过List接口定义的T\[\] toArray(IntFunction<T\[\]> generator)方法：

List<Integer> list = List.of(12, 34, 56);
    Integer[] array = list.toArray(Integer[]::new);

*  反过来，把Array变为List就简单多了，通过List.of(T…)方法最简单

Integer[] array = { 1, 2, 3 };
    List<Integer> list = List.of(array);

对于JDK 11之前的版本，可以使用Arrays.asList(T…)方法把数组转换成List，要注意的是，返回的List不一定就是ArrayList或者LinkedList，因为List只是一个接口，如果我们调用List.of()，它返回的是一个只读List，对只读List调用add()、remove()方法会抛出UnsupportedOperationException

### equals方法 ###

**Object类里的equals只做了简单的==判断**，如果我们的类没有覆写equals()方法，那么List就是用==比较两个对象，即比较内存地址，所以结果会有误，因此**List内部并不能简单通过==判断两个元素(自己定义的类)是否相等，而是使用自行实现的equals()方法判断两个元素是否相等**。  
**如果不重写还会间接影响需要使用equals()的方法，例如：List的contains()、indexOf()这些方法**，要正确使用List的contains()、indexOf()这些方法，放入的实例必须正确覆写equals()方法，否则，放进去的实例，查找不到。我们之所以能正常放入使用String、Integer这些对象，是因为Java标准库定义的这些类已经正确实现了equals()方法(可以自行查看源码)。例如：

public class Main {
        public static void main(String[] args) {
            List<Person> list = List.of(
                new Person("Xiao Ming"),
                new Person("Xiao Hong"),
                new Person("Bob")
            );
            // false，找不到Bob，因为Person类没有正确写好equals方法
            System.out.println(list.contains(new Person("Bob"))); 
        }
    }
    
    class Person {
        String name;
        public Person(String name) {
            this.name = name;
        }
    }

#### 正确编写equals ####

正确编写equals()方法要求我们必须满足以下几个条件：

*  自反性（Reflexive）：对于非null的x来说，x.equals(x)必须返回true；
 *  对称性（Symmetric）：对于非null的x和y来说，如果x.equals(y)为true，则y.equals(x)也必须为true；
 *  传递性（Transitive）：对于非null的x、y和z来说，如果x.equals(y)为true，y.equals(z)也为true，那么x.equals(z)也必须为true；
 *  一致性（Consistent）：对于非null的x和y来说，只要x和y状态不变，则x.equals(y)总是一致地返回true或者false；
 *  对null的比较：即x.equals(null)永远返回false。

上述规则看上去似乎非常复杂，但其实代码实现equals()方法是很简单的，例：

public class Person {
        public String name;
        public int age;
    }

首先，我们要定义“相等”的逻辑含义。对于Person类，如果name相等，并且age相等，我们就认为两个Person实例相等。  
使用Objects.equals()比较两个引用类型是否相等的目的是省去了判断null的麻烦。两个引用类型都是null时它们也是相等的。如果不调用List的contains()、indexOf()这些方法且不直接使用equals()，那么放入的元素就可以不实现equals()方法。(但**建议只要是实体类都覆写equals()，因为规范与健壮**)因此：

public boolean equals(Object o) {
        if (o instanceof Person) {
            Person p = (Person) o;
            //Objects.equals()静态方法,可以比较null值
            return Objects.equals(this.name, p.name) && this.age == p.age;
        }
        return false;
    }

**总结一下equals()方法的正确编写方法**

*  先确定实例“相等”的逻辑，即哪些字段相等，就认为实例相等；
 *  用instanceof判断传入的待比较的Object是不是当前类型，如果是，继续比较，否则，返回false；
 *  对引用类型用Objects.equals()比较，对基本类型直接用==比较。

**还是觉得难怎么办，IDEA可以自动帮你生成equals()方法，上面的只是原理而已**，下面就是自动生成的

@Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;
            return age == person.age &&
                    Objects.equals(name, person.name);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(name, age);
        }

### Map ###

而Map这种键值（key-value）映射表的数据结构，作用就是能高效通过key快速查找value（元素）。当我们调用put(K key, V value)方法时，就把key和value做了映射并放入Map。当我们调用V get(K key)时，就可以通过key获取到对应的value。如果key不存在，则返回null。和List类似，Map也是一个接口，最常用的实现类是HashMap。

Map<String, String> map = new HashMap<>();
        map.put("name", "LL");
        System.out.println(map.get("name"));

Map中不存在重复的key，因为放入相同的key，只会把原有的key-value对应的value给替换掉，虽然key不能重复，但value是可以重复的

#### 遍历Map ####

对Map来说，要遍历key可以使用for each循环遍历Map实例的keySet()方法返回的Set集合，它包含不重复的key的集合:

public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("name", "LL");
        map.put("password", "123456");
        map.put("age", "8");
        for (String s : map.keySet()) {
            String string = map.get(s);
            System.out.println(string);
        }
    }

同时遍历key和value可以使用for each循环遍历Map对象的entrySet()集合，它包含每一个key-value映射：

for (Map.Entry<String,String> entry : map.entrySet()) {
            String key = entry.getKey();
            String value = entry.getValue();
            System.out.println(key + " = " + value);
        }

Map和List不同的是，Map存储的是key-value的映射关系，并且，它不保证顺序。在遍历的时候，遍历的顺序既不一定是put()时放入的key的顺序，也不一定是key的排序顺序。使用Map时，任何依赖顺序的逻辑都是不可靠的。

### 编写equals和hashCode ###

HashMap之所以能根据key直接拿到value，原因是它内部通过空间换时间的方法，用一个大数组存储所有value，并根据key直接计算出value应该存储在哪个索引，如果key的值为"a"，计算得到的索引总是1，因此返回value为Person(“Xiao Ming”)，如果key的值为"b"，计算得到的索引总是5，因此返回value为Person(“Xiao Hong”)，这样，就不必遍历整个数组，即可直接读取key对应的value。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 5]  
这里有一个问题，我们放入Map的key是字符串"a"，但是，当我们获取Map的value时，传入的变量不一定就是放入的那个key对象。换句话讲，两个key应该是内容相同，但不一定是同一个对象。测试代码如下：

public static void main(String[] args) {
        String key1 = "a";
        Map<String, Integer> map = new HashMap<>();
        map.put(key1, 123);
    
        String key2 = new String("a");
        map.get(key2); // 123，也能获取出来值
    
        System.out.println(key1 == key2); // false
        System.out.println(key1.equals(key2)); // true
    }

因为在Map的内部，对key做比较是通过equals()实现的，这一点和List查找元素需要正确覆写equals()是一样的，即正确使用Map必须保证：**作为key的对象必须正确覆写equals()方法**。只有这样才能正确做比较，而不是用Object的equals()方法做（==）内存地址比较！  
**我们经常使用String作为key，因为String已经正确覆写了equals()方法。但如果我们放入的key是一个自己写的类，就必须保证正确覆写了equals()方法**  
我们再思考一下HashMap为什么能通过key直接计算出value存储的索引。相同的key对象（使用equals()判断时返回true）必须要计算出相同的索引，否则，相同的key每次取出的value就不一定对。  
通过key计算索引的方式就是调用key对象的hashCode()方法，它返回一个int整数。HashMap正是通过这个方法直接定位key对应的value的索引，继而直接返回value。  
因此，正确使用Map必须保证：

*  作为key的对象必须正确覆写equals()方法，相等的两个key实例调用equals()必须返回true；
 *  作为key的对象还必须正确覆写hashCode()方法，且hashCode()方法要严格遵循两个规定：一、如果两个对象相等，则它们的hashCode()一定要等；二、如果两个对象不相等，则它们的hashCode()尽量不相等；

上述第一条规范是正确性，必须保证实现，否则HashMap不能正常工作  
而第二条如果尽量满足，则可以保证查询效率，因为不同的对象，如果返回相同的hashCode()，会造成Map内部存储冲突，使存取的效率下降。  
正确编写equals()的方法已经说过了（用IDEA），这里看下实现hashCode（）的方法，

public class Person {
        String firstName;
        String lastName;
        int age;
    
        @Override
        int hashCode() {
            int h = 1;
            h = 31 * h + firstName.hashCode();
            h = 31 * h + lastName.hashCode();
            h = 31 * h + age;
            return h;
        }
    }

注意到String类已经正确实现了hashCode()方法，我们在计算Person的hashCode()时，反复使用31\*h，这样做的目的是为了尽量把不同的Person实例的hashCode()均匀分布到整个int范围。至于为什么是31，当然也可以是别的数字，但31是个神奇的数字，JVM可以做能优化（32-1=31）。  
和实现equals()方法遇到的问题类似，如果firstName或lastName为null，上述代码工作起来就会抛NullPointerException。为了解决这个问题，我们在计算hashCode()的时候，经常借助Objects.hash()来计算：

int hashCode() {
        return Objects.hash(firstName, lastName, age);
    }

我们查看 Objects.hash（）源码可知，它由下面的方法实现：

public static int hashCode(Object a[]) {
        if (a == null)
            return 0;
        int result = 1;
        for (Object element : a)
        	//和我们的算法一致，两个哈希算出的值自然也一致
            result = 31 * result + (element == null ? 0 : element.hashCode());
            return result;
    }

所以，编写equals()和hashCode()遵循的原则是:  
**equals()用到的用于比较的每一个字段，都必须在hashCode()中用于计算；equals()中没有使用到的字段，绝不可放在hashCode()中计算**。  
注：当然IDEA也可以帮你自动生成hashCode()方法  
如果不同的两个key，例如"a"和"b"，它们的hashCode()恰好是相同的（这种情况是完全可能的，因为不相等的两个实例，只要求hashCode()尽量不相等），那么，当我们放入：

map.put("a", new Person("Xiao Ming"));
    map.put("b", new Person("Xiao Hong"));

时，由于计算出的数组索引相同，后面放入的"Xiao Hong"会不会把"Xiao Ming"覆盖了？  
当然不会！使用Map的时候，只要key不相同，它们映射的value就互不干扰。但是，在HashMap内部，确实可能存在不同的key，映射到相同的hashCode()，即相同的数组索引上，怎么办？  
我们就假设"a"和"b"这两个key最终计算出的索引都是5，那么，在HashMap的数组中，实际存储的不是一个Person实例，而是一个List，它包含两个Entry，一个是"a"的映射，一个是"b"的映射：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 6]  
在查找的时候，例如：

Person p = map.get("a");

HashMap内部通过"a"找到的实际上是List<Entry<String, Person>>，它还需要遍历这个List，并找到一个Entry，它的key字段是"a"，才能返回对应的Person实例。  
我们把不同的key具有相同的hashCode()的情况称之为哈希冲突。在冲突的时候，一种最简单的解决办法是用List存储hashCode()相同的key-value。显然，如果冲突的概率越大，这个List就越长，Map的get()方法效率就越低，这就是为什么要尽量满足条件二：如果两个对象不相等，则两个对象的hashCode()尽量不要相等。  
最后：hashCode()方法编写得越好，HashMap工作的效率就越高，不会写就用默认的方法

### EnumMap ###

如果作为key的对象是enum类型，那么，还可以使用Java集合库提供的一种EnumMap，它在内部以一个非常紧凑的数组存储value，并且根据enum类型的key直接定位到内部数组的索引，并不需要计算hashCode()，不但效率最高，而且没有额外的空间浪费。

public static void main(String[] args) {
        Map<DayOfWeek, String> enumMap = new EnumMap<>(DayOfWeek.class);
        enumMap.put(DayOfWeek.MONDAY, "星期一");
        enumMap.put(DayOfWeek.THURSDAY, "星期二");
        enumMap.put(DayOfWeek.WEDNESDAY, "星期三");
        enumMap.put(DayOfWeek.THURSDAY, "星期四");
        enumMap.put(DayOfWeek.FRIDAY, "星期五");
        enumMap.put(DayOfWeek.SATURDAY, "星期六");
        enumMap.put(DayOfWeek.SUNDAY, "星期七");
        System.out.println(enumMap);
        System.out.println(enumMap.get(DayOfWeek.MONDAY));
    }

### TreeMap ###

我们已经知道，HashMap是一种以空间换时间的映射表，它的实现原理决定了内部的Key是无序的，即遍历HashMap的Key时，其顺序是不可预测的（但每个Key都会遍历一次且仅遍历一次）。**还有一种Map，它在内部会对Key进行排序，这种Map就是SortedMap。注意到SortedMap是接口，它的实现类是TreeMap**。  
![在这里插入图片描述][20200219141019530.png]

public static void main(String[] args) {
        Map<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("B", 2);
        treeMap.put("C", 3);
        treeMap.put("A", 1);
        treeMap.put("D", 4);
        for (String key : treeMap.keySet()) {
            System.out.println(key);
            // A B C D
        }
    }

**使用TreeMap时，放入的Key必须实现Comparable接口**。String、Integer这些类已经实现了Comparable接口，因此可以直接作为Key使用。作为Value的对象则没有任何要求。  
如果果作为Key的class没有实现Comparable接口，那么，必须在创建TreeMap时同时指定一个自定义排序算法：

public static void main(String[] args) {
        //不实现Comparable接口，Person将无法做为Key，因为Key将用于TreeMap排序
        Map<Person, Integer> personMap = new TreeMap<>((Person p1, Person p2) -> p1.name.compareTo(p2.name));
        personMap.put(new Person("Bob", "123456"), 100);
        personMap.put(new Person("Alice", "123456"), 85);
        personMap.put(new Person("Dave", "123456"), 90);
        personMap.put(new Person("Coco", "123456"), 80);
        for (Person p: personMap.keySet()){
            System.out.println(p.name);
        }
    }
    static class Person{
        public String name;
        public String password;
        public Person(String name, String password) {
            this.name = name;
            this.password = password;
        }
    }

注意到Comparator接口要求实现一个比较方法，它负责比较传入的两个元素a和b，如果a<b，则返回负数，通常是-1，如果a==b，则返回0，如果a>b，则返回正数，通常是1。TreeMap内部根据比较结果对Key进行排序。**要严格按照compare()规范实现比较逻辑，否则，TreeMap将不能正常工作。**  
我们可以传入一个new Person(“Bob”,“123456”)作为Key，它会返回对应的Integer值100。另外，注意到**Person类并未覆写equals()和hashCode()，因为TreeMap不使用equals()和hashCode()**。

System.out.println(personMap.get(new Person("Bob","123456")))

### Properties ###

在编写应用程序的时候，经常需要读写配置文件。配置文件的特点是，它的Key-Value一般都是String-String类型的，因此我们完全可以用Map<String, String>来表示它。例如，用户的设置：

user.name=Bob
    user.password=123456

因为配置文件非常常用，所以Java集合库提供了一个Properties来表示一组“配置”。由于历史遗留原因，Properties内部本质上是一个Hashtable，但我们只需要用到Properties自身关于读写配置的接口。而Hashtable的相关方法就不要用了，属于危险且老旧的操作

#### 读取配置文件 ####

用Properties读取配置文件非常简单。Java默认配置文件以.properties为扩展名，每行以key=value表示，以\#课开头的是注释。可以从文件系统读取properties文件，示例：

public static void main(String[] args)  throws IOException {
        	//文件路径
        	String configPath = ".../config.properties";
            Properties properties = new Properties();
            properties.load(new java.io.FileInputStream(configPath));
            String userName = properties.getProperty("user.name");
            System.out.println(userName);
            String userPassword = properties.getProperty("user.password");
            System.out.println(userPassword);
    }

可见，用Properties读取配置文件，一共有三步

*  创建Properties实例；
 *  调用load()读取文件；
 *  调用getProperty()获取配置  
    调用getProperty()获取配置时，如果key不存在，将返回null。我们还可以提供一个默认值，这样，当key不存在的时候，就返回默认值。学了这个，你就知道类似于SpringBoot一样的框架，读取配置文件的原理了。  
    也可以从classpath读取.properties文件，因为load(InputStream)方法接收一个InputStream实例，表示一个字节流，它不一定是文件流，也可以是从jar包中读取的资源流：

Properties props = new Properties();
    props.load(getClass().getResourceAsStream("/common/config.properties"));

如果有多个.properties文件，可以反复调用load()读取，后读取的key-value会覆盖已读取的key-value  
Properties设计的目的是存储String类型的key－value，但Properties实际上是从Hashtable派生的，它的设计实际上是有问题的，但是为了保持兼容性，现在已经没法修改了。除了getProperty()和setProperty()方法外，还有从Hashtable继承下来的get()和put()方法，这些方法的参数签名是Object，我们在使用Properties的时候，不要去调用这些从Hashtable继承下来的方法。

#### 写入配置文件 ####

如果通过setProperty()修改了Properties实例，可以把配置写入文件，以便下次启动时获得最新配置。写入配置文件使用store()方法

//修改properties对象内容
    properties.setProperty("user.password", "123");
    //储存内容改变至文件，且书写注释
    properties.store(new java.io.FileOutputStream(configPath),"This is an annotation!");
    System.out.println("new password:"+properties.getProperty("user.password"));

修改过后的配置文件

#This is an annotation!
    #Wed Feb 19 15:21:42 CST 2020
    user.name=Bob
    user.password=123

#### 编码 ####

早期版本的Java规定.properties文件编码是ASCII编码（ISO8859-1），如果涉及到中文就必须用name=\\u4e2d\\u6587来表示，非常别扭。从JDK9开始，Java的.properties文件可以使用UTF-8编码了。  
不过，需要注意的是，由于load(InputStream)默认总是以ASCII编码读取字节流，所以会导致读到乱码。我们需要用另一个重载方法load(Reader)读取：

Properties props = new Properties();
    props.load(new FileReader(configPath, StandardCharsets.UTF_8));

就可以正常读取中文。InputStream和Reader的区别是一个是字节流，一个是字符流。字符流在内存中已经以char类型表示了，不涉及编码问题。

### Set ###

我们知道，Map用于存储key-value的映射，对于充当key的对象，是不能重复的，并且，不但需要正确覆写equals()方法，还要正确覆写hashCode()方法。如果我们只需要存储不重复的key，并不需要存储映射的value，那么就可以使用Set。Set用于存储不重复的元素集合，它主要提供以下几个方法：

*  将元素添加进Set：boolean add(E e)
 *  将元素从Set删除：boolean remove(Object e)
 *  判断是否包含元素：boolean contains(Object e)

public static void main(String[] args) {
          Set<String> set = new HashSet<>();
          System.out.println(set.add("AAA"));//true
          System.out.println(set.add("BBB"));//true
          System.out.println(set.add("AAA"));//false
          System.out.println(set.size());//2
      }

**Set实际上相当于只存储key、不存储value的Map。我们经常用Set用于去除重复元素**。  
因为放入Set的元素和Map的key类似，都要正确实现equals()和hashCode()方法，否则该元素无法正确地放入Set。  
最常用的Set实现类是HashSet，实际上，**HashSet仅仅是对HashMap的一个简单封装**，它的核心代码如下：

public class HashSet<E> implements Set<E> {
        // 持有一个HashMap:
        private HashMap<E, Object> map = new HashMap<>();
        // 放入HashMap的value:
        private static final Object PRESENT = new Object();
        
        public boolean add(E e) {
            return map.put(e, PRESENT) == null;
        }
        public boolean contains(Object o) {
            return map.containsKey(o);
        }
        public boolean remove(Object o) {
            return map.remove(o) == PRESENT;
        }
    }

Set接口并不保证有序，而SortedSet接口则保证元素是有序的：

*  HashSet是无序不重复集合，因为它实现了Set接口，并没有实现SortedSet接口；
 *  TreeSet是有序不重复集合，因为它实现了SortedSet接口。

![在这里插入图片描述][20200219163112462.png]

**使用TreeSet和使用TreeMap的要求一样，添加的元素必须正确实现Comparable接口，如果没有实现Comparable接口，那么创建TreeSet时必须传入一个Comparator对象**。自然，String和Integer类已经在内部实现了该接口。

### Queue ###

队列（Queue）是一种经常使用的集合。Queue实际上是实现了一个先进先出（FIFO：First In First Out）的有序表。它和List的区别在于，List可以在任意位置添加和删除元素，而Queue只有两个操作：

*  把元素添加到队列末尾；
 *  从队列头部取出元素。

在Java的标准库中，队列接口Queue定义了以下几个方法：

*  int size()：获取队列长度；
 *  boolean add(E)/boolean offer(E)：添加元素到队尾；
 *  E remove()/E poll()：获取队首元素并从队列中删除；
 *  E element()/E peek()：获取队首元素但并不从队列中删除。

对于具体的实现类，有的Queue有最大队列长度限制，有的Queue没有。注意到添加、删除和获取队列元素总是有两个方法，这是因为在添加或获取元素失败时，这两个方法的行为是不同的。我们用一个表格总结如下：  
![在这里插入图片描述][20200219163956627.png]  
例如：如果我们调用offer()方法来添加元素，当添加失败时，它不会抛异常，而是返回false：  
注意：不要把null添加到队列中，否则poll()方法返回null时，很难确定是取到了null元素还是队列为空。

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    	    ......
    }

从上述代码，我们可以看出，**LinkedList即实现了List接口，又实现了Deque（双向队列，继承自Queue）接口，但是，在使用的时候，如果我们把它当作List，就获取List的引用，如果我们把它当作Queue，就获取Queue的引用**：

// 这是一个List:
    List<String> list = new LinkedList<>();
    // 这是一个Queue:
    Queue<String> queue = new LinkedList<>();
    //这是一个双向队列，Deque是Queue的子类：
    Deque<String> deque = new LinkedList<>();

**始终按照面向抽象编程的原则编写代码，可以大大提高代码的质量**。

### PriorityQueue ###

PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。要使用PriorityQueue，我们就必须给每个元素定义“优先级”。我们以实际代码为例，先看看PriorityQueue的行为：

public class Main {
        public static void main(String[] args) {
            Queue<String> q = new PriorityQueue<>();
            // 添加3个元素到队列:
            q.offer("apple");
            q.offer("pear");
            q.offer("banana");
            System.out.println(q.poll()); // apple
            System.out.println(q.poll()); // banana
            System.out.println(q.poll()); // pear
            System.out.println(q.poll()); // null,因为队列为空
        }
    }

我们放入的顺序是"apple"、“pear”、“banana”，但是取出的顺序却是"apple"、“banana”、“pear”，这是因为从字符串的排序看，"apple"排在最前面，"pear"排在最后面。**因此，放入PriorityQueue的元素，必须实现Comparable接口，PriorityQueue会根据元素的排序顺序决定出队的优先级**。  
如果我们要放入的元素并没有实现Comparable接口怎么办？PriorityQueue允许我们提供一个Comparator对象来判断两个元素的顺序，这个对象的类必须实现Comparable接口，再或者也可以输入一个Lambda表达式。

### Deque ###

如果把条件放松一下，允许两头都进，两头都出，这种队列叫双向队列（Double Ended Queue），学名Deque。  
Java集合提供了接口Deque来实现一个双端队列，它的功能是：

*  既可以添加到队尾，也可以添加到队首；
 *  既可以从队首获取，又可以从队尾获取。  
    我们来比较一下Queue和Deque出队和入队的方法：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 7]  
    对于添加元素到队尾的操作，Queue提供了add()/offer()方法，而Deque提供了addLast()/offerLast()方法。添加元素到对首、取队尾元素的操作在Queue中不存在，在Deque中由addFirst()/removeLast()等方法提供。  
    意到Deque接口实际上扩展自Queue：

public interface Deque<E> extends Queue<E> {
        ...
    }

因此，Queue提供的add()/offer()方法在Deque中也可以使用，但是，使用Deque，最好不要调用offer()，而是调用offerLast()，offer()实际上是offerLast()，我们明确地写上offerLast()，不需要思考就能一眼看出这是添加到队尾。  
**Deque是一个接口，它的实现类有ArrayDeque和LinkedList**。  
我们发现LinkedList真是一个全能选手，它即是List，又是Queue，还是Deque。**但是我们在使用的时候，总是用特定的接口来引用它，这是因为持有接口说明代码的抽象层次更高，而且接口本身定义的方法代表了特定的用途**。

// 不推荐的写法:
    LinkedList<String> linkedList = new LinkedList<>();
    // 推荐的写法：
    List<String> list = new LinkedList<>();
    Queue<String> queue = new LinkedList<>();
    Deque<String> deque = new LinkedList<>();

**可见面向抽象编程的一个原则就是：尽量持有接口，而不是具体的实现类**。

### Stack ###

栈（Stack）是一种后进先出（LIFO：Last In First Out）的数据结构。  
Stack只有入栈和出栈的操作：

*  把元素压栈：push(E)；
 *  把栈顶的元素“弹出”：pop(E)；
 *  取栈顶元素但不弹出：peek(E)。

在Java中，我们用Deque可以实现Stack的功能：

*  把元素压栈：push(E)/addFirst(E)；
 *  把栈顶的元素“弹出”：pop(E)/removeFirst()；
 *  取栈顶元素但不弹出：peek(E)/peekFirst()。

为什么Java的集合类没有单独的Stack接口呢？因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来“模拟”一个Stack了，并且现在不推荐使用Stack类了。当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。  
**为什么现在不建议遗留类Stack呢，因为如下代码所示，Stack继承自Vector集合，Vector性能不佳，且有更好的代替类，Vector已不推荐使用，故Stack也不推荐使用**。

public class Stack<E> extends Vector<E> {
    	......
    }

### Iterator ###

Java的集合类都可以使用for each循环，List、Set和Queue会迭代每个元素，Map会迭代每个key。以List为例：

List<String> list = List.of("Apple", "Orange", "Pear");
    for (String s : list) {
        System.out.println(s);
    }

实际上，Java编译器并不知道如何遍历List。上述代码能够编译通过，只是因为编译器把for each循环通过Iterator改写为了普通的for循环：

for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
         String s = it.next();
         System.out.println(s);
    }

我们把这种通过Iterator对象遍历集合的模式称为迭代器。使用迭代器的好处在于，调用方总是以统一的方式遍历各种集合类型，而不必关系它们内部的存储结构。Iterator对象是集合对象自己在内部创建的，它自己知道如何高效遍历内部的数据集合，调用方则获得了统一的代码，编译器才能把标准的for each循环自动转换为Iterator遍历。  
如果我们自己编写了一个集合类，想要使用for each循环，只需满足以下条件：

*  集合类实现Iterable接口，该接口要求返回一个Iterator对象；
 *  用Iterator对象迭代集合内部数据。

这里的关键在于，**集合类通过调用iterator()方法，返回一个Iterator对象，这个对象必须自己知道如何遍历该集合，这样对不同的集合，我们可以使用同样的调用方法，让集合本身去关心怎么样遍历自己**。  
在编写Iterator的时候，我们通常可以用一个内部类来实现Iterator接口，这个内部类可以直接访问对应的外部类的所有字段和方法。  
还有一点要注意，**使用foreach循环(Iterable)时，不能在循环体中，用集合的增删操作，例如：list.remove(x)，这样会报java.util.ConcurrentModificationException异常，因为，这样相当并发修改了集合，进而影响了Iterator的游标值，所以才报了异常**，如果你要删除，新起一个迭代器就好，类似于

Iterator iterable = arrayList.iterator();
            while (iterable.hasNext()) {
                if (iterable.next().equals("B")) {
                    iterable.remove();
                }
            }

### Collections ###

**Collections是JDK提供的工具类，注意Collections结尾多了一个s，不是Collection！同样位于java.util包中。它提供了一系列静态方法，能更方便地操作各种集合**。

#### 创建空集合 ####

Collections提供了一系列方法来创建空集合：

*  创建空List：List emptyList()
 *  创建空Map：Map<K, V> emptyMap()
 *  创建空Set：Set emptySet()

**要注意到返回的空集合是不可变集合，无法向其中添加或删除元素**，此外，也可以用各个集合接口提供的of(T…)方法创建空集合。例如，以下创建空List的两个方法是等价的：

List<String> list1 = List.of();
    List<String> list2 = Collections.emptyList();

#### 创建单元素集合 ####

Collections提供了一系列方法来创建一个单元素集合：

创建一个元素的List：List<T> singletonList(T o)
    创建一个元素的Map：Map<K, V> singletonMap(K key, V value)
    创建一个元素的Set：Set<T> singleton(T o)

要注意到返回的单元素集合也是不可变集合，无法向其中添加或删除元素。此外，也可以用各个集合接口提供的of(T…)方法创建单元素集合。例如，以下创建单元素List的两个方法是等价的：

List<String> list1 = List.of("apple");
    List<String> list2 = Collections.singleton("apple");

实际上，使用List.of(T…)更方便，因为它既可以创建空集合，也可以创建单元素集合，还可以创建任意个元素的集合

#### 排序 ####

Collections可以对List进行排序。因为排序会直接修改List元素的位置，因此必须传入可变List

public class Main {
        public static void main(String[] args) {
            List<String> list = new ArrayList<>();
            list.add("apple");
            list.add("pear");
            list.add("orange");
            // 排序前:
            System.out.println(list);
            Collections.sort(list);
            // 排序后:
            System.out.println(list);
        }
    }

#### 洗牌 ####

Collections提供了洗牌算法，即传入一个有序的List，可以随机打乱List内部元素的顺序，效果相当于让计算机洗牌:

public class Main {
        public static void main(String[] args) {
            List<Integer> list = new ArrayList<>();
            for (int i=0; i<10; i++) {
                list.add(i);
            }
            // 洗牌前:
            System.out.println(list);
            Collections.shuffle(list);
            // 洗牌后:
            System.out.println(list);
        }
    }

#### 不可变集合 ####

Collections还提供了一组方法把可变集合封装成不可变集合：

*  封装成不可变List：List unmodifiableList(List<? extends T> list)
 *  封装成不可变Set：Set unmodifiableSet(Set<? extends T> set)
 *  封装成不可变Map：Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m)

这种封装实际上是通过创建一个代理对象，拦截掉所有修改方法实现的。

#### 线程安全集合 ####

Collections还提供了一组方法，可以把线程不安全的集合变为线程安全的集合:

*  变为线程安全的List：List synchronizedList(List list)
 *  变为线程安全的Set：Set synchronizedSet(Set s)
 *  变为线程安全的Map：Map<K,V> synchronizedMap(Map<K,V> m)

它的实现原理实际上，只是给原来的集合加上synchronized锁而已，性能不佳，再加之从Java 5开始，引入了更高效的并发集合类**java.util.concurrent**，所以上述这几个同步方法已经没有什么用了

### 遗留的集合 ###

从 Java 第 1 版问世以来， 在集合框架出现之前已经存在大量“ 遗留的” 容器类，这些类已经集成到集合框架中，已变的不好删除或修改，前面也提到一些，这里总结一下，如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 8]  
主要包括有Vector、Stack、Hashtable、Properties(感觉还可以用一下)、Enumeration接口、BitSet，至于为什么不再推荐使用，无非三个方面一、可能不安全。例如，Stack还可以用Vector的方法。二、性能不佳，方法不尽人意，例如Vector与Hashtable。三、有更好的代替，例如Enumeration接口被Iterator接口代替！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020021919165757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200219191823690.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200219193557436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200219193616954.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200218140659817.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200218181031258.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200218185941437.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5,size_16,color_FFFFFF,t_70
[20200219141019530.png]: https://img-blog.csdnimg.cn/20200219141019530.png
[20200219163112462.png]: https://img-blog.csdnimg.cn/20200219163112462.png
[20200219163956627.png]: https://img-blog.csdnimg.cn/20200219163956627.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200219165959660.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200220150043776.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMTM2NDM5,size_16,color_FFFFFF,t_70