forked from zhonghuasheng/Tutorial
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathjava-collection.md
More file actions
executable file
·1129 lines (985 loc) · 42.1 KB
/
java-collection.md
File metadata and controls
executable file
·1129 lines (985 loc) · 42.1 KB
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
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
# 目录
* [0. Java集合框架历史](#Java集合框架历史)
* [1. Java集合概述](#1.Java集合概述)
* [Collection集合概述](Collection集合概述)
* [Map集合概述](#Map集合概述)
* [Concurrent包下的集合概述](#Concurrent包下的集合概述)
* [2. Java集合详解](#2.Java集合详解)
* [Collection集合下常用实现类详解](#Collection集合下常用实现类详解)
* [Iterator接口源码解析](#Iterator接口源码解析)
* [Collection接口源码解析](#Collection接口源码解析)
* [List接口源码解析](#List接口源码解析)
* [AbstractCollection抽象类源码解析](#AbstractCollection抽象类源码解析)
* [AbstractList抽象类源码解析](#AbstractList源码解析)
* [ArrayList源码解析和使用](#ArrayList源码解析和使用)
* [Vector源码解析和使用](#Vector源码解析和使用)
* [Stack源码解析和使用](#Stack源码解析和使用)
* [AbstractSequentialList抽象类源码解析](#AbstractSequentialList抽象类源码解析)
* [LinkedList源码解析和使用](#LinkedList源码解析和使用)
* [Set接口源码解析](#Set接口源码解析)
* [AbstractSet源码解析](#AbstractSet源码解析)
* [HashSet源码解析和使用](#HashSet源码解析和使用)
* [TreeSet源码解析和使用](#TreeSet源码解析和使用)
* [Queue接口源码解析](#Queue接口源码解析)
* [Deque接口源码解析](#Deque接口源码解析)
* [LinkedList使用](#LinkedList使用)
* [Map集合下常用实现类详解](#Map集合下常用实现类详解)
* [AbstractMap接口源码解析](#AbstractMap接口源码解析)
* [HashMap源码解析和使用](#HashMap源码解析和使用)
* [WeakHashMap源码解析和使用](#WeakHashMap源码解析和使用)
* [TreeMap源码解析和使用](#TreeMap源码解析和使用)
* [Hashtable源码解析和使用](#Hashtable源码解析和使用)
* [Concurrent包下常用实现类详解](#Concurrent包下常用实现类详解)
* [3. 集合框架中体现的设计模式和编程规范](#3.集合框架中体现的设计模式和编程规范)
* [迭代器模式](#迭代器模式)
* [适配器模式](#适配器模式)
* [4. 其他](#4.其他)
* [fail-fast机制](#fail-fast机制)
* [MarkerInterface](#Marker-Interface)
* [Collections工具类-操作集合]()
* [Arrays工具类-操作数组]()
* [5. 圈重点](#5.圈重点)
* [参考资料](#参考资料)
# 0.Java集合框架历史
摘自Wikipedia [Java Collection Framework](https://en.wikipedia.org/wiki/Java_collections_framework):
```
Collection implementations in pre-JDK 1.2 versions of the Java platform included few data structure classes, but did not contain a collections framework.[3] The standard methods for grouping Java objects were via the array, the Vector, and the Hashtable classes, which unfortunately were not easy to extend, and did not implement a standard member interface.[4]
To address the need for reusable collection data structures, several independent frameworks were developed,[3] the most used being Doug Lea's Collections package,[5] and ObjectSpace Generic Collection Library (JGL),[6] whose main goal was consistency with the C++ Standard Template Library (STL).[7]
```
可知,早期的Java Group通过Array, Vector, HashTable这些类来实现,但是他们难扩展,后期大神们创建了独立的Java Data Structure Framework,并且在日后这些framework被build进入JDK中,慢慢形成了Java Collection Framework。
# 1.Java集合概述
Java的集合类位于java.util.*包下,大体分为2类,Collection和Map,另外就是2个工具类。Concurrent是jdk1.5引入的(在这之前java语言内置对多线程的支持比较有限),主要代码由Doug Lea完成。
## Collection集合概述
1. 概述
* Collection包含3个分支
```
AbstractCollection是抽象类,实现了部分Collection中的API,如contains,toArray, remove, toString等方法。
```
* Queue
```
队列是一种特殊的线性表,允许在表的头部进行删除操作,在表的尾部进行插入操作。有2个继承接口,BlockingQueue(阻塞队列)和Deque(双向队列)。AbstractQueue是抽象类,实现了Queue中的大部分API,常见实现类有LinkedQueue。
```
* List
```
List是一个有序的队列,每个元素都有它的索引,第一个元素的索引值为0。AbstractList是抽象类,实现了List中的大部分API,常见实现类有LinkedList, ArrayList, Vector, Stack。
```
* Set
```
Set是一个不允许有重复元素的集合。 AbstractSet是抽象类,实现了Set中的大部分API,常见的实现类有HashSet, TreeSet。
```
## Map集合概述
1. 概述
* Map包含1个分支
```
Map是一个映射接口,即key-value的键值对。AbstractMap是抽象类,实现了Map中的大部分API,HashMap, TreeMap, WeakHashMap是其实现类。
```
2. 源码阅读
`接口定义`
```java
public interface Map<K,V>
```
`常用方法`
```java
abstract void clear()
abstract boolean containsKey(Object key)
abstract boolean containsValue(Object value)
abstract Set<Entry<K, V>> entrySet()
abstract boolean equals(Object object)
abstract V get(Object key)
abstract int hashCode()
abstract boolean isEmpty()
abstract Set<K> keySet()
abstract V put(K key, V value)
abstract void putAll(Map<? extends K, ? extends V> map)
abstract V remove(Object key)
abstract int size()
abstract Collection<V> values()
```
```
Map 是一个键值对(key-value)映射接口。Map映射中不能包含重复的键;每个键最多只能映射到一个值。
Map 接口提供三种collection 视图,允许以键集(keySet())、值集(values())或键-值(entrySet())映射关系集的形式查看某个映射的内容。
Map 映射顺序。有些实现类,可以明确保证其顺序,如 TreeMap;另一些映射实现则不保证顺序,如 HashMap 类。
Map 的实现类应该提供2个“标准的”构造方法:第一个,void(无参数)构造方法,用于创建空映射;第二个,带有单个 Map 类型参数的构造方法,用于创建一个与其参数具有相同键-值映射关系的新映射。实际上,后一个构造方法允许用户复制任意映射,生成所需类的一个等价映射。尽管无法强制执行此建议(因为接口不能包含构造方法),但是 JDK 中所有通用的映射实现都遵从它。
```
[Map的三种Collection视图例子 MapTest01.java](https://github.com/zhonghuasheng/JAVA/blob/master/basic/src/main/java/com/zhonghuasheng/basic/util/MapTest01.java)
## Concurrent包下的集合概述
1. 概述
* Concurrent主要有3个package组成
* java.util.concurrent
```
提供大部分关于并发的接口和类,如BlockingQueue, ConcurrentHashMap, ExecutorService等
```
* java.util.concurrent.atomic
```
提供所有的原子类操作,如AtomicInteger, AtomicLong等
```
* java.util.concurrent.locks
```
提供锁相关的类,如Lock, ReentrantLock, ReadWriteLock, Confition等
```
# 2.Java集合详解
## Collection集合下常用实现类详解
### Iterator接口源码解析
`总结`
```
iterator.remove()方法必须要在调用了next()方法之后,否则会报IllegalStateException。
if the next method has not yet been called, or the remove method has already been called after the last call to the next method
```
`常用方法`
```java
boolean hasNext()
E next()
void remove()
```
### Collection接口源码解析
`接口定义`:
```java
/* 说明:
Collection集合用于存Object的,不支持存储基础数据类型,这是由Collection接口的定义决定的: Collection<E>
这样写会报错: Syntax error, insert "Dimensions" to complete ReferenceType
List<int> ints = new ArrayList<int>();
*/
public interface Collection<E> extends Iterable<E>
```
`常用方法`
```java
abstract boolean add(E object)
// addAll参数为E或E的子类
abstract boolean addAll(Collection<? extends E> collection)
abstract void clear()
abstract boolean contains(Object object)
abstract boolean containsAll(Collection<?> collection)
abstract boolean equals(Object object)
abstract int hashCode()
abstract boolean isEmpty()
abstract Iterator<E> iterator()
abstract boolean remove(Object object)
abstract boolean removeAll(Collection<?> collection)
abstract boolean retainAll(Collection<?> collection)
/*
* Returns the number of elements in this collection. If this collection
* contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
* <tt>Integer.MAX_VALUE</tt>.
* Integer.MIN_VALUE是-(2的31次方),Integer.MAX_VALUE是2的31次方减1
*/
abstract int size()
abstract <T> T[] toArray(T[] array)
abstract Object[] toArray()
```
### List接口源码解析
`总结`
```
List是有序的,支持随机访问(通过索引下标访问)
List允许重复的值(原因是它的数据存储方式)
```
`常用方法`
```java
boolean add(E)
void add(int, E)
boolean addAll(int, Collection<? extends E>)
boolean addAll(Collection<? extends E>)
void clear()
boolean contains(Object) //AbstractCollection中通过iterator迭代遍历判断 ArrayList中通过调用indexOf(o) >= 0 来判断是否包含
boolean containsAll(Collection<?>)
boolean equals(Object)
E get(int)
int hashCode()
int indexOf(Object)
boolean isEmpty()
Iterator<E> iterator()
int lastIndexOf(Object)
ListIterator<E> listIterator()
ListIterator<E> listIterator(int)
E remove(int)
boolean remove(Object)
boolean removeAll(Collection<?>)
boolean retainAll(Collection<?> a) // b.retainAll(a) 移除b中有而a中没有的所有元素,所以结果是a的子集
E set(int, E)
int size()
List<E> subList(int, int)
Object[] toArray()
T[] toArray(T[])
```
```java
ListIterator.java
boolean hasNext()
boolean hasPrevioud()
E next()
E previous()
int nextIndex()
int previousIndex()
```
#### AbstractCollection抽象类源码解析
`总结`
```
AbstractCollection是个抽象类,继承自Collection接口,并实现了其中的方法,同时添加了toString()方法
```
`常用方法`
```java
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 减8的原因是某些VMs存储了数据的header
private static <T> T[] finishToArry(T[] r, Iterator<?> it) // 用于将集合转换为数组
private static int hugeCapacity(int minCapacity) // 用于finishToArry
boolean add(E e) // 未实现
boolean addAll(int index, Collection<? extends E> c) // 未实现
void clear()
boolean contains(Object o) // 迭代遍历判断
boolean containsAll(Collection<?> c) // for循环遍历c,然后通过调用contains判断
boolean isEmpty() // 通过判断size()==0,size()未实现
Iterator<E> iterator() // 未实现
boolean remove(Object o) //迭代器遍历删除
boolean removeAll(Collection<?> c)
boolean retainAll(Collection<?> c)
int size();
Object[] toArray()
T[] toArray(T[])
String toString() // 迭代遍历集合,通过StringBuilder接收组合输出
```
#### AbstractList源码解析
`总结`
```
AbstractList中有Itr(继承Iterator)和ListItr(继承ListIterator)两个内部类
在迭代遍历过程中,如果出现对集合的写的行为(list.remove(obj)),会报出ConcurrentModificationException。
AbstractList中仍然没有实现add方法
```
```java
// list调用remove方法会导致modCount的值改变
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
// 通过调用iterator.remove()可以保证不会报ConcurrentModificationException
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
```
##### ArrayList源码解析和使用
`总结`
1. ArrayList是一个数据集合,相当于一个动态数组(Object[] elementData)。与Java中的数据相比,它的容量能动态增长,默认长度时10(DEFAULT_CAPACITY),扩容时新的容量=原始容量 + 原始容量>>1
2. ArrayList实现了RandomAccess接口(Marker Interface),又由于其数据以数据存储,因此支持快速随机查找,但是修改和删除效率不高
```java
// Collections中通过RandomAccess接口判断
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
```
3. ArrayList不是线程安全的,Vertor是线程安全的(其绝大部分方法都加了synchronized关键字),可在多线程下使用CopyOnWriteArryList。
##### Vector源码解析和使用
`总结`
```java
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
```
1. Vector是一个矢量队列,支持比本的添加、修改、删除、遍历等功能
2. Vector实现了RandomAccess接口,即支持随机访问功能(get(int index))
3. Vector中的public API都是加了synchronized关键字来保证线程安全
##### Stack源码解析和使用
`总结`
```
Stack是栈,特性是先进后出(FILO, First In Last Out)
Stack是继承自Vector,也是通过数据实现的
```
`常用方法`
```java
Object push(Object element) // 把对象压入堆栈
Object pop() // 移除堆栈顶部对象,并作为此方法的返回值返回该对象
Object peek() // 查看堆栈顶部的对象,但不从堆栈中移除它
```
#### AbstractSequentialList抽象类源码解析
`总结`
```
这个抽象类没什么特别
```
##### LinkedList源码解析和使用
`总结`
```java
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable {}
```
```
LinkedList实现了Deque接口,能对它进行双向列表操作,也就是说顺序访问会非常高效,随机访问效率比较低
LinkedList不是线程安全的,可以通过List list = Collections.synchronizedList(new LinkedList(...))来转换,不过LinkedList的数据类型会丢失
LinkedList中使用Node对象来存储数据
```
`常用方法`
```java
boolean add(E element) // offer属于 offer in interface Deque<E>, add 属于 add in interface Collection<E>
void(int index, E element) // 判断index==size,=就linkLast, or linkBefore
void addFirst(E element)
void addLast(E element)
void clear() // 清空,注意GC
Object clone() // 浅拷贝 shallow copy
Iterator<E> descendingIterator() // 倒着输出
E element() // 获取第一个元素
E get(int index)
E getFirst();
E getLast();
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator<E> listIterator(int index)
boolean offer(E element) // offer属于 offer in interface Deque<E>, add 属于 add in interface Collection<E>
boolean offerFirst(E element)
boolean offerLast(E element)
E peek() // 返回链表中的第一个元素,并且不会移除
E peekFirst() // 和peek没啥区别
E peekLast()
E poll() // 返回链表中的第一个元素,并且会移除掉
E pollFirst() // 链表为空时会返回null
E pollLast()
E pop() // 链表为空时会报NoSuchElementException,这就是区别
void push(E e) // 添加到链表的第一个元素
E remove() // 删除第一个元素
E remove
E set(int index, E element) // 替换指定位置的元素
```
LinkedList可以作为FIFO的队列,使用如下方法:
```java
// Queue
boolean add(e) // add比offer的区别在于add时如果capacity超了,会报错,而offer不会
boolean offer(e)
E remove() // 返回队列的第一个元素,并且删除,如果队列为空,报NoSuchElementException
E poll() // 返回队列的第一个元素,并且删除,如果队列为空,返回null
E element() // 返回队列的第一个元素,不删除,如果队列为空,报NoSuchElementException
E peek() // 返回队列的第一个元素,不删除,如果队列为空,返回null
```
LinkedList也可以作为FILO的栈,使用如下方法:
```java
push(e)
pop()
peek()
```
`源码解析`
```java
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;
}
}
```
LinkedList在内部定义了一个叫做Node类型的静态内部类,Node就是一个节点,链表中的节点,有3个属性。
```java
// 3个属性
transient int size = 0; // 集合链表内节点数量
transient Node<E> first; // 首节点
transient Node<E> last; // 尾节点
```
```java
// Appends the specified element to the end of this list
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
...
```
### Set接口源码解析
`总结`
```
Set是继承自Collection的接口,是一个不允许有重复元素的结合。
AbstractSet是一个抽象类,继承自AbstractCollection,AbstractCollection实现了Set中的绝大部分函数
HashSet和TreeSet是Set的两个实现类
HashSet依赖HashMap,它实际上是通过HashMap实现的,HashSet中的元素是无序的
TreeSet依赖TreeMap,它实际上是通过TreeMap实现的,TreeSet中的元素是有序的
```
#### AbstractSet源码解析
AbstractSet没有对Set做多少的实现,其继承了AbstractCollection
`源码解析`
```java
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Collection c = (Collection) o;
if (c.size() != size())
return false;
try {
return containsAll(c);
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
}
```
##### HashSet源码解析和使用
`总结`
```
HashSet是一个没有重复元素的集合,它是由HashMap实现的(HashMap中key不能重复),不保证元素的顺序,而且HashSet允许使用null元素。
HashSet是非同步的,因此如果多线程同时访问一个HashSet,而其中至少有一个线程修改了该HashSet夺得话,那么需要保持外部同步,通常可以对该Set的对象封装来完成同步操作,也可以使用Collections.synchronizedSet方法来完成。
HashSet是通过Iterator迭代遍历的
```
`常用方法`
```java
HashSet()
HashSet(int initialCapacity)
HashSet(int initialCapacity, float loadFactor)
HashSet(int initialCapacity, float loadFactor, boolean dummy)
HashSet(Collection<? extends E> c)
boolean add(E)
void clear()
Object clone()
boolean contains(Object object)
boolean isEmpty()
Iterator<E> iterator()
boolean remove(Object object)
int size()
```
`源码解析`
```java
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private transient HashMap<E,Object> map;
// new一个HashSet的时候其实是new的HashMap
public HashSet() {
map = new HashMap<>();
}
/*
* Constructs a new set containing the elements in the specified
* collection. The <tt>HashMap</tt> is created with default load factor
* (0.75) and an initial capacity sufficient to contain the elements in
* the specified collection.
*
* @param c the collection whose elements are to be placed into this set
* @throws NullPointerException if the specified collection is null
调用的是Math.max((int) (c.size()/.75f) + 1, 16), 比较(int) (c.size()/.75f) + 1和16的大小
选择加载因子为.75是出于效率的考虑(时间和空间成本)
如果HashMap的当前size >= threadhold(也就是Math.max((int) (c.size()/.75f) + 1, 16)),那么在添加元素的时候,size是要翻倍的,也就是说HashMap的容量必须是2的指数,具体跟踪put方法
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
/*
会重新计算capacity int capacity = roundUpToPowerOf2(toSize);
roundUpToPowerOf2(toSize)
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
*/
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); // 这里调用addEntry
return null;
}
// 迭代遍历的时候遍历的是key
public Iterator<E> iterator() {
return map.keySet().iterator();
}
// add的时候插入的是key
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
/** 浅拷贝
* Returns a shallow copy of this <tt>HashSet</tt> instance: the elements
* themselves are not cloned.
*
* @return a shallow copy of this set
*/
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
/**
* Save the state of this <tt>HashSet</tt> instance to a stream (that is,
* serialize it).
*
* @serialData The capacity of the backing <tt>HashMap</tt> instance
* (int), and its load factor (float) are emitted, followed by
* the size of the set (the number of elements it contains)
* (int), followed by all of its elements (each an Object) in
* no particular order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out HashMap capacity and load factor
s.writeInt(map.capacity());
s.writeFloat(map.loadFactor());
// Write out size
s.writeInt(map.size());
// Write out all elements in the proper order.
for (E e : map.keySet())
s.writeObject(e);
}
/**
* Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in HashMap capacity and load factor and create backing HashMap
int capacity = s.readInt();
float loadFactor = s.readFloat();
map = (((HashSet)this) instanceof LinkedHashSet ?
new LinkedHashMap<E,Object>(capacity, loadFactor) :
new HashMap<E,Object>(capacity, loadFactor));
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
E e = (E) s.readObject();
map.put(e, PRESENT);
}
}
```
##### TreeSet源码解析和使用
`总结`
```java
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable {}
```
```
TreeSet是一个有序并且没有重复的Set集合,它是通过TreeMap实现的
TreeSet实现了NavigableSet接口,因此其支持集合的导航方法,如lower(返回小于), floor(返回小于等于), ceiling(返回大于等于), higher(返回大于),如果不存在这样的元素,则返回null
```
`源码解析`
```java
// The backing map. 数据存储在这个对象中
private transient NavigableMap<E, Object> m;
private static final Object ORESENT = new Obect();
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
// 带比较器的构造函数
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
// 迭代器
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
/* Returns the least key greater than or equal to the given key, or {@code null} if there is no such key.
返回集合中大于等于给定元素的最小元素,有点绕,还是英文比较好理解
*/
public E ceiling(E e) {
return m.ceilingKey(e);
}
/*
Returns the least key strictly greater than the given key, or {@code null} if there is no such key.
返回集合中大于给定元素的最小元素
*/
public E higher(E e) {
return m.higherKey(e);
}
/*
Returns the greatest key strictly less than the given key, or {@code null} if there is no such key.
返回集合中小于给定元素的最大元素
*/
public E lower(E e) {
return m.lowerKey(e);
}
/*
Returns the greatest key less than or equal to the given key, or {@code null} if there is no such key.
返回几何中小于或等于给定元素的最大元素
*/
public E floor(E e) {
return m.floorKey(e);
}
```
### Queue接口源码解析
`源码分析`
```java
public interface Queue<E> extends Collection<E> {
boolean add(e) // add比offer的区别在于add时如果capacity超了,会报错,而offer不会
boolean offer(e)
E remove() // 返回队列的第一个元素,并且删除,如果队列为空,报NoSuchElementException
E poll() // 返回队列的第一个元素,并且删除,如果队列为空,返回null
E element() // 返回队列的第一个元素,不删除,如果队列为空,报NoSuchElementException
E peek() // 返回队列的第一个元素,不删除,如果队列为空,返回null
}
```
### Deque接口源码解析
`总结`
```
双向队列,继承自Queue接口,同时提供了丰富的操作队列的方法,具体可参考LinkedList源码分析
```
##### LinkedList使用
Go to here [LinkedList源码解析和使用](#LinkedList源码解析和使用)
## Map集合下常用实现类详解
`总结`
```
Map是一个键值对的接口,Map<K, V>
AbstractMap实现了Map接口,但是几乎没有实现Map中的方法,但是却定义了一些常用的方法
SortedMap继承自Map接口,SortedMap中的内容是排序了的键值对,排序的方法是通过比较器(Comparator)
NavigableMap是继承自SortedMap的接口,相对于SortedMap,NavigableMap有一系列的导航方法,如获取>, <, >=, <=的值
TreeMap继承自AbstractMap,实现了NavigableMap接口,因此,TreeMap是有序的键值对
HashMap继承自AbstractMap,没有实现SortedMap,因此,HashMap不是有序的键值对。HashMap允许插入key或者value为null的元素
Hashtable没有继承自AbstractMap,继承的是Dictionary,实现了Map接口,因此,Hashtable是无序的键值对。Hashtable不允许插入key或者value为null的元素,Hashtable的方法加了synchronized关键字,保证了线程的安全。
WeakhashMap继承自AbstractMap,大致来说它与HashMap的键类型不同,WeakHashMap使用的是“弱键”(内存不足时会被GC收掉)
```
`源码分析`
```java
void clear();
boolean containsKey(Object key);
boolean containsValue(Object value);
Set<Map.Entry<K, V> entrySet();
boolean equals(Object o);
V get(Object obj);
boolean isEmpty();
Set<K> keySet(); // 返回key的集合,因为key不重复,所以用Set接收
V put(K k, V v);
void putAll(Map<? extends K, ? extends V> m);
V remove(Object key);
int size();
Collections<V> values(); // 返回value的结合,values是重复的
// Map中还有一个内置的接口 Map#entrySet()
interface Entry<K,V> {
K getKey();
V getValue();
int hashCode();
V setValue(V);
boolean equals(Object obj)
}
```
#### AbstractMap接口源码解析
AbstractMap实现了Map接口,实现了一些通用的方法
`源码解析`
```java
// 巧妙的写法
private static boolean eq(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}
```
##### HashMap源码解析和使用
`定义`
```java
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {}
```
`构造函数`
```java
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); // initial capacity=16 load factor=0.75
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {}
public HashMap(Map<? extends K, ? extends V> m) {}
```
`public method`
```java
void clear()
Object clone()
boolean containsKey(Object key)
boolean containsValue(Object value)
Set<Entry<K, V>> entrySet()
V get(Object obj)
boolean isEmpty()
Set<K> keySet()
V put(K k, V v)
void putAll(Map<? extends K, ? extends V>)
V remove(Object obj)
int size()
String toString()
Collection<V> values()
```
`源码解析`
```java
// 数据存储在这里,一个叫table的变量中
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 看下Entry的定义,每一个Entry是一个单向链表
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
// 接下来我们就看下HashMap是如何存储值的。我们都知道HashMap中使用put(K k, V v)来存储值
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value); // 存储null key,直接调价到table[0]中
int hash = hash(key); // 首先根据key计算出hash值
int i = indexFor(hash, table.length); // 再根据hash值,计算出数据索引,也就是Entry<K, V>在table中的索引
// 然后根据索引找到table中的Entry(是一个单向链表),通过e.next循环遍历单项链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 将key与每一个Entry的key进行对比,哈希值进行对比,如果key已经存在就替换掉旧值,并且返回旧值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 如果key不存在Entry链表中,就新建一个Entry
addEntry(hash, key, value, i);
return null;
}
// addEntry的时候索引值为0,
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
// 在table中的index是0,所以HashMap有一个固定存储key为null的值,此位置为table的第一个位置
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); // size翻倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
// 插入null值之后,循环调用Map#put方法插入1-18
::hash:: 0 ::key:: null ::value:: 1 ::bucketIndex:: 0
::hash:: 50 ::key:: 1 ::value:: value 1 ::bucketIndex:: 2
::hash:: 49 ::key:: 2 ::value:: value 2 ::bucketIndex:: 1
::hash:: 48 ::key:: 3 ::value:: value 3 ::bucketIndex:: 0
::hash:: 55 ::key:: 4 ::value:: value 4 ::bucketIndex:: 7
::hash:: 54 ::key:: 5 ::value:: value 5 ::bucketIndex:: 6
::hash:: 53 ::key:: 6 ::value:: value 6 ::bucketIndex:: 5
::hash:: 52 ::key:: 7 ::value:: value 7 ::bucketIndex:: 4
::hash:: 59 ::key:: 8 ::value:: value 8 ::bucketIndex:: 11
::hash:: 58 ::key:: 9 ::value:: value 9 ::bucketIndex:: 10
::hash:: 1650 ::key:: 10 ::value:: value 10 ::bucketIndex:: 2
::hash:: 1614 ::key:: 11 ::value:: value 11 ::bucketIndex:: 14
::hash:: 1615 ::key:: 12 ::value:: value 12 ::bucketIndex:: 15
::hash:: 1612 ::key:: 13 ::value:: value 13 ::bucketIndex:: 12
::hash:: 1613 ::key:: 14 ::value:: value 14 ::bucketIndex:: 13
::hash:: 1610 ::key:: 15 ::value:: value 15 ::bucketIndex:: 10
::hash:: 1611 ::key:: 16 ::value:: value 16 ::bucketIndex:: 11
::hash:: 1608 ::key:: 17 ::value:: value 17 ::bucketIndex:: 8
```
`总结`
```
HashMap继承于AbstractMap类,实现了Map接口。Map是"key-value键值对"接口,AbstractMap实现了"键值对"的通用函数接口。
HashMap是通过"拉链法"实现的哈希表。它包括几个重要的成员变量:table, size, threshold, loadFactor, modCount。
table是一个Entry[]数组类型,而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。
size是HashMap的大小,它是HashMap保存的键值对的数量。
threshold是HashMap的阈值,用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子",当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。
loadFactor就是加载因子。
modCount是用来实现fail-fast机制的。
```
##### WeakHashMap源码解析和使用
`定义`
```java
public class WeakhashMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {}
```
`构造函数和HashMap类似`
```java
public WeakHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public WeakHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public WeakHashMap(int initialCapacity, float loadFactor) {}
public WeakHashMap(Map<? extends K, ? extends V> m) {}
```
`重要变量`
```java
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final float DEFAULT_LOAD_FACTOR = 0.75F;
Entry<K, V>[] table;
private int size;
private int threshold;
private final float loadFactor;
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
int modCount;
```
`总结`
```