image frame

无论走到哪里,
都应该记住,
过去都是假的,
回忆是一条没有尽头的路。
一切以往的春天都不复存在,
就连那最坚韧而又狂乱的爱情,
归根结底也不过是转瞬即逝的现实,
唯有孤独永恒。

——加西亚·马尔克斯

HashSet 源码

问题

  1. HashSet 底层数据结构是什么?
  2. HashSet 是有序的吗?
  3. HashSet 是否允许 null 元素?

概括

HashSet 是 Set 的一种实现方式,基于 HashMap 来确保元素不重复。

继承结构

HashSet 继承结构

  • 实现 Set 接口,有 Set 所有特性

源码实现

属性

View Code
1
2
3
4
private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
  • HashSet 的底层是基于 HashMap 实现;
  • PRESENT 伪值,以便与后备映射中的对象相关联;

构造方法

View Code
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
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
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
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}

/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* 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
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}

/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* the specified initial capacity and default load factor (0.75).
*
* @param initialCapacity the initial capacity of the hash table
* @throws IllegalArgumentException if the initial capacity is less
* than zero
*/
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}

/**
* 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);
}
  • 初始化过程,实际上是初始化 HashMap 参数;
  • 最后一个构造方法是 LinkedHashSet 专属的方法;

操作方法

add(E e)

View Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element <tt>e</tt> to this set if
* this set contains no element <tt>e2</tt> such that
* <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
* unchanged and returns <tt>false</tt>.
*
* @param e element to be added to this set
* @return <tt>true</tt> if this set did not already contain the specified
* element
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
  • 增加元素,实际上是把元素作为 key 保存到 HashMap 中,而对应的 Value 是一个空对象数组;

remove(Object o)

View Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* Removes the specified element from this set if it is present.
* More formally, removes an element <tt>e</tt> such that
* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
* if this set contains such an element. Returns <tt>true</tt> if
* this set contained the element (or equivalently, if this set
* changed as a result of the call). (This set will not contain the
* element once the call returns.)
*
* @param o object to be removed from this set, if present
* @return <tt>true</tt> if the set contained the specified element
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
  • 删除元素的同时,对 value 做了一次判断;

contains(Object o)

View Code
1
2
3
4
5
6
7
8
9
10
11
12
/**
* Returns <tt>true</tt> if this set contains the specified element.
* More formally, returns <tt>true</tt> if and only if this set
* contains an element <tt>e</tt> such that
* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
*
* @param o element whose presence in this set is to be tested
* @return <tt>true</tt> if this set contains the specified element
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
  • 判断集合是否包含某一元素,直接调用 HashMap.containsKey(o) 方法;

iterator()

View Code
1
2
3
4
5
6
7
8
9
10
/**
* Returns an iterator over the elements in this set. The elements
* are returned in no particular order.
*
* @return an Iterator over the elements in this set
* @see ConcurrentModificationException
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
  • 遍历元素也是直接调用 HashMap 方法;

总结

  • HashSet 内部使用 HashMap 的 key 存储元素,以此来保证元素不重复;
  • HashSet 是无序的,因为 HashMap 的 key 是无序的;
  • HashSet 中允许有一个 null 元素,因为 HashMap 允许 key 为 null;
  • HashSet 是非线程安全的;
  • HashSet 是没有 get() 方法的;
  • © 2015-2020 Andrew
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信