初探Java-Collecions-Framework-Interface.md

​ Java集合类皆是为帮助我们在程序设计中实现传统的数据结构。作为Java基础的知识,这里简单快速的了解下。后续的文章中会逐步深入。优先参考官 方API文档。

建议在学习集合类之前,先了解下数据结构Data Structures ,对学习集合类有很大帮助。

泛型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

需要特别说明下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;
}
}