Java集合框架详解-阿里云开发者社区

开发者社区> benjaminwhx> 正文

Java集合框架详解

简介:
+关注继续查看

这篇文章详细对比以及分析了Java的集合框架的原理使用以及比较。

ArrayList

ArrayList就是传说中的动态数组,就是Array的复杂版本,它提供了如下一些好处:动态的增加和减少元素、灵活的设置数组的大小……
ArrayList底层是数组,并且add remove指定位置元素的时候,是通过memcpy来实现的。我们直接来看源码:
ArrayList源码分析:

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
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;

/**
* 默认初始化容量
*/

private static final int DEFAULT_CAPACITY = 10;

/**
* 实例化空Object数组
*/

private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 用于默认大小的容量(10)来实例化空Object数组
*/

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 数组缓冲区中数组元素的存储.ArrayList的容量是数组缓冲区的长度.任何时候
* elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的时候都会扩充一个默认
* 大小的容量 DEFAULT_CAPACITY
*/

transient Object[] elementData; // non-private to simplify nested class access

/**
* ArrayList的大小
*/

private int size;

/**
* 指定容量的构造器
*
* @param initialCapacity 初始化容量
* @throws IllegalArgumentException 初始化容量 <0 的时候抛出
*/

public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

/**
* 构造一个默认长度 DEFAULT_CAPACITY=10 的空数组elementData
*/

public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
* 指定一个集合来构造list包含这些元素.内部的集合排序不变.
*
* @param c 即将被加入list的元素集合
* @throws NullPointerException 指定集合为null
*/

public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

/**
* 缩减ArrayList的大小为size
由于elementData的长度会被拓展,size标记的是其中包含的元素的个数。所以会出现size很小但elementData.length很大的情况,将出现空间的浪费。trimToSize将返回一个新的数组给elementData,元素内容保持不变,length很size相同,节省空间。
*/

public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

/**
* 增加容量,minCapacity要超过minExpand
*
* @param minCapacity 所需的最小容量
*/

public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;

if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}

private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
* 对数组增加容量
*
* @param minCapacity 增加的最小容量
*/

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); // 指定容量构造新数组
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

/**
* list中元素的个数
*
* @return list中元素的个数
*/

public int size() {
return size;
}

/**
* 如果list没有包含元素,返回true
*
* @return 如果list没有包含元素,返回true
*/

public boolean isEmpty() {
return size == 0;
}

/**
* list中如果包含传入的元素,返回true
*
* @param o 指定的查找元素
* @return list中如果包含传入的元素,返回true
*/

public boolean contains(Object o) {
return indexOf(o) >= 0;
}

/**
* 返回指定元素在list中的位置,如果不存在返回-1.
* 如果存在,返回第一个找到的元素index
*/

public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

/**
* 如果list没有包含元素,返回-1
* 如果包含了元素,返回最后一个元素的index
*/

public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else { // 把数组进行倒序遍历
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

/**
* 返回一个ArrayList实例的浅拷贝
*
* @return 返回一个ArrayList实例的浅拷贝
*/

public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// 这个永远不会发生,因为我们是可克隆的
throw new InternalError(e);
}
}

/**
* 把List转为数组
*
* @return list转为的数组
*/

public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}

// Positional Access Operations

@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}

/**
* 返回指定位置的元素
*
* @param index 指定的位置
* @return 返回指定位置的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/

public E get(int index) {
rangeCheck(index);

return elementData(index);
}

/**
* 替换指定位置的元素为传入的新元素
*
* @param index 指定的位置
* @param element 即将要替换指定位置元素的新元素
* @return 指定位置之前的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/

public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

/**
* 在list结尾增加一个元素
*
* @param e 即将要增加的元素
* @return true
*/

public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

/**
* 在指定的位置插入一个元素,原来位置的元素以及后面的所有元素向后移
* System.arraycopy(elementData, index, elementData, index + 1,
* size - index);这句copy是关键,把原来数组的index位置后面的元素复制到
* 当前数组index+1的位置,成功后移.
*
* @param index 指定位置
* @param element 插入的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/

public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

/**
* 移除指定位置的元素,后面的所有元素前移
* 移动的方法和上面的 add(int index, E element) 方法类似
* 利用了System.arraycopy实现
*
* @param index 移除元素的位置
* @return 移除位置之前的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/

public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

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

return oldValue;
}

/**
* 移除list中存在的传入对象
*
* @param o 将要被移除的对象
* @return 如果存在指定元素,返回true
*/

public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}

/**
* 快速移除指定索引元素
* 使用了高效的 System.arraycopy 方法
*/

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
}

/**
* 移除list中所有元素,全部置为null
*/

public void clear() {
modCount++;

// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;

size = 0;
}

/**
* 把传入的所有集合元素加入list中
*
* @param c 将要被加入list的集合元素
* @return 如果集合元素个数 >0 返回true
* @throws NullPointerException 指定的集合为null
*/

public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

/**
* 指定位置插入传入的集合元素
*
* @param index 指定的位置
* @param c 要被加入list的集合元素
* @return 如果集合元素个数 >0 返回true
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException 指定的集合为null
*/

public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);

Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount

int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);

System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}

/**
* 移除范围内的所有元素 (fromIndex, toIndex)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex}
* fromIndex < 0 || fromIndex >= size || toIndex >= size || toIndex < fromIndex
*/

protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);

// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}

/**
* 检查index范围,超过size抛出 IndexOutOfBoundsException
* 如果index为负数,抛出 ArrayIndexOutOfBoundsException
*/

private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
* 增加元素的范围检查
*/

private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
* 构建 IndexOutOfBoundsException 时需要的message
*/

private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}

/**
* 移除list中所有的指定集合中的元素
*
* @param c 集合
* @return 如果list改变,返回true
* @throws ClassCastException
*/

public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}

/**
* 如果传入的集合中有元素在list中,则保留不删除,其他的全部删除
*
* @param c 集合
* @return 如果list改变,返回true
* @throws ClassCastException
*/

public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}

/**
* 通过流写出所有集合对象
*
* @serialData The length of the array backing the <tt>ArrayList</tt>
* instance is emitted (int), followed by all of its elements
* (each an <tt>Object</tt>) in the proper order.
*/

private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();

// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);

// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}

if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

/**
* 还原集合对象
*/

private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;

// Read in size, and any hidden stuff
s.defaultReadObject();

// Read in capacity
s.readInt(); // ignored

if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);

Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}

/**
* 从传入的位置遍历集合
*
* 返回listIterator
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/

public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}

/**
* 返回一个遍历的集合
*
* 返回listIterator
*
* @see #listIterator(int)
*/

public ListIterator<E> listIterator() {
return new ListItr(0);
}

/**
* 返回一个迭代器
*
* @return 迭代器
*/

public Iterator<E> iterator() {
return new Itr();
}

/**
* 优化版本的迭代器
*/

private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;

public boolean hasNext() {
return cursor != size;
}

@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}

public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

/**
* ListItr的优化
*/

private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}

public boolean hasPrevious() {
return cursor != 0;
}

public int nextIndex() {
return cursor;
}

public int previousIndex() {
return cursor - 1;
}

@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}

public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

public void add(E e) {
checkForComodification();

try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
}

源码中存放数据的数组是用transient关键字定义的

private transient Object[] elementData;  

那什么是transient呢?

Java的serialization提供了一种持久化对象实例的机制。当持久化对象时,可能有一个特殊的对象数据成员,我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization,可以在这个域前加上关键字transient。
ansient是Java语言的关键字,用来表示一个域不是该对象串行化的一部分。当一个对象被串行化的时候,transient型变量的值不包括在串行化的表示中,然而非transient型的变量是被包括进去的。

在使用ArrayList的toArray方法时候,因为不支持Object[]向下转型,所以我们使用 T[] toArray(T[] a) 这个方法。
下面是使用方法:

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
String[] str = new String[4];
list.toArray(str);
for (String s : str) {
System.out.println(s);
}
}

LinkedList


LinkedList也和ArrayList一样实现了List接口,但是它执行插入和删除操作时比ArrayList更加高效,因为它是基于链表的。基于链表也决定了它在随机访问方面要比ArrayList逊色一点。
下面是我根据源码自己写出来的LinkedList,其实就是双向链表。在我的双向链表文章中已经详细讲过了。需要看的朋友请移步前去看,这里就不废话了。

Vector


vector实际上实现的原理和ArrayList大部分都相同,不同的地方就是它绝大部分方法都使用了Synchronized同步。所以会很影响性能。
源码就不看了,如果想看的朋友可以看看这篇文章:

Vector详解


HashSet

对于HashSet而言,它是基于HashMap实现的,HashSet底层采用HashMap来保存所有元素,因此HashSet的实现比较简单,查看HashSet的源代码,可以看到:

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
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;

// 底层使用HashMap来保存HashSet中所有元素。
private transient HashMap<E,Object> map;

// 定义一个虚拟的Object对象作为HashMap的value,将此对象定义为static final。
private static final Object PRESENT = new Object();

/**
* 默认的无参构造器,构造一个空的HashSet。
*
* 实际底层会初始化一个空的HashMap,并使用默认初始容量为16和加载因子0.75。
*/
public HashSet() {
map = new HashMap<E,Object>();
}

/**
* 构造一个包含指定collection中的元素的新set。
*
* 实际底层使用默认的加载因子0.75和足以包含指定
* collection中所有元素的初始容量来创建一个HashMap。
* @param c 其中的元素将存放在此set中的collection。
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}

/**
* 以指定的initialCapacity和loadFactor构造一个空的HashSet。
*
* 实际底层以相应的参数构造一个空的HashMap。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}

/**
* 以指定的initialCapacity构造一个空的HashSet。
*
* 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
* @param initialCapacity 初始容量。
*/
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}

/**
* 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
* 此构造函数为包访问权限,不对外公开,实际只是是对LinkedHashSet的支持。
*
* 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
* @param dummy 标记。
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

/**
* 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。
*
* 底层实际调用底层HashMap的keySet来返回所有的key。
* 可见HashSet中的元素,只是存放在了底层HashMap的key上,
* value使用一个static final的Object对象标识。
* @return 对此set中元素进行迭代的Iterator。
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}

/**
* 返回此set中的元素的数量(set的容量)。
*
* 底层实际调用HashMap的size()方法返回Entry的数量,就得到该Set中元素的个数。
* @return 此set中的元素的数量(set的容量)。
*/
public int size() {
return map.size();
}

/**
* 如果此set不包含任何元素,则返回true。
*
* 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。
* @return 如果此set不包含任何元素,则返回true。
*/
public boolean isEmpty() {
return map.isEmpty();
}

/**
* 如果此set包含指定元素,则返回true。
* 更确切地讲,当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))
* 的e元素时,返回true。
*
* 底层实际调用HashMap的containsKey判断是否包含指定key。
* @param o 在此set中的存在已得到测试的元素。
* @return 如果此set包含指定元素,则返回true。
*/
public boolean contains(Object o) {
return map.containsKey(o);
}

/**
* 如果此set中尚未包含指定元素,则添加指定元素。
* 更确切地讲,如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2))
* 的元素e2,则向此set 添加指定的元素e。
* 如果此set已包含该元素,则该调用不更改set并返回false。
*
* 底层实际将将该元素作为key放入HashMap。
* 由于HashMap的put()方法添加key-value对时,当新放入HashMap的Entry中key
* 与集合中原有Entry的key相同(hashCode()返回值相等,通过equals比较也返回true),
* 新添加的Entry的value会将覆盖原来Entry的value,但key不会有任何改变,
* 因此如果向HashSet中添加一个已经存在的元素时,新添加的集合元素将不会被放入HashMap中,
* 原来的元素也不会有任何改变,这也就满足了Set中元素不重复的特性。
* @param e 将添加到此set中的元素。
* @return 如果此set尚未包含指定元素,则返回true。
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

/**
* 如果指定元素存在于此set中,则将其移除。
* 更确切地讲,如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e,
* 则将其移除。如果此set已包含该元素,则返回true
* (或者:如果此set因调用而发生更改,则返回true)。(一旦调用返回,则此set不再包含该元素)。
*
* 底层实际调用HashMap的remove方法删除指定Entry。
* @param o 如果存在于此set中则需要将其移除的对象。
* @return 如果set包含指定元素,则返回true。
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}

/**
* 从此set中移除所有元素。此调用返回后,该set将为空。
*
* 底层实际调用HashMap的clear方法清空Entry中所有元素。
*/
public void clear() {
map.clear();
}

/**
* 返回此HashSet实例的浅表副本:并没有复制这些元素本身。
*
* 底层实际调用HashMap的clone()方法,获取HashMap的浅表副本,并设置到HashSet中。
*/
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();
}
}
}

由上面源程序可以看出,HashSet 的实现其实非常简单,它只是封装了一个 HashMap 对象来存储所有的集合元素,所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存,而 HashMap 的 value 则存储了一个 PRESENT,它是一个静态的 Object 对象。

HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的,因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。

下面是一个HashSet的例子:

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
package Collections;

/**
* Created by piqiu on 1/16/16.
*/

public class Name {

private String first;
private String last;

public Name(String first, String last) {
this.first = first;
this.last = last;
}

public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o.getClass() == Name.class) {
Name n = (Name)o;
return n.first.equals(first);
}
return false;
}

@Override
public String toString() {
return "Name{first='" + first + '\'' +
", last='" + last + '\'' +
'}';
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package Collections;

import java.util.HashSet;
import java.util.Set;

/**
* Created by piqiu on 1/16/16.
*/

public class CollectionsTest {

public static void main(String[] args) {
Set<Name> set = new HashSet<>();
set.add(new Name("abc", "123"));
System.out.println(set.contains(new Name("abc", "123"))); // false
}
}

这段测试居然输出false。这是因为 HashSet 判断两个对象相等的标准除了要求通过 equals() 方法比较返回 true 之外,还要求两个对象的 hashCode() 返回值相等。而上面程序没有重写 Name 类的 hashCode() 方法,两个 Name 对象的 hashCode() 返回值并不相同,因此 HashSet 会把它们当成 2 个对象处理,因此程序返回 false。

由此可见,当我们试图把某个类的对象当成 HashMap 的 key,或试图将这个类的对象放入 HashSet 中保存时,重写该类的 equals(Object obj) 方法和 hashCode() 方法很重要,而且这两个方法的返回值必须保持一致:当该类的两个的 hashCode() 返回值相同时,它们通过 equals() 方法比较也应该返回 true。通常来说,所有参与计算 hashCode() 返回值的关键属性,都应该用于作为 equals() 比较的标准。

我们在刚刚的实体中加入重写的hashCode方法,再进行一个测试:

1
2
3
public int hashCode() {
return first.hashCode();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package Collections;

import java.util.HashSet;
import java.util.Set;

/**
* Created by piqiu on 1/16/16.
*/

public class CollectionsTest {

public static void main(String[] args) {
Set<Name> set = new HashSet<>();
set.add(new Name("abc", "123"));
set.add(new Name("abc", "456"));
System.out.println(set); // [Name{first='abc', last='123'}]
}
}

根据equals和hashcode的比较,只要first属性相同,就认为这两个对象是同一个对象。那么不难想象上面的程序只包含一个对象了。

LinkedHashSet

LinkedHashSet概述:


LinkedHashSet是具有可预知迭代顺序的Set接口的哈希表和链接列表实现。此实现与HashSet的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可为插入顺序或是访问顺序。
注意,此实现不是同步的。如果多个线程同时访问链接的哈希Set,而其中至少一个线程修改了该Set,则它必须保持外部同步。

LinkedHashSet的实现:


对于LinkedHashSet而言,它继承与HashSet、又基于LinkedHashMap来实现的。
LinkedHashSet底层使用LinkedHashMap来保存所有元素,它继承与HashSet,其所有的方法操作上又与HashSet相同,因此LinkedHashSet 的实现上非常简单,只提供了四个构造方法,并通过传递一个标识参数,调用父类的构造器,底层构造一个LinkedHashMap来实现,在相关操作上与父类HashSet的操作相同,直接调用父类HashSet的方法即可。LinkedHashSet的源代码如下:

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
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {

private static final long serialVersionUID = -2851667679971038690L;

/**
* 构造一个带有指定初始容量和加载因子的新空链接哈希set。
*
* 底层会调用父类的构造方法,构造一个有指定初始容量和加载因子的LinkedHashMap实例。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
*/
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}

/**
* 构造一个带指定初始容量和默认加载因子0.75的新空链接哈希set。
*
* 底层会调用父类的构造方法,构造一个带指定初始容量和默认加载因子0.75的LinkedHashMap实例。
* @param initialCapacity 初始容量。
*/
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}

/**
* 构造一个带默认初始容量16和加载因子0.75的新空链接哈希set。
*
* 底层会调用父类的构造方法,构造一个带默认初始容量16和加载因子0.75的LinkedHashMap实例。
*/
public LinkedHashSet() {
super(16, .75f, true);
}

/**
* 构造一个与指定collection中的元素相同的新链接哈希set。
*
* 底层会调用父类的构造方法,构造一个足以包含指定collection
* 中所有元素的初始容量和加载因子为0.75的LinkedHashMap实例。
* @param c 其中的元素将存放在此set中的collection。
*/
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
}

在父类HashSet中,专为LinkedHashSet提供的构造方法如下,该方法为包访问权限,并未对外公开。

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
* 此构造函数为包访问权限,不对外公开,实际只是是对LinkedHashSet的支持。
*
* 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
* @param dummy 标记。
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

由上述源代码可见,LinkedHashSet通过继承HashSet,底层使用LinkedHashMap,以很简单明了的方式来实现了其自身的所有功能。

TreeSet

查看TreeSet的源码可以发现,它是利用TreeMap来实现的。
TreeSet是无序的(关于这个是不是有序无序,在总结里面讲的很清楚)。但是它可以自定义排序规则,使它按照某种顺序排列。我们可以自定义比较器,也可以把比较器传给TreeSet构造一个拥有自定义比较器的Set。

在TreeSet里面放入Integer和String的时候,系统会默认帮我们排序。因为它们都已经实现了Comparable接口,并且重写了compareTo方法。我们自己定义一个类放入TreeSet的时候,务必要重写实现Comparable并且重写compareTo方法。

private transient NavigableMap<E,Object> m;

这个是TreeSet中存放对象的Map,这个NavigableMap继承于SortedMap,而SortedMap继承于Map。很明显,这个Map带有排序功能。

public TreeSet() {
    this(new TreeMap<E,Object>());
}
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

这两个构造函数说明了,默认是以TreeMap来实现的。所以,这里就不讲太多它的实现,我们会在TreeMap部分讲解。
下面是TreeSet的使用:

第一种,我们可以让我们的实体实现Comparable接口。

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
package Collections;

/**
* Created by piqiu on 1/16/16.
*/
public class Student implements Comparable<Student>{

private int studentNo;
private String studentName;

public Student(int studentNo, String studentName) {
this.studentNo = studentNo;
this.studentName = studentName;
}

public String toString() {
return "学号: " + studentNo + "\t姓名: " + studentName;
}

/**
* 排序规则是按照学号从大到小排列
* 如果学号相等,那就按姓名字母从低到高排列(String默认排序)
* @param o 比较的Student
* @return 顺序
*/
@Override
public int compareTo(Student o) {
int result = studentNo < o.studentNo ? 1 : (studentNo == o.studentNo ? 0 : -1);
if (result == 0) {
result = studentName.compareTo(o.studentName);
}
return result;
}
}
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
package Collections;

import java.util.TreeSet;

/**
* Created by piqiu on 1/16/16.
*/

public class CollectionsTest {

public static void main(String[] args) {
TreeSet<Student> set = new TreeSet<>();
set.add(new Student(1001, "zhangsan"));
set.add(new Student(1004, "lisi"));
set.add(new Student(1003, "wangwu"));
set.add(new Student(1003, "zhaoliu"));
set.add(new Student(1002, "benjamin"));
for (Student s : set) {
System.out.println(s);
}

/**
* 学号: 1004 姓名: lisi
学号: 1003 姓名: wangwu
学号: 1003 姓名: zhaoliu
学号: 1002 姓名: benjamin
学号: 1001 姓名: zhangsan
*/

}
}

还有一种,我们可以自定义一个构造器,通过构造方法传入TreeSet

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
package Collections;

import java.util.Comparator;

/**
* Created by piqiu on 1/16/16.
*/
public class Student {

private int studentNo;
private String studentName;

public Student(int studentNo, String studentName) {
this.studentNo = studentNo;
this.studentName = studentName;
}

public String toString() {
return "学号: " + studentNo + "\t姓名: " + studentName;
}

/**
* 排序规则是按照学号从大到小排列
* 如果学号相等,那就按姓名字母从低到高排列(String默认排序)
*/
static class StudentComparable implements Comparator<Student> {

@Override
public int compare(Student o1, Student o2) {
int result = o1.studentNo < o2.studentNo ? 1 : (o1.studentNo == o2.studentNo ? 0 : -1);
if (result == 0) {
result = o1.studentName.compareTo(o2.studentName);
}
return result;
}
}
}
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
package Collections;

import java.util.TreeSet;

/**
* Created by piqiu on 1/16/16.
*/

public class CollectionsTest {

public static void main(String[] args) {
TreeSet<Student> set = new TreeSet<>(new Student.StudentComparable());
set.add(new Student(1001, "zhangsan"));
set.add(new Student(1004, "lisi"));
set.add(new Student(1003, "wangwu"));
set.add(new Student(1003, "zhaoliu"));
set.add(new Student(1002, "benjamin"));
for (Student s : set) {
System.out.println(s);
}

/**
* 学号: 1004 姓名: lisi
学号: 1003 姓名: wangwu
学号: 1003 姓名: zhaoliu
学号: 1002 姓名: benjamin
学号: 1001 姓名: zhangsan
*/

}
}

HashMap


有空再进行整理

HashTable


有空再进行整理

TreeMap


有空再进行整理

总结

Java中有序和无序的概念


    有序指的是存储顺序与添加顺序相同,并且可以通过下标访问,List就是这样。
    无序刚好相反,指的是存储顺序与添加顺序无关,没有下标,当然也不可能通过下标访问,Set就是如此。
    这里需要注意的是,有序、无序中的“序”与我们平常所说的顺序无关。
而TreeSet是无序,但又是排好序的。即添加顺序与存储顺序无关,但是其中的对象实现了排序。

Set集合总体分析


    HashSet的元素存放顺序和添加进去时候的顺序没有任何关系;而LinkedHashSet 则保持元素的添加顺序;TreeSet则是对我们的Set中的元素进行排序存放。
    一般来说,当要从集合中以有序的方式抽取元素时,TreeSet 实现就会有用处。为了能顺利进行,添加到 TreeSet 的元素必须是可排序的。 而同样需要对添加到TreeSet中的类对象实现 Comparable 接口的支持。对于Comparable接口的实现。假定一棵树知道如何保持 java.lang 包装程序器类元素的有序状态。一般说来,先把元素添加到 HashSet,再把集合转换为 TreeSet 来进行有序遍历会更快。这点和HashMap的使用非常的类似。
    其实Set的实现原理是基于Map上面的。Set中很多实现类和Map中的一些实现类的使用上非常的相似。Map中的“键值对”,其中的 “键”是不能重复的。这个和Set中的元素不能重复一致,其实Set利用的就是Map中“键”不能重复的特性来实现的。 HashSet的巧妙实现:就是建立一个“键值对”,“键”就是我们要存入的对象,“值”则是一个常量。这样可以确保, 我们所需要的存储的信息之是“键”。而“键”在Map中是不能重复的,这就保证了我们存入Set中的所有的元素都不重复。而判断是否添加元素成功,则是通 过判断我们向Map中存入的“键值对”是否已经存在,如果存在的话,那么返回值肯定是常量:PRESENT ,表示添加失败。如果不存在,返回值就为null 表示添加成功。

List集合总体分析


Vector的方法都是同步的(Synchronized),是线程安全的(thread-safe),而ArrayList的方法不是,由于线程的同步必然要影响性能,因此,ArrayList的性能要比Vector好。
当Vector或ArrayList中的元素超过它的初始大小时,Vector会将它的容量翻倍,而ArrayList只增加50%大小,这样,ArrayList就有利于节约内存空间。
而ArrayList和LinkedList通过源码发现有很大差别。一个是基于数组实现的,一个是基于链表实现。这样,当ArrayList在插入数据时,必须将所有后面的数据后移,这样必然要花费较多时间。所以,当你的操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能。而访问链表中的某个元素时,就必须从链表的一端开始沿着连接方向一个一个元素地去查找,直到找到所需的元素为止,所以,当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Android Java 框架基础[知识点汇总]
学习android的过程中,把整个框架的基础结构牢记很重要,特此摘录了一些这个框架的一些基础知识,在使用的过程中按照这个框架学习,事半功倍。 开发过程中参考JDK的文档和android的sdk文档可以清楚遇到的很多问题,遇到问题是现在这两个文档中一般都能找到原因(安装sdk的文档参考http://www.
754 0
java干货spring框架
1、什么是Spring框架?Spring框架有哪些主要模块?  Spring框架是一个为Java应用程序的开发提供了综合、广泛的基础性支持的Java平台。Spring帮助开发者解决了开发中基础性的问题,使得开发人员可以专注于应用程序的开发。
847 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4478 0
Java集合框架
一、集合: 集合是Java API所提供的一系列类的实例,可以用于动态存放多个对象 为什么要使用集合?数组的长度是固定的,存满了就不能存了。集合可以存储不同类型的对象,而且它的容量可以随着对象数量的增加,自动扩大。
556 0
Java Executor 框架
Executor框架是指java5中引入的一系列并发库中与executor相关的功能类,包括Executor、Executors、ExecutorService、CompletionService、Future、Callable等。
653 0
Python3 | Django后台管理框架Xadmin安装指南
Django是python的重量级web框架,写得少,做得多,非常适合后端开发,它很大的一个亮点是,自带后台管理模块,但它自带的后台管理有点丑,而Xadmin是基于bootstrap开发的一套后台管理框架,界面非常美观,只需几步就可以替换自带的Dja...
1253 0
+关注
194
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载