Collection

Collection
Java标准库自带的java.util包提供了集合类：Collection，它是除Map外所有其他集合类的根接口。Java的java.util包主要提供了以下三种类型的集合：

• List：一种有序列表的集合，例如，按索引排列的Student的List；
• Set：一种保证没有重复元素的集合，例如，所有无重复名称的Student的Set；
• Map：一种通过键值（key-value）查找的映射表集合，例如，根据Student的name查找对应Student的Map。

Java集合的设计有几个特点：一是实现了接口和实现类相分离，，例如，有序表的接口是List，具体的实现类有ArrayList，LinkedList等，二是支持泛型，我们可以限制在一个集合中只能放入同一种数据类型的元素，例如：

List<String> list = new ArrayList<>(); // 只能放入String类型

Java访问集合总是通过统一的方式——迭代器（Iterator）来实现

有一小部分集合类是遗留类，不应该继续使用：

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

还有一小部分接口是遗留接口，也不应该继续使用：
Enumeration：已被Iterator取代。

使用List

• ArrayList：基于动态数组实现，支持随机访问。

• Vector：和 ArrayList 类似，但它是线程安全的。

• LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

List接口，可以看到几个主要的接口方法：

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

但是，实现List接口并非只能通过数组（即ArrayList的实现方式）来实现，另一种LinkedList通过“链表”也实现了List接口。在LinkedList中，它的内部每个元素都指向下一个元素：

比较一下ArrayList和LinkedList：

通常情况下，我们总是优先使用ArrayList。

List的特点

• 允许添加重复的元素
• 允许添加null

创建List

除了使用ArrayList和LinkedList，(new ArrayList)我们还可以通过List接口提供的of()方法，根据给定元素快速创建List：

List<Integer> list = List.of(1, 2, 5);

遍历List

• 使用for循环根据索引配合get(i)方法遍历
  不推荐，get方法只有ArrayList的实现时高效的，LinkedList访问速度慢。
• 坚持使用迭代器Iterator来访问List
  Iterator对象有两个方法：boolean hasNext()判断是否有下一个元素，E next()返回下一个元素。因此，使用Iterator遍历List代码如下：

import java.util.Iterator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = List.of("apple", "pear", "banana");
        for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
            String s = it.next();
            System.out.println(s);
        }
    }
}

• for each循环本身就可以帮我们使用Iterator——最常见

import java.util.List;

public class Main {
	public static void main(String[] args){
		List<String> list = List.of("apple","pear","banana");
		for (String s : list) {
			System.out.println(s);
		}
	}
}

List和Array转换

List——>Array

• 调用toArray()方法，直接返回一个Object[]数组——会丢失类型信息，很少应用

import java.util.List;

public class Main {
	public static void main(String[] args){
		List<String> list = List.of("apple","pear","banana");
		Object[] array = list.toArray();
		for(Object s : array){
			System.out.println(s);
		}
	}
}

• 给toArray(T[])传入一个类型相同的Array，List内部自动把元素复制到传入的Array中：

import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = List.of(12, 34, 56);
        Integer[] array = list.toArray(new Integer[3]);
        for (Integer n : array) {
            System.out.println(n);
        }
    }
}

toArray(T[])方法的泛型参数并不是List接口定义的泛型参数，所以，我们实际上可以传入其他类型的数组，例如我们传入Number类型的数组，返回的仍然是Number类型.

实际上，最常用的是传入一个“恰好”大小的数组：

Integer[] array = list.toArray(new Integer[list.size()]);

• 通过List接口定义的T[] toArray(IntFunction<T[]> generator)方法：
  Integer[] array = list.toArray(Integer[]::new);

Array——>List

通过List.of(T…)方法最简单：

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

返回的List不一定就是ArrayList或者LinkedList，因为List只是一个接口，如果我们调用List.of()，它返回的是一个只读List（无法使用add方法等）

编写equals方法

List还提供了boolean contains(Object o)方法来判断List是否包含某个指定元素。此外，int indexOf(Object o)方法可以返回某个元素的索引，如果元素不存在，就返回-1。

String、Integer这些类已经实现了equals()方法，对于我们自定义的类一定要注意覆写equals()方法
例如对于Person类，如果name相等，并且age相等，我们就认为两个Person实例相等。

public boolean equals(Object o) {
    if (o instanceof Person) {
        Person p = (Person) o;
        return Objects.equals(this.name, p.name) && this.age == p.age;
    }
    return false;
}

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

先确定实例“相等”的逻辑，即哪些字段相等，就认为实例相等；
用instanceof判断传入的待比较的Object是不是当前类型，如果是，继续比较，否则，返回false；
对引用类型用Objects.equals()比较，对基本类型直接用==比较。
使用Objects.equals()比较两个引用类型是否相等的目的是省去了判断null的麻烦。两个引用类型都是null时它们也是相等的。

如果不调用List的contains()、indexOf()这些方法，那么放入的元素就不需要实现equals()方法。

使用Map

Map这种键值（key-value）映射表的数据结构，作用就是能高效通过key快速查找value（元素）

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

public class Main {
	public static void main(String[] args) {
		Student s = new Student("xiao ming",99);
		Map<String, Student> map = new HashMap<>();
		map.put("xiao ming",s);
		Student target = map.get("xiao ming");
        System.out.println(target == s); // true，同一个实例
        System.out.println(target.score); // 99
        Student another = map.get("Bob"); // 通过另一个key查找
        System.out.println(another); // 未找到返回null
	}
}


class Student {
	public String name;
	public int score;
	public Student(String name, int score){
		this.name = name;
		this.score = score;
	}
}

遍历Map

• 遍历key，使用for each循环遍历Map实例的keySet()方法返回的Set集合

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

public class Main {
    public static void main(String[] args) {
		Map<String, Integer> map = new HashMap<>();
		map.put("apple", 123);
		map.put("pear", 456);
		map.put("banana", 789);
		for(String key : map.keySet()){
			Integer value = map.get(key);
			System.out.println(key + "=" + value);
		}
    }
}

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 123);
        map.put("pear", 456);
        map.put("banana", 789);
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key + " = " + value);
        }
    }
}

遍历Map的时候不保证按照put的顺序遍历。

使用EnumMap

HashMap通过对key计算hashcode(),通过空间换时间的方式，定位到value所在内部数组的索引，因此，查找效率很高。
Map中key的对象是enum类型，可以使用EnumMap，根据enum可以直接定位到内部数组的索引，不需要计算hashcode()。
使用EnumMap的时候，我们总是用Map接口来引用它(开发原则，接口引用，不关心具体子类型)，因此，实际上把HashMap和EnumMap互换，在客户端看来没有任何区别。

使用TreeMap

TreeMap是 SortMap接口（内部会对key排序）的实现类。
SortedMap保证遍历时以Key的顺序来进行排序。例如，放入的Key是"apple"、“pear”、“orange”，遍历的顺序一定是"apple"、“orange”、“pear”，因为String默认按字母排序。
所以放入的Key必须实现comparable接口（你得能比较排序吧），String、Integer已经实现了comparable接口，可以直接作为Key。如果作为Key的class没有实现comparable接口，那么在创建TreeMap是要指定自定义排序算法：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
		public int compare(Student p1, Student p2) {
    		if (p1.score == p2.score) {
        		return 0;
    		}
    	return p1.score > p2.score ? -1 : 1;
		}
        });
        map.put(new Person("Tom"), 1);
        map.put(new Person("Bob"), 2);
        map.put(new Person("Lily"), 3);
        for (Person key : map.keySet()) {
            System.out.println(key);
        }
        // {Person: Bob}, {Person: Lily}, {Person: Tom}
        System.out.println(map.get(new Person("Bob"))); // 2
    }
}

class Person {
    public String name;
    Person(String name) {
        this.name = name;
    }
    public String toString() {
        return "{Person: " + name + "}";
    }
}

SortedMap在遍历时严格按照Key的顺序遍历，最常用的实现类是TreeMap；

作为SortedMap的Key必须实现Comparable接口，或者传入Comparator；

要严格按照compare()规范实现比较逻辑，否则，TreeMap将不能正常工作。

使用Properties(没学好，日后填坑)

Java集合库提供的Properties用于读写配置文件.properties。.properties文件可以使用UTF-8编码。

可以从文件系统、classpath或其他任何地方读取.properties文件。

读写Properties时，注意仅使用getProperty()和setProperty()方法，不要调用继承而来的get()和put()等方法。

使用Set

Map用于存储key-value的映射，对于充当key的对象不能重复，并且，不但需要正确覆写equals()方法，还要正确覆写hashCode()方法。

Set用于存储不重复的元素集合，它主要提供以下几个方法：

将元素添加进Set：boolean add(E e)
将元素从Set删除：boolean remove(Object e)
判断是否包含元素：boolean contains(Object e)
Set<String> set = new HashSet<>();

Set相当于只存储key、不存储value的Map。Set经常用于去除重复元素。
放入Set的元素和Map的key类似，都要正确实现equals()和hashCode()方法，否则该元素无法正确地放入Set。
最常用的Set实现类是HashSet
Set接口并不保证有序，而SortedSet接口则保证元素是有序的：
HashSet是无序的，因为它实现了Set接口，并没有实现SortedSet接口；
TreeSet是有序的，因为它实现了SortedSet接口。

使用TreeSet和使用TreeMap的要求一样，添加的元素必须正确实现Comparable接口，如果没有实现Comparable接口，那么创建TreeSet时必须传入一个Comparator对象。

使用Queue

队列——先进先出（小孩排队）的有序表
特点：

• 队尾添加元素
• 队头取元素

队列接口Queue定义了以下几个方法：

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

LinkedList即实现了List接口，又实现了Queue接口，但是，在使用的时候，如果我们把它当作List，就获取List的引用，如果我们把它当作Queue，就获取Queue的引用：

// 这是一个List:
List<String> list = new LinkedList<>();
// 这是一个Queue:
Queue<String> queue = new LinkedList<>();

使用PriorityQueue

优先级队列——“VIP插队”
PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。
入PriorityQueue的元素，必须实现Comparable接口，PriorityQueue会根据元素的排序顺序决定出队的优先级。

PriorityQueue默认按元素比较的顺序排序（必须实现Comparable接口），也可以通过Comparator自定义排序算法（元素就不必实现Comparable接口）。

使用Deque

允许两头进两头出——双端队列Deque
Deque是一个接口，它的实现类有ArrayDeque和LinkedList。

使用Stack

先进后出（箱子取苹果）——栈
在Java中，我们用Deque可以实现Stack的功能：

把元素压栈：push(E)/addFirst(E)；
把栈顶的元素“弹出”：pop(E)/removeFirst()；
取栈顶元素但不弹出：peek(E)/peekFirst()。
当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。

方法调用栈

JVM在处理Java方法调用的时候就会通过栈这种数据结构维护方法调用的层次。
每调用一个方法时，先将参数压栈，然后执行对应的方法；当方法返回时，返回值压栈，调用方法通过出栈操作获得方法返回值。

因为方法调用栈有容量限制，嵌套调用过多会造成栈溢出，即引发StackOverflowError

整数进制转换

例如将int整数转换为十六进制表示的字符串
不断用商/16，将余数压栈，当商是0时，计算结束，弹出栈所有元素组成字符串。

计算中缀表达式

这部分数据结构的知识，很简单
编译器将中缀表达式转换为后缀表达式，这个过程就用到栈。计算过程：遇到操作数压栈，遇到运算符弹出栈顶元素，计算完成后再将结果压栈。

使用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);
}

实际上，编译器把for each循环通过Iterator改写成了普通的for循环：

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

在编写Iterator的时候，我们通常可以用一个内部类来实现Iterator接口，这个内部类可以直接访问对应的外部类的所有字段和方法。
Iterator是一种抽象的数据访问模型。使用Iterator模式进行迭代的好处有：

对任何集合都采用同一种访问模型；
调用者对集合内部结构一无所知；
集合类返回的Iterator对象知道如何迭代。
Java提供了标准的迭代器模型，即集合类实现java.util.Iterable接口，返回java.util.Iterator实例。

使用Collections

Collections类提供了一组工具方法（一些列静态方法）来方便使用集合类：

创建空集合；
创建单元素集合；
创建不可变集合；
排序／洗牌等操作。