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