java高级-集合collection/map
前言
类似map、list、set等集合经常在项目中使用，今天在这里做个总结
为什么要有集合
java中基础的数据存储为数组，很多集合的底层逻辑就是基于数组实现的，对于数组他的优缺点很明显：
-
缺点
一旦初始化数组长度固定，无法自动扩容，数据可以存储重复的数据
删除/插入数据慢 -
优点
查询、修改速度快
数组的优缺点很明显，但是对于一些高级应用还是欠缺一些功能，所有就诞生了集合，集合分为collection和map两个体系，下面将分开描述这两个体系
collection
collection的继承树
image.png
上述图中这是描述了简单的继承关系，复杂的继承关系可以查看一些api文档
collection的方法描述
image.png
其中大部分方法不用描述，重点描述下iterator(),removeIf(),stream()这几个方法
iterator():返回一个迭代器，方便对集合中的数据遍历
removeIf():顾名思义就是有条件性的删除(删除满足给定Predicate(谓词)的此集合的所有元素)，
stream()：返回一个以此集合做为源的顺序流，可以根据此流来过滤以产生用户需要的流或者集合
removeIf()和stream()方法都会涉及一个接口Predicate，
Predicate的使用参考
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("1");
list.add("a");
list.add("2");
list.removeIf(new Predicate<String>() {
@Override
public boolean test(String s) {
return "a".equals(s);
}
});
System.out.println(list);
}
当集合中的数据与"a"相等时则删除
[1, 2]
可以看到，使用Predicate删除集合中的数据是很方便的，不用使用iterator遍历删除
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("1");
list.add("a");
list.add("2");
List list1 = list.stream().filter(new Predicate<String>() {
@Override
public boolean test(String s) {
return "a".equals(s);
}
}).collect(Collectors.toList());
System.out.println(list1);
}
[a, a]
使用stream流操作可以根据Predicate筛选出符合条件的集合
List
list应该被经常在java中使用，常用的子集有ArrayList、LinkedList、vector
-
ArraryList
- 相信ArraryList中的常用方法大家都很熟悉，下面对几个不常用的方法做个介绍
- indexOf(Object o):返回此集合中指定元素第一次出现的索引，如果不包含此元素则返回-1
- lastIndexOf(Object o):返回此集合中指定元素最后一次出现的索引，如不包含返回-1
- trimToSize：修改这个集合的容量为当前集合的实际大小，最小化集合实例的存储
- sort(Comparator<? super E> c)：使用提供的comparator对此列表进行排序，并返回排序后的集合
- listIterator():返回一个listIterator对象,Iterator只能单向遍历，而listIterator可以双向遍历，listIterator继承Iterator并且添加一些双向操作,例如：
- add(E e):将制定的元素插入列表,插入位置为迭代器当前位置之前
- set(E e):迭代器返回的最后一个元素替换参数e
- hasPrevious(E e):迭代器当前位置，是否有前序元素
- previous(E e):返回列表中的上一个元素，并向后移动光标位置
- previous(E e):返回列表中的上一个元素，并向后移动光标位置
- retainAll(Collection<?> c):此列表中只保留参数集合中包含的元素，
- 相信ArraryList中的常用方法大家都很熟悉，下面对几个不常用的方法做个介绍
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("1");
list.add("a");
list.add("2");
List list1 = new ArrayList();
list1.add("a");
list.retainAll(list1);
System.out.println(list);
}
输出：[a, a]
- LinkedList
ArrayList的内部是由一个可扩容的数组实现的，而LinkedList则是类似c语言中的双向链表，其核心存储结构的私有静态类Node,
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Node中的泛型对象e为实际存储的object，next和prev分别存储双向链表中的下一个节点和前一个节点，依次存储构成就构成了双向链表
- ArraryList和LinkedList的优缺点区别：
- 对于随机访问，ArraryList由于优于LinkedList，ArraryList可根据索引获取，而LinkedList则需要遍历移动指针去获取数据
- 对于新增和删除数据，则LinkedList优于ArraryList，
- LinkedList常用方法介绍：
- peekFirst():获取第一个元素，为空则返回空
- peekLast():获取最后一个元素，为空则返回空
- pollFirst():获取第一个元素并删除
- pollLast():获取最后一个元素并删除
- pop():弹出队列中第一个元素并删除
这些方法都是队列中常用的方法，还有一些常用方法是从List中实现的，具体就不一一描述了
Queue(队列)
- Queue与Deque的区别：
-
Deque:是Queue接口的子接口，为一个双向队列，双向队列是指该队列即能入队也能出队，如果将Deque限制只能从一端入队和出队，那么可实现栈的数据结构，对于栈而言，有入栈(push)和出栈(pop),遵循先进后出原则，由它衍生出的类有 LinkedBlockingDeque 、LinkedList、ArrayDeque等，当然这些类中也有些实现了Queue接口，所以这些类可以有队列的特性也可以用栈的特性,此接口包含的方法如下:
image.png
可以看到Deque中不仅包含可用于队列的add、poll、peek等方法，也包含用于栈的push和pop等方法
-
Queue：常用的队列模式，遵循先进先出原则，由他衍生出的类有LinkedBlockingQueue，ArrayDeque，ArrayBlockingQueue等。此接口包含的方法如下:
image.png
-
在具体的操作中可根据项目的实际需求来判定是要使用Queue下属子类(有些片面,主要是区分栈结构或者队列结构)或者使用Deque下属子类，（当然由于Deque是继承Queue的，所以都算是Queue的子类，但是Deque在Queue的基础上增加了栈的特性，所以继承了Deque的子类也具有栈的结构，同时具有Queue的队列特性，）
set
set存储的元素不可重复，且存储的元素无序，该集合中元素是否相等可重写hashCode和equals方法来判断，该接口的常用类有HashSet、TreeSet、LinkedHashSet等
-
HashSet
image.png
可以看到HashSet中并没有什么特殊的方法，基本都是从Set接口从实现的，值的一说的是，HashSet内部用于储存数据的是一个HashMap集合，换言之HashSet的实现原理是基于HashMap的；
- TreeSet
TreeSet是一个包含有序且没有重复元素的集合，通过TreeMap实现，TreeSet中包含一个"NavigableMap"类型的成员变量，实际上是一个TreeMap实例，TreeSet与HashMap最大的区别就是前者是有序的，后者是无序的；TreeSet用于存储元素时需要注意一点，因为treeMap值有序的，而这个有序并不是插入的顺序而是元素之前的比较顺序，所以存储的元素需要带有比较器(Comparable)或者在实例化TreeSet时传入比较器实例(Comparator)，参考其构造方法，
TreeSet方法介绍：参考
package java.util;
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
// 使用NavigableMap对象的key来保存Set集合的元素
private transient NavigableMap<E,Object> m;
//使用PRESENT作为Map集合中的value
private static final Object PRESENT = new Object();
// 不带参数的构造函数。创建一个空的TreeMap
//以自然排序方法创建一个新的TreeMap，再根据该TreeMap创建一个TreeSet
//使用该TreeMap的key来保存Set集合的元素
public TreeSet() {
this(new TreeMap<E,Object>());
}
// 将TreeMap赋值给 "NavigableMap对象m"
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
//以定制排序的方式创建一个新的TreeMap。根据该TreeMap创建一个TreeSet
//使用该TreeMap的key来保存set集合的元素
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<E,Object>(comparator));
}
// 创建TreeSet，并将集合c中的全部元素都添加到TreeSet中
public TreeSet(Collection<? extends E> c) {
this();
// 将集合c中的元素全部添加到TreeSet中
addAll(c);
}
// 创建TreeSet，并将s中的全部元素都添加到TreeSet中
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
// 返回TreeSet的顺序排列的迭代器。
// 因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
// 返回TreeSet的逆序排列的迭代器。
// 因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
// 返回TreeSet的大小
public int size() {
return m.size();
}
// 返回TreeSet是否为空
public boolean isEmpty() {
return m.isEmpty();
}
// 返回TreeSet是否包含对象(o)
public boolean contains(Object o) {
return m.containsKey(o);
}
// 添加e到TreeSet中
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
// 删除TreeSet中的对象o
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
// 清空TreeSet
public void clear() {
m.clear();
}
// 将集合c中的全部元素添加到TreeSet中
public boolean addAll(Collection<? extends E> c) {
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
//把C集合强制转换为SortedSet集合
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
//把m集合强制转换为TreeMap集合
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
Comparator<? super E> mc = map.comparator();
//如果cc和mc两个Comparator相等
if (cc==mc || (cc != null && cc.equals(mc))) {
//把Collection中所有元素添加成TreeMap集合的key
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
return super.addAll(c);
}
// 返回子Set，实际上是通过TreeMap的subMap()实现的。
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
// 返回Set的头部，范围是：从头部到toElement。
// inclusive是是否包含toElement的标志
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<E>(m.headMap(toElement, inclusive));
}
// 返回Set的尾部，范围是：从fromElement到结尾。
// inclusive是是否包含fromElement的标志
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<E>(m.tailMap(fromElement, inclusive));
}
// 返回子Set。范围是：从fromElement(包括)到toElement(不包括)。
public SortedSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
// 返回Set的头部，范围是：从头部到toElement(不包括)。
public SortedSet<E> headSet(E toElement) {
return headSet(toElement, false);
}
// 返回Set的尾部，范围是：从fromElement到结尾(不包括)。
public SortedSet<E> tailSet(E fromElement) {
return tailSet(fromElement, true);
}
// 返回Set的比较器
public Comparator<? super E> comparator() {
return m.comparator();
}
// 返回Set的第一个元素
public E first() {
return m.firstKey();
}
// 返回Set的最后一个元素
public E first() {
public E last() {
return m.lastKey();
}
// 返回Set中小于e的最大元素
public E lower(E e) {
return m.lowerKey(e);
}
// 返回Set中小于/等于e的最大元素
public E floor(E e) {
return m.floorKey(e);
}
// 返回Set中大于/等于e的最小元素
public E ceiling(E e) {
return m.ceilingKey(e);
}
// 返回Set中大于e的最小元素
public E higher(E e) {
return m.higherKey(e);
}
// 获取第一个元素，并将该元素从TreeMap中删除。
public E pollFirst() {
Map.Entry<E,?> e = m.pollFirstEntry();
return (e == null)? null : e.getKey();
}
// 获取最后一个元素，并将该元素从TreeMap中删除。
public E pollLast() {
Map.Entry<E,?> e = m.pollLastEntry();
return (e == null)? null : e.getKey();
}
// 克隆一个TreeSet，并返回Object对象
public Object clone() {
TreeSet<E> clone = null;
try {
clone = (TreeSet<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
clone.m = new TreeMap<E,Object>(m);
return clone;
}
// java.io.Serializable的写入函数
// 将TreeSet的“比较器、容量，所有的元素值”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
s.defaultWriteObject();
// 写入比较器
s.writeObject(m.comparator());
// 写入容量
s.writeInt(m.size());
// 写入“TreeSet中的每一个元素”
for (Iterator i=m.keySet().iterator(); i.hasNext(); )
s.writeObject(i.next());
}
// java.io.Serializable的读取函数：根据写入方式读出
// 先将TreeSet的“比较器、容量、所有的元素值”依次读出
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden stuff
s.defaultReadObject();
// 从输入流中读取TreeSet的“比较器”
Comparator<? super E> c = (Comparator<? super E>) s.readObject();
TreeMap<E,Object> tm;
if (c==null)
tm = new TreeMap<E,Object>();
else
tm = new TreeMap<E,Object>(c);
m = tm;
// 从输入流中读取TreeSet的“容量”
int size = s.readInt();
// 从输入流中读取TreeSet的“全部元素”
tm.readTreeSet(size, s, PRESENT);
}
// TreeSet的序列版本号
private static final long serialVersionUID = -2479143000061671589L;
}
- LinkedHashSet
继承HashSet,使用HashSet中带有LinkedHashMap的构造方法实例化出存储数据的map，从源码中可以看到LinkedHashSet直接继承了HashSet并没有新增任何方法，只是复写了spliterator()方法；LinkedHashSet内部使用的是LinkedHashMap，与HashSet的区别就是前者可以保证元素的顺序，也就是遍历顺序和插入顺序是一致的
上述是大概的Collection中的常用类，当然还有很多类没有被介绍到，可以在具体使用的时候去查看，看一下源码基本的使用方式差不多，下面我们看下Map集合的形式
Map
image.png
map中的方法一览：
image.png
对于其中常用方法和不常用方法做个简单介绍：
- size():返回map大小
- isEmpty():判断map是否为空
- containsKey():是否包含当前key
- containsValue():是否包含当前value
- get()/put()：存储值
- remove()/clear():清除指定键的值，清除等个map
- KeySet():返回当前map的所有键值的set集合，其内部是基于iterator(迭代器)实现的，
- values():返回当前map中所有有效值value的集合
- entrySet():返回当前map中的所有实例(Entry)的set集合
- getOrDefault():获取对应key的值，如果没有则返回入参中的默认值
- forEach:对map的所有键值对遍历，内部实际就是对entrySet的返回值进行遍历输出key-value
- replaceAll():替换map中所有的value值，替换的值为BiFunction接口中的apply()的返回值
- putIfAbsent():如果指定的key不存在与map中则新增改key-value值并返回null，如果存在于map中则刷新map的值为新的value值，返回旧value值
- compute():api文档的解释为计算当前key的映射及当前映射的值，可能初看会看不懂，举个例子：
String str1 = "hello java, i am vary happy! nice to meet you";
HashMap<Character, Integer> result2 = new HashMap<>();
for (int i = 0; i < str1.length(); i++) {
char curChar = str1.charAt(i);
//compute是返回最新的值
result2.compute(curChar, (k, v) -> {
if (v == null) {
v = 1;
} else {
v += 1;
}
return v;
});
}
System.out.println(result1);
输出：
{ =9, !=1, a=5, c=1, e=4, h=2, i=2, j=1, ,=1, l=2, m=2, n=1, o=3, p=2, r=1, t=2, u=1, v=2, y=3}
可以看到compute会根据指定的key生成一个key-value，
HashMap
HashMap可以算是项目中最常用的一种map子集，用来存储k-v数据，其内部采用的是哈希结构的形式，其实也就是数组加链表的使用，由于其使用的是哈希结构的方式去存储数据，则其必然会存在哈希冲突，对于哈希冲突只能尽量的减少而不能完全避免，HashMap中真正存储k-v集合的对象为Node对象，此对象继承自Mao.Entry,
HashMap中包含有很多的内部类，大体如下：
image.png
可以看到基本都很类似，其中：
Node：为HashMap中的存储对象类型实际类型
KeySet/Values/EntrySet:为键的set集合，value的set集合，Node的set集合，都是用来方便更好的访问HashMap中的key或者value
keyIterator/valueIterator/EntryIterator都是继承自HashIterator：返回一个key或者value的迭代器
keySplitIterator/valueSplitIterator/EntrySplitIterator都是继承自HashSplitIterator;
HashMap继承自Map，所以其中的方法大致来自于Map，上述已经分析过了，部分自定义的方法是扩展自有功能，也不难，可以执行分析一下
LinkedHashMap
一看是Linked开头的就知道跟链表有关系，是的，LinkedHashMap区别于HashMap的重要一点就是前者使用的是双向链表，而后者使用的是单向链表，前者可以保证按照插入顺序迭代输出，后者在迭代输出数据时是无序的
WeakHashMap
WeakHashMap也是一个散列表，存储的内容也是键值对，键和值都可以是null，不过WeakHashMap的键是"弱键"，在weakHashMap中，当某个键没有其他任何地方没有引用时(只有map中的弱引用)，该key-value被从weakHashMap中被自动移除(实际是被gc回收了到ReferenceQueue队列中，它会保存被GC回收的弱键)，当下一次操作weakHashMap时会先同步table和queue，table中保存了全部的键值对，而queue中保存了被GC回收的键值对，同步他们就是删除table中被GC回收的键值对，这就是弱键如何被自动从weakHashMap中删除的步骤。
image.png
可以看到weakHashMap中存储实例Entry类继承了weakReference，并在构造方法中调用了父类的构造方法传入了key，即在此时将key变为了弱键。
