1 Java集合
1.1 Java集合的简介
1.基本说明
-
定义：
一个Java对象可以在内部持有若干其他对象，并对外提供访问接口，将这种Java对象称之为集合。
这些对象可以是基本的数据类型也可以是引用类型。
-
主要的Java集合：
java.util提供了集合类，包括：
Collection：根接口
List：有序列表，一种线性ADT
Set：无重复元素集合（这个set就是数学中的集合，与Java中所定义的集合意思不同）
Map：通过Key查找Value的映射表 Queue：队列，也是一种线性ADT，遵循先进先出的规则，即FIFO
-
集合之间的关系
如下图所示，图片来自于《码出高效》。
从图中可以看出List、Queue、Set和Map实现了Collection接口，图中黑体加粗的是目前常用的几种集合的具体实现。
主要有如下表所示的几类：
从该表中可以看出每种集合的几个具体实现，同时也给出了每个具体实现其底层的数据结构。比如List的一个实现，ArrayList就是基于数组的，LinkedList是基于链表的（更准确一点是双向链表）。
Java集合支持泛型，通过迭代器（Iterator）访问集合。**如下图所示：
1.2 List
1.基本说明
-
List方法
List是一种有序列表，通过索引访问元素，例如List.get(index)
1.list.add(E) 在末尾添加一个元素
2.list.add(int index，E) 在指定索引添加一个元素
3.list.remove(int index) 删除指定索引的元素
4.list.remove(Object e) 删除某个元素
5.list.get(int index) 获取指定索引的元素
6.list.size() 获取链表大小（包含元素的个数） -
List有ArrayList和LinkedList两种实现。
ArrayList的内部是使用数组进行存储，ArrayList是容量可以改变的非线程安全集合，其默认的容量是10，在容量不够时会自动扩容，其扩容的方式是容量的进行向右移位。ArrayList的随机访问速度很快，但是其插入和删除通常很慢，这是由其底层的数据结构决定的。
LinkedList的内部是使用双向链表进行存储，由于其采用的是双链表，所以不存在扩容的问题，而且内存的利用率也较高。其插入和删除通常快于ArrayList，但是访问元素的速度很慢。
-
遍历List使用Iterator或者foreach循环。
-
List和Array可以相互转换。数组是一种顺序表，在Java中，数组用于存储统一类型的对象，且一旦分配内存之后无法扩容。Arrays是针对数组对象进行操作的工具类，包括数组的排序、查找、对比和拷贝等。使用Arrays中的Arrays.asList()方法可以将数组转化成List,但是转成的List仅仅能够使用set,而无法使用add/remove/clear等一系列会改变List长度的方法，这是因为这个转化并不是完全的，而是新生成的Arrays的ArrayList内部类。相对于数组转集合而言，集合转数组更加可控，使用的方法是List中的toArray方法，需要注意的是：①不要使用toArray的无参方式，这样会导致泛型丢失（直接转化成了Object）②数组的容量必须≥代转化List中的容量。
-
集合与泛型
使用泛型的好处是不言而喻的，①类型安全，设置的是什么类型，取出的一定是这个类型；②代码重用
在集合中使用泛型，有一个常见的问题是：如何分清List、List、List<?>、List<? extents T>和List<? super T>
List与List是不一样的，List可以接受其他泛型的赋值，List是不可以的，因为集合不具有协变性。
List<?>可以接受任何类型的赋值，但不能添加任何元素，可以remove和clear。
为了防止多种泛型，extents T 表示可以赋值给任何T及其子类的集合，super T表示可以赋值给任何T及其父类的集合。前者是“getfirst”，主要用于消费集合元素的场合；后者是“putfirst”，主要用于生产集合元素的场合。
2.基本操作
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] args) {
//新建ArrayList，并往里面添加元素
List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Pear");
list.add("Orange");
for (String l : list) {
System.out.println(l);
}
System.out.println(list.get(0));
System.out.println(list.getClass());
//将ArrayList转化成Arrays
String[] ss = list.toArray(new String[list.size()]);
System.out.println(Arrays.toString(ss));
System.out.println(ss.getClass());
//将Arrays转化成ArrayList
List<String> list0 = new ArrayList<>(Arrays.asList(ss));
for (String l : list0) {
System.out.println(l);
}
System.out.println(list0.getClass());
}
}
//输出结果
/* Apple Pear Orange Apple class java.util.ArrayList [Apple, Pear, Orange] class [Ljava.lang.String; Apple Pear Orange class java.util.ArrayList */
1.3 Map
1.基本说明
-
Map是一种键值映射表，可以通过Key快速查找Value
常用方法：
1.put(K key, V value)：把Key-Value放入Map
2.get(K key)：通过Key获取Value，<mark>要点</mark>：在输出value时可能会发现输出是一个栈地址，这个时候需要使用这个栈对应的对象的方法来输出我们想要的值。具体见基本操作代码。
3.boolean containsKey(K key)：判断Key是否存在
遍历Map：
1.用for…each循环：
2.循环Key：keySet()
3.循环Key和Value：entrySet()
常用的实现类：
HashMap：不保证有序
SortedMap：保证按Key排序，默认是从小到大排序，也可以自定义排序的方式为倒序（覆写）。在SortedMap 中主要的实现类有TreeMap -
编写equals和hashcode方法
正确使用Map必须保证：
作为Key的对象必须正确覆写equals()方法
作为Key的对象必须正确覆写hashCode()方法 一般Java已经将String等的覆写已经实现了。
覆写hashCode：
如果两个对象相等，则两个对象的hashCode()必须相等
如果两个对象不相等，则两个对象的hashCode()尽量不相等（可以相等，会造成效率下降）
hashCode可以通过Objects.hashCode()辅助方法实现
2.基本操作
-
自定义Map
//Main.java import com.sun.javafx.collections.MappingChange; import java.util.*; public class Main { public static void main(String[] args) { List<Person> list1 = new ArrayList<>(Arrays.asList(new Person("Ming", 12), new Person("Jun", 18), new Person("Hong", 20)));//定义了一个元素均为Person对象的List。 Map<String, Person> map = new TreeMap<>(new Comparator<String>() { //这里覆写了TreeMap中的compare方法，使正序转化成倒序 @Override public int compare(String o1, String o2) { return - o1.compareTo(o2); } }); for (Person p : list1) {//将List中的元素以键值对的方式存入一个Map map.put(p.getName(), p); } System.out.println(map.get("Jun"));//get（）返回键对应的值 System.out.println(map); //使用entrySet（）同时遍历键和值 for (Map.Entry<String, Person> entry : map.entrySet()) { String key = entry.getKey(); Person value = entry.getValue(); System.out.println("key=" + key + ", value=" + value.getName() + "," + value.getAge());//这里不能直接输出value } //在Person类中覆写了equals方法和hashcode方式，从而下面这个句子可以正常执行。否则会输出null。 System.out.println(map.get(new String("Jun"))); } } //Person.class import java.util.Objects; public class Person { public String name;//定义字段 public int 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() {//覆写了hashcode方法 return Objects.hash(this.name, this.age); } @Override public boolean equals(Object obj) {//覆写了equals方法 if (obj == this) { return true; } if (obj instanceof Person) { Person p = (Person) obj;//现将要比较的对象强制转化成Person对象 return Objects.equals(this.name, p.name) && this.age == p.age; } return false; } public Person(String name, int age) { this.name = name; this.age = age; } } //输出结果 /* Person@236bd0//key是“Jun” {Ming=Person@46e79f8, Jun=Person@236bd0, Hong=Person@42abeb5} key=Ming, value=Ming,12 key=Jun, value=Jun,18 key=Hong, value=Hong,20 Person@236bd0//如果value是一个对象，直接输出会是一个栈地址 */
1.4 Set
1.基本说明
-
Set
Set用于存储不重复的元素集合：
1.boolean add(E e)
2.boolean remove(Object o)
3.boolean contains(Object o)
4.int size()
利用Set可以去除重复元素
放入Set的元素要正确实现equals()和hashCode()，所以需要像Map一样给对象覆写这两个方法。
Set不保证有序：
HashSet是无序的
TreeSet是有序的 同样的我们也可以像Map那样自定义排序的顺序
实现了SortedSet接口的是有序Set。
2.基本操作
-
set的实现
import java.util.*; public class Main { public static void main(String[] args) { List<String> list2 = Arrays.asList("Apple", "Peach", "Orange", "Banana", "Apple"); List<String> list3 = removeDuplicate(list2); System.out.println(list3); } static List<String> removeDuplicate(List<String> list) { Set<String> set = new HashSet<>(list);//使用TreeSet会自动排序，同时也可以在这个地方覆写排序方式。 return new ArrayList<String>(set); } } //输出结果 /* [Apple, Peach, Orange, Banana] */
1.5 Queue
1.基本说明
-
Queue
队列（Queue）是一种先进先出（FIFO）的数据结构
实现类：ArrayDeque，LinkedList
操作Queue的元素的方法：
添加至队尾压栈：add() / offer()
获取队列头部元素并删除：E remove() / E poll()
获取队列头部元素但不删除：E element() / E peek()
两组方法的区别：是否抛出Exception，前面的抛出异常，后面的给出true和false。
避免把null添加到队列使用E isEmpty（）来判断queue是否为空。
-
PriorityQueue
PriorityQueue的出队顺序与元素的优先级有关：
从队首获取元素时，总是获取优先级最高的元素
默认按元素比较的顺序排序（必须实现Comparable接口），需要自己在元素所在类中覆写。
可以通过Comparator自定义排序算法（不必实现Comparable接口） -
Deque
Deque的实现类：ArrayDeque和LinkedList
Deque实现一个双端队列（Double Ended Queue）：
既可以添加到队尾，也可以添加到队首
既可以从队首获取，又可以从队尾获取
添加元素到队尾：addLast(E e) / offerLast(E e)
取队首元素并删除：E removeFirst() / E pollFirst()
取队首元素但不删除：E getFirst() / E peekFirst()
总是调用xxxFirst / xxxLast以便与Queue的方法区分开
2.基本操作
-
PriorityQueue在类中覆写优先级
//Main.class import java.util.*; public class Main { public static void main(String[] args) { Queue<Person> queue = new PriorityQueue<>(); queue.offer(new Person("Ming", 12)); queue.offer(new Person("Hong", 23)); queue.offer(new Person("Jun", 18)); System.out.println(queue.poll().getName()); System.out.println(queue.poll().getName()); System.out.println(queue.poll().getName()); } } //Person.class import java.util.Objects; public class Person implements Comparable<Person> { public String name; public int 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; } public Person(String name, int age) { this.name = name; this.age = age; } @Override public int compareTo(Person o) { return this.name.compareTo(o.name);//覆写compareTo方法实现优先级，这里是根据名字来比较大小 } } //输出结果 /* Hong Jun Ming */ -
在PriorityQueue中定义优先级
//Main.class import java.util.*; public class Main { public static void main(String[] args) { Queue<Person> queue = new PriorityQueue<>(new Comparator<Person>() {//在PriorityQueue中定义优先级 @Override public int compare(Person o1, Person o2) { return o1.getName().compareTo(o2.getName()); } }); queue.offer(new Person("Ming", 12)); queue.offer(new Person("Hong", 23)); queue.offer(new Person("Jun", 18)); System.out.println(queue.poll().getName()); System.out.println(queue.poll().getName()); System.out.println(queue.poll().getName()); } } //Person.class import java.util.Objects; public class Person implements Comparable<Person> { public String name; public int 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; } public Person(String name, int age) { this.name = name; this.age = age; }
//输出结果
/*
Hong
Jun
Ming
*/
1.6.6 Stack
1.基本说明
-
Stack
栈（Stack）是一种后进先出（LIFO）的数据结构
操作栈的元素的方法： push(E e)：压栈 pop()：出栈* peek()：取栈顶元素但不出栈
Java使用Deque实现栈的功能，注意只调用push/pop/peek，避免调用Deque的其他方法 -
Collections
Collections是一个工具类，而上面这些Map、List等是Java提供的接口，是两个完全不同的额概念。
Collections是JDK提供的集合工具类，从而方便集合（Collection）的使用。
创建空集合：emptyList / emptySet / emptyMap
创建单元素集合：singleton / singletonList / singletonMap
对List排序：sort
洗牌：suffle
创建不可变集合：unmodifiableList / unmodifiableSet / unmodifiableMap
京公网安备 11010502036488号