0%

查缺补漏-JavaCollecionsFramework

本章是整理知识内容,为强化知识长期更新。

Java集合

​ 集合是Java提供的工具包、包含常用的数据结构:集合、链表、队列、栈、数组、映射等。Collection的包是java.util.*。

Collection

Map

实际上还有Cloneable、Serializable接口是都集合类需要实现的,通用所以不不画上去了。

Java集合主要划分4个部分:

  • List(列队)
  • Set(集合)
  • Map(映射)
  • 工具类(Iterator迭代器、Enumeration枚举类、Arrays、Collections)

划重点

  • Conllection
    • List
      • ArrayList
      • Vector
        • Stack
      • LinkedList
    • Set
      • HashSet
      • TreeSet
      • LinkedHashSet
    • Queue
  • Map
    • HashMap
    • HashTable
    • TreeMap
  • 工具
    • Arrays
    • Collections
    • Enumeration

Java类库中具体集合

集合类型 概括
ArrayList 一种可以动态增长和缩减的索引序列,访问速度很快但是插入和删除比ArrayList慢。
LinkedList 一种可以在任何位置进行高效地插入和删除操作的有序序列,但是访问比较ArrayList慢。
ArrayDeque 一种循环数组实现的双端序列。
HashSet 一种没有重复元素的无序集合。
TreeSet 一种有序集合。
EnumSet<E extends Enum> 一种包含枚举类型的集合。
LinkedHashSet 一种可以记住元素插入顺序的集合。
PriorityQueue 一种允许高效删除最小元素的集合。
HashMap<K , V> 一个存储 键 / 值 关联的数据结构。
TreeMap<K , V> 一种键值有序排列的映射表。
EnumMap<K extends Enum, V> 一种键属于枚举类型的映射表。
LinkedHashMap<K ,V > 一种可以记住键 / 值 项添加顺序的映射表。
WeakHashMap<K , V > 一种其值无用武之地后可以被垃圾回收回收的映射表。
IdentityHashMap<K , V> 一种用 == 而不是用用 equals 比较的映射表。

介绍下Java Collection Interface

1. Set

  • TreeSet:基于红黑树实现,支持有序性操作,例如根据一个范围查找元素的操作。但是查找效率不如 HashSet,HashSet 查找的时间复杂度为 O(1),TreeSet 则为 O(logN)。
  • HashSet:基于哈希表实现,支持快速查找,但不支持有序性操作。并且失去了元素的插入顺序信息,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
  • LinkedHashSet:具有 HashSet 的查找效率,并且内部使用双向链表维护元素的插入顺序。

2. List

  • ArrayList:基于动态数组实现,支持随机访问。
  • Vector:和 ArrayList 类似,但它是线程安全的。
  • LinkedList:基于双向链表实现,只能顺序访问,但是可以快速地在链表中间插入和删除元素。不仅如此,LinkedList 还可以用作栈、队列和双向队列。

3. Queue

  • LinkedList:可以用它来实现双向队列。
  • PriorityQueue:基于堆结构实现,可以用它来实现优先队列。

4. Map

  • TreeMap:基于红黑树实现。
  • HashMap:基于哈希表实现。
  • HashTable:和 HashMap 类似,但它是线程安全的,这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类,不应该去使用它,而是使用 ConcurrentHashMap 来支持线程安全,ConcurrentHashMap 的效率会更高,因为 ConcurrentHashMap 引入了分段锁。
  • LinkedHashMap:使用双向链表来维护元素的顺序,顺序为插入顺序或者最近最少使用(LRU)顺序。

泛型E

​ 该接口封装了不同类型的结合,使得开发人员操作集合的时候不必关心他们具体的实现,核心的集合接口是Java集合框架的基础。证如上图看到的核心集合接口的层次关系。

语法告诉我们这个接口是泛化的,在使用集合的时候需要声明集合的实例、指定集合中对象的类型。指定类型之后编译器能在编译期间验证集合中的元素类型是正确的。从而减少错误。

Interface

首先简单的介绍下接口以及接口的方法,便于后面的深入学习。

  • Iterator

  • Iterable

  • Collection

    • Queue

      • LinkedList 双向列队结构。
      • PriorityQueue 基于堆机构实现,可以用来做优先级列队。
    • Set

      • HashSet 基于哈希实现,支持快速查找,但不支持有序性操作,例如根据一个范围查找元素的操作。并且失去了元素的插入顺序信息,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
      • TreeSet 基于红黑树实现,支持有序性操作,但是查找效率不如 HashSet,HashSet 查找时间复杂度为 O(1),TreeSet 则为 O(logN);
    • LinkedHashSet 具有 HashSet 的查找效率,且内部使用链表维护元素的插入顺序。

    • List

      • ArrayList 基于动态数组实现,支持随机访问元素。
      • Vector 和ArrayList类似,但是它是线程安全的。
      • Stack 是Vector的子类,它实现了一个标准的后进先出的栈。
      • LinkedList 基于双向循环列表,只能顺序访问;可以快速的插入和删除元素。而且,LinkedList还可以用作栈、列队和双端列队。
  • Map<K , V >

需要特别说明下Irertor<E> 和Iterable<T>这两个接口,Iterator模式是用于遍历集合类的标准方法。它主要用于将 访问逻辑从不同的类型集合类中抽象出来、所以在很多实现了Iterble集合类中实现这个多个Iterator接口。这样避免向客用户包撸集合内部的结构,这就是为什么我们用的这么爽的原因之一。

实现类一览表

Collction 排序 随机访问 Key-Value 可重复元素 空元素 线程安全
ArrayList Y Y N Y Y N
LinkedList Y N N Y Y N
HashSet N N N N Y N
TreeSet Y N N N N N
HashMap N Y Y N Y N
TreeMap Y Y Y N N N
Vector Y Y N Y Y Y
Stack Y N N Y Y Y
Hashtable N Y Y N N Y
Properties Y N N Y Y Y
CopyOnWriteArrayList Y Y Y N N Y
ConcurrentHashMap N Y Y N N Y
CopyOnWriteArrayList N N N N Y Y

Iterator 接口

  • 迭代器必须从属容器、其作用就是迭代所属容器中的元素。源代码看出这是一个泛型接口。就是迭代泛型类元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public interface Iterator<E> {

// 如果存在可以返回的元素就返回true
boolean hasNext();

// 返回将要访问的下一个元素、如果已经达到集合的尾部,则抛出一个NoSuchElementException异常。
E next();

// 删除上次访问的对象。如果已经是尾部;则抛出一个IllegalStateException异常。
// 如果没有重写这个方法就会排除这个异常UnsupportedOperationException
// 比如:Arrays$ArrayList中add 、 remove方法就没有重写,直接使用Arrays.toList的集合就会抛出这个异常
default void remove() {
throw new UnsupportedOperationException("remove");
}

// Itreator专门提供的一个方法,可以使用Lambda表达式遍历。
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}

Iterable 接口

  • 这个接口被Collection继承。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public interface Iterable<T> {

// 定义了Iterator,返回Iterator实例。
Iterator<T> iterator();

// 增强for循环,专门给Lambda表达式遍历。
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}

// 根据此Iterable描述的元素创建Spliterator。
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}

Collection 接口

  • 这个接口集合接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public interface Collection<E> extends Iterable<E> {
// Query Operations

// 返回当前存储在集合中的元素个数。
int size();

// 如果集合中没有元素,则返回true。
boolean isEmpty();

// 如果集合中包含一个元素与参数o相同,这返回true。
boolean contains(Object o);

// 返回当前用于访问集合的迭代器。
Iterator<E> iterator();

// 返回这个集合的数组对象。
Object[] toArray();

// 返回这个集合的数组对象,如果t这个数组足够大,就将集合中的元素填入这个数组中。剩余的空间填入Null;否则,分配一个新数组,其成员类型与t的成员类型相同,其长度等于集合的大小,并添加集合元素。
<T> T[] toArray(T[] a);

// Modification Operations
// 将一个元素添加到集合中,如果这个调用改变了集合,则返回true。
boolean add(E e);

// 从这个集合中删除等于o的对象,如果匹配对象被删除。就返回true。
boolean remove(Object o);

// Bulk Operations
// 如果此集合包含指定集合c中的所有元素,则返回true。
boolean containsAll(Collection<?> c);

// 将c集合中所有元素添加到这个集合中,如果由于这个调用改变了集合,返回true。
boolean addAll(Collection<? extends E> c);

// 从集合中删除集合c中的所有元素,如果由于这个元素改变了集合,返回true。
boolean removeAll(Collection<?> c);

// 删除此集合中满足给定谓词的所有元素。
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}

// 仅保留包含在指定集合中的此c集合中的元素
boolean retainAll(Collection<?> c);

// 从这个集合中删除所有元素。
void clear();

// Comparison and hashing
// 从这个集合中删除所有元素。
boolean equals(Object o);

// 返回此集合的哈希码值
int hashCode();

// 在此集合中的元素上创建Spliterator
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}

// 以此集合作为源返回顺序流。
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}

// 以此集合作为源返回可能并行的Stream。
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}

Map 接口

翻译成中文就是地图,x y 坐标代表地图上的一个位置。Map就是一种 键\值的存在。键好比地图中的x y ,值好比地图中的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
public interface Map<K,V> {
// Query Operations

// 返回此映射中的键-值映射关系数。
int size();

/**
* Returns <tt>true</tt> if this map contains no key-value mappings.
*
* @return <tt>true</tt> if this map contains no key-value mappings
*/
// 如果不存在映射元素,则返回true否则返回false。
boolean isEmpty();

// 如果这个映射表已经存有这个键就返回true。
boolean containsKey(Object key);

// 如果这个映射表已经存在这个值就返回true。
boolean containsValue(Object value);

// 获取与键对应的值;返回与键对应的对象,如果映射表中没有这个对象则返回NULL,键可以是NULL。
V get(Object key);

// Modification Operations

// 将键值对关系插入映射表中,如果这个键已经存在,新的对象会取代这个键对应旧的对象。这个方法将返回键的旧值,如果这个键以前没有出现过则返回NULL,键可以是NULL,但是值不能是NULL。
V put(K key, V value);

// 如果该键 key 的映射存在,则从映射集合中删除该映射,并返回该键对应的值。如果该键没有映射关系,则返回一个NULL。
V remove(Object key);


// Bulk Operations

// 将m映射表中所有的条目都添加到当前的映射表中。
void putAll(Map<? extends K, ? extends V> m);

// 清空当前映射中键对值
void clear();

// Views
// 返回映射表中所有键的集合,可以从这个集中删除元素,同时也可以映射表中删除它们,但是不能添加元素。
Set<K> keySet();

// 返回映射表中所有值的集合,可以从这个集中删除元素,同时也可以从映射表中删除它们,但是不能添加元素。
Collection<V> values();

// 返回Map.Entry对象的集,即映射表中的键\ 值对。同时也可以从映射表中删除元素,同时可以删除该键\值对。但是不能添加任何元素。
Set<Map.Entry<K, V>> entrySet();


interface Entry<K,V> {

K getKey();


V getValue();


V setValue(V value);


boolean equals(Object o);


int hashCode();


public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}


public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}


public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}


public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}

// Comparison and hashing


boolean equals(Object o);


int hashCode();

// Defaultable methods

// 返回指定建映射到的值,如果该键不存在值,就返回一个默认的。
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}

// 为此映射中每一元素进行操作。
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}


default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}

// ise thrown from function is not a cme.
v = function.apply(k, v);

try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}


default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}

return v;
}


default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}


default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}


default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}


default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}

return v;
}


default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null;
}
} else {
return null;
}
}


default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);

V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
if (oldValue != null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null;
}
} else {
// add or replace old mapping
put(key, newValue);
return newValue;
}
}


default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if(newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
}
}