11. 集合
一、Java集合框架概述
??Java集合可分为Collection和Map两种体系
- Collection接口：单列数据，定义了存取一组对象的方法的集合
- List接口：元素有序、可重复的集合
- ArrayList：线程不安全，效率高，底层使用Object[]存储
- LinkedList：底层使用双向链表存储
- Vector：线程安全，效率低，底层使用Object[]存储
- Set接口：元素无序、不可重复的数据
- HashSet：线程不安全，可以存储null值，底层使用数组+链表存储
- LinkedHashSet：遍历其内部数据时，可以按照添加的顺序遍历，底层使用数组+双向链表存储
- TreeSet：可以按照添加对象的指定属性，进行排序，底层使用红黑树存储
- HashSet：线程不安全，可以存储null值，底层使用数组+链表存储
- List接口：元素有序、可重复的集合
- Map接口：双列数据，保存具有映射关系“key-value”对的集合
- HashMap：线程不安全，效率高，可以存储null的key和value，底层使用数组+链表+红黑树
- LinkedHashMap：遍历其内部数据时，可以按照添加的顺序遍历，在原有的HashMap底层结构基础上，添加一对指针，指向前一个和后一个元素
- TreeMap：按照添加的key-value对进行排序，实现排序遍历，底层使用红黑树，此时考虑key的自然排序或定制排序
- Hashtable：线程安全，效率低，不能存储null的key和value
- Properties：key和value都是String，常用于处理配置文件
- Properties：key和value都是String，常用于处理配置文件
- HashMap：线程不安全，效率高，可以存储null的key和value，底层使用数组+链表+红黑树
二、Collection接口
2.1、Collection接口常用方法
boolean add(E e) //将元素e添加到集合中
int size() //获取元素的个数
boolean addAll(Collection<? extends E> c) //将一个集合添加到另一个集合中
boolean isEmpty() //判断当前集合是否为空
void clear() //清空当前集合元素
boolean contains(Object object) //判断当前集合是否包含object
boolean containsAll(Collection<?> coll) //判断形参coll中的所有元素是否都存在当前集合中
boolean remove(Object object) //将指定元素从当前集合中移除
boolean containsAll(Collection<?> coll) //从当前集合中移除coll中所有的元素
boolean retainAll(Collection<?> coll) //获取当前集合和coll集合的交集，并返回给当前集合
boolean equals(Object object) //判断两个集合是否相等
int hashCode() //返回当前对象的哈希值
Object[] toArray() //将指定集合转换成数组
Iterator iterator() //返回Iterator接口的实例，用于遍历集合元素
2.2、Iterator迭代器接口
??Iterator对象称为迭代器，主要用于遍历Collection集合中的元素。Collection接口继承了java.lang.Iterable接口，该接口有一个iterator()，那么实现了Collection接口的集合类都有一个iterator()，用以返回一个实现了Iterator接口的对象。Iterator仅用于遍历集合，Iterator本身并不具有承装对象的能力，如果需要创建Iterator对象，则必须有一个被迭代的集合。集合对象每次调用iterator()都会得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。
2.2.1、Iterator接口的常用方法
boolean hasNext() //判断是否还有下一个元素
E next() //指针下移，将下移以后集合位置上的元素返回
default void remove() //在遍历时，删除集合中的元素
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class CollectionTest {
public static void main(String[] args) {
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("sakura"));
coll.add(true);
coll.add(new String("kinomoto"));
//如果还未调用next()或上一次调用next()之后已经调用remove()，在调用remove()会报IllegalStateException
Iterator iterator = coll.iterator();
while(iterator.hasNext()){
Object object = iterator.next();
if("sakura".equals(object)){
iterator.remove();
}
}
for (Object object : coll) {
System.out.println(object);
}
}
}
2.3、List接口
??List集合类中元素有序，且可重复，集合中的每个元素都有其对应的顺序索引。List容器中的元素都对应一个整数型的记号记载其在容器中的位置，可以根据序号存取容器中的元素。
??JDK API 中 List 接口的实现类常用的有：ArrayList、LinkList 和 Vector
void add(int index, E element) //在index位置插入element元素
boolean addAll(int index, Collection<? extends E> coll) //从index位置开始将coll中的所有元素添加进来
E get(int index) //获取指定index位置的元素
int indexOf(Object object) //返回object在集合中首次出现的位置
int lastIndexOf(Object object) //返回object在当前集合中末次出现的位置
E remove(int index) //移除指定index位置的元素element
E set(int index, E element) //设置指定index位置的元素为element
List subList(int fromIndex, int toIndex) //返回从formIndex到toIndex位置的子集合
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ListTest {
public static void main(String[] args) {
List list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add("BB");
list.add(456);
System.out.println(list);
list.add(4,"CC");
System.out.println(list);
List list1 = Arrays.asList(1,2,3);
list.addAll(list1);
System.out.println(list.size());
System.out.println(list.get(0));
System.out.println(list.indexOf(456));
System.out.println(list.lastIndexOf(456));
Object object = list.remove(0);
System.out.println(object);
System.out.println(list);
list.set(1, "DD");
System.out.println(list);
List list2 = list.subList(2, 7);
System.out.println(list);
System.out.println(list2);
}
}
2.3.1、ArrayList源码分析
2.3.1.1、JDK 7 及之前的版本源码分析
??ArrayList底层创建了长度是10的Object[] elementData；默认情况下，扩容为原来的1.5倍，同时需要将原有的数组中的数据复制到新的数组中。建议在开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)
2.3.1.2 JDK 8 及之前的版本源码分析
??底层Object[] elementData 初始化为{}，并没有创建长度为10的数组。第一次调用add()时，底层才创建了长度为10的数组，并将数据添加到elementData[0]，后续的添加和扩容操作为 JDK 7 无异。
2.3.2、LinkList源码分析
??内部声明了Node类型的first和last属性，默认值为null；调用add()时，将数据封装到Node中，创建了Node对象；
??其中Node定义为：
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
2.3.3、Vector源码分析
??JDK 7 和 JDK 8 中通过Vector()构造器创建对象时，底层后创建了长度为10的数组。默认扩容为原来数组的2倍；
2.4、Set接口
??Set接口是Collection的子接口，set接口没有提供额外的方法。Set接口不允许包含相同的元素，如果试把两个相同的元素加入同一个Set集合中，则添加失败。Set判断两个对象是否相同不是使用"=="运算符，而是根据equals()。
- 无序性：不等于随机性。存储的数据在底层数组中斌并非按照数组索引的顺序添加，而是根据数据的哈希值确定的
- 不可重复性：保证添加的元素按照equals()判断时，不能返回true，即相同的元素只能添加一个
2.4.1、HashSet
??HashSet按Hash算法来存储集合中的元素，因此具有很好的存储、查找、删除性能。HashSet线程不安全，不能保证元素的排列顺序，集合元素可以是null。HashSet集合通过hashCode()判断两个元素是否相等，并且两个对象的equals()返回值也相等。对于存放在Set容器中的对象，对应类一定要重写equals()和hashCode(Object object)，以便实现对象相等规则，即：“相等的对象必须具有相等的散列码”；
??我们向HashSet中添加元素a，首先调用元素a所在类的hashCode()，计算元素a的哈希值，此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为：索引位置），判断数组此位置上是否已经有元素：
- 如果此位置没有其它元素，则元素a添加成功； --> 情况1
- 如果此位置上有其它元素b（或以链表形式存在的多个元素）， 则比较元素a与元素b的hash值：
- 如果hash值不相同，则元素a添加成功 --> 情况2
- 如果hash值相同，进而需要调用元素a所在类的equals()：
- equals()返回true，元素a添加失败
- equals()返回false，元素a添加成功 --> 情况3
??对于添加成功的情况2和情况3而言：元素a与已经存在指定索引位置上数据以链表的方式存储
- jdk7：元素a方法数组中，指向原来的元素
- jdk8：原来的元素在数组中，指向元素a
2.4.1.1、重写hashCode()的基本规则
- 当程序运行时，同一个对象多次调用hashCode()应该返回相同的值
- 当两个对象的equals()返回true时，这两个对象的hashCode()的返回值也应该相等
- 对象中用作equals()比较的Field，都应该用来计算hashCode值
2.4.1.2、LinkedHashSet
??LinkedHashSet根据元素的hashCode值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。LinkedHashSet插入性能略低于HashSet，但它迭代访问Set里的全部元素时有很好的性能。LinkedHashSet不允许集合元素重复
2.4.2、TreeSet
??TreeSet可以确保集合元素处于排序状态，TreeSet底层使用红黑树结构存储数据。TreeSet有两种排序方法：自然排序和定制排序。默认情况下，TreeSet采用自然排序。向TreeSet添加数据，要求是相同类的对象。
2.4.2.1、TreeSet的自然排序：实现Comparable接口
??自然排序中，比较两个对象是否相同的标准为compareTo()返回0，不再是equals();
import java.util.Iterator;
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
TreeSet treeSet = new TreeSet();
treeSet.add(new User("Sakura",10));
treeSet.add(new User("Mikoto",13));
treeSet.add(new User("Nanoha",7));
treeSet.add(new User("Kagome",15));
treeSet.add(new User("Kikyou",21));
treeSet.add(new User("Sakura",13));
Iterator iterator= treeSet.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
public class User implements Comparable{
private String name;
private int age;
public User(){
}
public User(String name,int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(Object o) {
if(o instanceof User){
User user = (User)o;
int compare = this.name .compareTo(user.name);
if(compare != 0){
return compare;
} else {
return Integer.compare(this.age, user.age);
}
} else {
throw new RuntimeException("输入的类型不匹配");
}
}
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 String toString(){
return "{ name = " + name + ",age = " + age +" }";
}
}
2.4.2.2、TreeSet的定制排序：实现Comparator接口
??自然排序中，比较两个对象是否相同的标准为compare()返回0，不再是equals();
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
Comparator comparator = new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof User && o2 instanceof User){
User u1 = (User)o1;
User u2 = (User)o2;
int compare = Integer.compare(u1.getAge(), u2.getAge());
if(compare != 0){
return compare;
} else {
return u1.getName().compareTo(u2.getName());
}
} else {
throw new RuntimeException("传入参数不匹配！");
}
}
};
TreeSet treeSet = new TreeSet(comparator);
treeSet.add(new User("Sakura",10));
treeSet.add(new User("Mikoto",13));
treeSet.add(new User("Nanoha",7));
treeSet.add(new User("Kagome",13));
treeSet.add(new User("Kikyou",21));
treeSet.add(new User("Sakura",13));
Iterator iterator= treeSet.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
public class User implements Comparable{
private String name;
private int age;
public User(){
}
public User(String name,int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(Object o) {
if(o instanceof User){
User user = (User)o;
int compare = this.name .compareTo(user.name);
if(compare != 0){
return compare;
} else {
return Integer.compare(this.age, user.age);
}
} else {
throw new RuntimeException("输入的类型不匹配");
}
}
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 String toString(){
return "{ name = " + name + ",age = " + age +" }";
}
}
五、Map接口
- Map中的key：无序的、不可重复的、使用Set存储所有的key --> key所在的类要重写equals()和hashCode()
- Map中value：无序的、可重复的、使用Collection存储所有的value
- 一对键值对：key-value构成一个Entry对象
- Map中的entry：无序的、不可重复的
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
public class MapTest {
public static void main(String[] args) {
Map map = new HashMap();
map.put("AA", 123);
map.put("BB", 123);
map.put("CC", 123);
map.put("AA", 27185);
//遍历所有的key集：keySet()
Set set = map.keySet();
Iterator iterator1 = set.iterator();
while(iterator1.hasNext()){
System.out.println(iterator1.next());
}
System.out.println();
//遍历所有的value集：values()
Collection value = map.values();
for (Object object : value) {
System.out.println(object);
}
System.out.println();
//遍历所有的key-value
Set entrySet = map.entrySet();
Iterator iterator2 = entrySet.iterator();
while(iterator2.hasNext()){
Object object = iterator2.next();
Map.Entry entry = (Map.Entry)object;
System.out.println(entry.getKey() + " --> " + entry.getValue());
}
System.out.println();
//遍历所有的key-value
Set keySet = map.keySet();
Iterator iterator3 = keySet.iterator();
while(iterator3.hasNext()){
Object key = iterator3.next();
Object value2 = map.get(key);
System.out.println(key + " : " + value2);
}
}
}
5.1 常用方法
V put(K key, V value) //将指定key-value添加到（或修改）当前map对象中
void putAll(Map<? extends K,? extends V> m) //将m中的所有key-value对存放到当前map中
V remove(Object key) //移除指定key的key-value对，并返回value
void clear() //清空当前map中的所有数据
V get(Object key) //获取指定key对应的value
boolean containsKey(Object key) //是否包含指定的key数据
boolean containsValue(Object value) //是否包含指定的value
int size() //返回map中key-value对的个数
boolean isEmpty() //返回当前map是否为空
boolean equals(Object o) //判断当前map和参数对象o是否相等
Set keySet() //返回所有key构成的Collection集合
Set> entrySet() //返回所有key-value对构成的Set集合
5.2、HashMap
5.2.1、HashMap源码分析
??JDK 7 及之前的版本源码分析在实例化以后，底层创建了长度是16的一维数组Entry[] table。
??当进行添加操作时，首先调用key所在类的hashCode()计算key的哈希值，此哈希值经过么某种算法计算以后，得到在Entry数组中的存放位置：
- 如果此位置上的数据为空，此时key-value添加成功； --> 情况1
- 如果此位置上的数据不为空，比较key和已经存在的一个或多个的哈希值：
- 如果key的哈希值与已经存在的哈希值都不相同，此时key-value添加成功； --> 情况1
- 如果key的哈希值和已经存在的某一个数据的哈希值相同，调用key所在类的equals()比较：
- 如果equals()返回false：此时key-value添加成功 --> 情况1
- 如果equals()返回true：使用当前value替换原有的value值
??关于情况2和情况3，此时的key-value和原来的数据以链表的方式存储;
??在不断的添加过程中，会涉及到扩容问题，当超出临界值且要存放的位置非空时，需要扩容，默认的扩容方式为原来容量的2倍，并将原有的数据复制过来；
jdk 8相较于jsk7在底层实现方面的不同
- 底层没有创建一个长度为16的数组
- jdk 8底层的数组是：Node[]
- 首次调用put()，底层创建长度为16的数组
- jdk 7底层结构只有：数组+链表，jdk 8底层结构：数组+链表+红黑树
- 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64 时，此索引位置上的所有数据改为使用红黑树存储
5.2.2、LinkedHashMap
??内部声明了Entry类型的first和last属性，默认值为null；调用add()时，将数据封装到Entry中，创建了Entry对象；
??其中Entry定义为：
static class Entry extends HashMap.Node {
Entry before, after;
Entry(int hash, K key, V value, Node next) {
super(hash, key, value, next);
}
}
5.3、TreeMap
??TreeMap可以确保集合元素处于排序状态，TreeMap底层使用红黑树结构存储数据。TreeMap有两种排序方法：自然排序和定制排序。默认情况下，TreeMap采用自然排序。向TreeMap添加key-value时，要求key必须是同一个类的对象。
5.3.1、自然排序
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class TreeMapTest {
public static void main(String[] args) {
TreeMap map = new TreeMap();
map.put(new User("Sakura",10), 100);
map.put(new User("Mikoto",13), 97);
map.put(new User("Nanoha",7), 93);
map.put(new User("Kagome",15), 90);
map.put(new User("Kikyou",21), 99);
Set entrySet = map.entrySet();
Iterator iterator = entrySet.iterator();
while(iterator.hasNext()){
Object object = iterator.next();
Map.Entry entry = (Map.Entry)object;
System.out.println(entry.getKey() + " --> " + entry.getValue());
}
}
}
public class User implements Comparable{
private String name;
private int age;
public User(){
}
public User(String name,int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(Object o) {
if(o instanceof User){
User user = (User)o;
int compare = this.name .compareTo(user.name);
if(compare != 0){
return compare;
} else {
return Integer.compare(this.age, user.age);
}
} else {
throw new RuntimeException("输入的类型不匹配");
}
}
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 String toString(){
return "{ name = " + name + ",age = " + age +" }";
}
}
5.3.2、定制排序
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class TreeMapTest {
public static void main(String[] args) {
TreeMap map = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof User && o2 instanceof User){
User u1 = (User)o1;
User u2 = (User)o2;
int compare = Integer.compare(u1.getAge(), u2.getAge());
if(compare != 0){
return compare;
} else {
return u1.getName().compareTo(u2.getName());
}
} else {
throw new RuntimeException("输入的类型不匹配");
}
}
});
map.put(new User("Sakura",10), 100);
map.put(new User("Mikoto",13), 97);
map.put(new User("Nanoha",7), 93);
map.put(new User("Kagome",15), 90);
map.put(new User("Kikyou",21), 99);
Set entrySet = map.entrySet();
Iterator iterator = entrySet.iterator();
while(iterator.hasNext()){
Object object = iterator.next();
Map.Entry entry = (Map.Entry)object;
System.out.println(entry.getKey() + " --> " + entry.getValue());
}
}
}
public class User implements Comparable{
private String name;
private int age;
public User(){
}
public User(String name,int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(Object o) {
if(o instanceof User){
User user = (User)o;
int compare = this.name .compareTo(user.name);
if(compare != 0){
return compare;
} else {
return Integer.compare(this.age, user.age);
}
} else {
throw new RuntimeException("输入的类型不匹配");
}
}
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 String toString(){
return "{ name = " + name + ",age = " + age +" }";
}
}
5.4、Hashtable
??Hashtable，线程安全，效率低，不能存储null的key和value；
5.4.1、Properties
??Properties是Hashtable的子类，该对象用于处理属性文件。由于属性文件里的key、value都是字符串类型，所以Properties里的key和value都是字符串类型；读取数据时，建议使用setProperty(String key,String value)和getProperty(String key)；
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Properties;
public class PropertiesTest {
public static void main(String[] args) {
Properties properties = new Properties();
FileInputStream fileInputStream = null;
try {
fileInputStream = new FileInputStream("./java/jdbc.properties");
properties.load(fileInputStream);
String name = properties.getProperty("name");
String password = properties.getProperty("password");
System.out.println("name: " + name + " , password: " + password);
} catch (IOException e) {
e.printStackTrace();
} finally {
if(fileInputStream != null){
try {
fileInputStream.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
}
}
jdbc.properties文件中的内容如下：
name=sakura
password=27185
注意：我用的开发工具是VSCode，默认的工作目录是Source
六、集合与数组间的相互转换
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
public class CollectiontTest {
public static void main(String[] args) {
Collection collection = new ArrayList();
collection.add(123);
collection.add(true);
collection.add("Sakura");
//集合 --> 数组
Object array = collection.toArray();
for (Object object : collection) {
System.out.println(object);
}
//数组 --> 集合
List list = Arrays.asList(new String[]{"Sakura","Nanoha","Mikoto"});
Iterator iterator = list.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
六、Collections工具类
??Collections是一个操作Set、List和Map等集合的工具类，Collections中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法。
排序操作：
public static void reverse(List<?> list) //反转list中元素的顺序
public static void shuffle(List<?> list) //对list集合元素进行随机排序
public static > void sort(List list) //根据元素的自然顺序对指定List集合元素按升序排序
public static void sort(List list, Comparator<? super T> c) //根据指定的Compatator产生的顺序对List集合元素进行排序
public static void swap(List<?> list, int i, int j) //将指定list集合中的i出元素与j出元素进行排序
public static > T max(Collection<? extends T> coll) //根据元素的自然排序，返回给定集合中的最大元素
public static T max(Collection<? extends T> coll, Comparator<? super T> comp) //根据Comparator指定的顺序，返回给定集合中的最大元素
public static > T min(Collection<? extends T> coll) //根据元素的自然排序，返回给定集合中的最小元素
public static T min(Collection<? extends T> coll, Comparator<? super T> comp) //根据Comparator指定的顺序，返回给定集合中的最小元素
public static int frequency(Collection<?> c, Object o) //返回指定集合中指定元素的出现次数
public static void copy(List<? super T> dest, List<? extends T> src) //将src中的内容复制到dest中
public static boolean replaceAll(List list, T oldVal, T newVal) //使用新值newVal替换list对象中的旧值oldVal
public static List synchronizedList(List list) //将list转换成线程安全的
public static Map synchronizedMap(Map m) //将Map转换成线程安全的
七、常见的面试题
7.1 Set的面试题1
import java.util.HashSet;
public class HashSetTest{
public static void main(String[] args) {
HashSet set = new HashSet();
Person p1 = new Person("AA",1001);
Person p2 = new Person("BB",1002);
set.add(p1);
set.add(p2);
System.out.println(set);
p1.name = "CC";
set.remove(p1);
System.out.println(set);
set.add(new Person("CC",1001));
System.out.println(set);
set.add(new Person("AA",1001));
System.out.println(set);
}
}
public class Person {
String name;
int id;
public Person(){
}
public Person(String name,int id){
this.name = name;
this.id = id;
}
@Override
public boolean equals(Object obj) {
if(this == obj) return true;
if(obj == null || getClass()!= obj.getClass()) return false;
Person person = (Person)obj;
if(id != person.id) return false;
return (name != null) ? name.equals(person.name) : (person.name == null);
}
@Override
public int hashCode() {
int result = id;
return 31 * result + ((name != null) ? name.hashCode() : 0);
}
@Override
public String toString() {
return "Person{ name = " + name + "id = " + id + " }";
}
}