More
More
文章目录
  1. HashSet
  2. LinkedHashSet
  3. TreeSet
  4. 说点什么:
  5. 知识点:

【java源码一带一路系列】之HashSet、LinkedHashSet、TreeSet

Map篇暂告段落,却并非离我们而去。这不在本篇中你就能经常见到她。HashSet、LinkedHashSet、TreeSet各自基于对应Map实现,各自源码内容较少,因此归纳为一篇。

HashSet

1
2
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

HashSet基于HashMap实现;而Map是键值对形式的,因此构造一个PRESENT假装为值。


同样在HashSet源码的Line273Line294分别见看到老朋友writeObject()和readObject()。使用它们自定义序列化规则,将不会调用默认的序列化方法。

这样做可以降低性能消耗的同时,还可以减少序列化字节流的大小,从而减少网络开销(RPC框架中)。[①]

记得在之前的文章中留了一个问题。即该private方法供谁调用?解释如下,然而笔者并未在ObjectOutputStream源码中找到getPrivateMethod方法,不知是否由于版本不同还是作者笔误。倒是在ObjectStreamClass中找到了getPrivateMethod()。

ObjectOutputStream使用了反射来寻找是否声明了这两个方法。因为ObjectOutputStream使用getPrivateMethod,所以这些方法不得不被声明为priate以至于供ObjectOutputStream来使用。 [②]

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
/**
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
* set.
*
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and
* {@link Spliterator#DISTINCT}. Overriding implementations should document
* the reporting of additional characteristic values.
*
* @return a {@code Spliterator} over the elements in this set
* @since 1.8
*/
public Spliterator<E> spliterator() {
return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
}
// HashMap源码中
static final class KeySpliterator<K,V>
extends HashMapSpliterator<K,V>
implements Spliterator<K> {
KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
public KeySpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
public void forEachRemaining(Consumer<? super K> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
Node<K,V>[] tab = m.table;
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = (tab == null) ? 0 : tab.length;
}
else
mc = expectedModCount;
if (tab != null && tab.length >= hi &&
(i = index) >= 0 && (i < (index = hi) || current != null)) {
Node<K,V> p = current;
current = null;
do {
if (p == null)
p = tab[i++];
else {
action.accept(p.key);
p = p.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
public boolean tryAdvance(Consumer<? super K> action) {
int hi;
if (action == null)
throw new NullPointerException();
Node<K,V>[] tab = map.table;
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index < hi) {
if (current == null)
current = tab[index++];
else {
K k = current.key;
current = current.next;
action.accept(k);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
}
}
return false;
}
public int characteristics() {
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
Spliterator.DISTINCT;
}
}

spliterator()将Set中所有元素封装中并返回,依靠HashMap.KeySpliterator()方法来实现。HashMap.KeySpliterator重写了Spliterator接口的一些方法:

tryAdvance:如果存在没处理(action.accept(k))的数据,执行指定的代码并返回true;若不存在,直接返回false;单次;

forEachRemaining:循环对所有数据进行处理(action.accept(p.key));

trySplit:分割出一个新的Spliterator,从“mid = (lo + hi) >>> 1;”来看,KeySpliterator是对半切割的。

characteristics:返回特征值。这里只会有2种结果。Spliterator.SIZED(0x00000040)|Spliterator.DISTINCT(0x00000001)=65(十进制)和0|Spliterator.DISTINCT(0x00000001)=1,通过返回值能反应KeySpliterator当前状态。因为一旦调用以上方法处理数据,fence值就会被改变,即从65变为1(个人理解,网上资料凤毛麟角)。

“jdk1.8中的集合框架中的数据结构都默认实现了Spliterator。”(惭愧的是当时在看HashMap并没有注意到,由于Set代码行数少,反倒引起了关注。)看看下面的执行结果你是否能全部bingo呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
HashSet hs = new HashSet();
hs.add("c");
hs.add("h");
hs.add("e");
Spliterator<String> spliterator = hs.spliterator();
System.out.println("characteristics:"+spliterator.characteristics());
Spliterator<String> spliterator2 = spliterator.trySplit();
while(spliterator.tryAdvance(t -> System.out.println("tryAdvance:"+t.toString())));
while(spliterator2.tryAdvance(t -> System.out.println("trySplit:"+t.toString())));
System.out.println("characteristics:"+spliterator.characteristics());
hs.spliterator().forEachRemaining(t -> System.out.println("forEachRemaining:"+t.toString()));

LinkedHashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* Constructs a new, empty linked hash set. (This package private
* constructor is only used by LinkedHashSet.) The backing
* HashMap instance is a LinkedHashMap with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hash map
* @param loadFactor the load factor of the hash map
* @param dummy ignored (distinguishes this
* constructor from other int, float constructor.)
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

增加dummy标志与HashSet(int initialCapacity, float loadFactor, boolean dummy)构造方法区分开来,供LinkedHashSet调用。

TreeSet

略。(是不是有种翻阅课后答案参考书的感觉- -)

说点什么:

HashSet无序;允许值为null;非线程安全;底层增删等操作基于HashMap实现;

LinkedHashSet有序;允许值为null;非线程安全;依赖于HashSet,底层增删等操作基于LinkedHashMap实现;

TreeSet有序;不允许为null;非线程安全;底层增删等操作基于TreeMap实现。

从查阅Spliterator相关资料的感受就是J8的一些技术点在国内应用貌似还不是那么普及。③中举了25个java.util.Spliterators在实际项目中的应用,感兴趣的同学可以深入学习。

知识点:

java序列化用法以及理论(三);

什么是writeObject 和readObject?可定制的序列化过程【译】

Java Code Examples for java.util.Spliterators

打赏
手机扫一扫,支持CHE~