Java集合框架详解(四) HashSet

相关文章

HashSet

今天继续对集合框架源码的学习 JDK1.8 今天学习HashSet

HashSet 顾名思义,就是以散列表的形式存储数据的集合,集合中不允许相同的元素。HashSet底层是由HashMap实现的,所以在学习HashSet之前最好先学习HashMap。最后HashSet也不是线程安全的。下面看看类定义。

类定义

1
2
3
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable

这个在前面几节的分析中已经比较熟悉了,继承了AbstractSet,实现了Set接口,Cloneable接口,以及Serializable可序列化。

成员变量

1
2
3
4
5
static final long serialVersionUID = -5024744406713321676L; //序列化ID

private transient HashMap<E,Object> map; //底层使用HashMap来存储数据

private static final Object PRESENT = new Object();//新建一个object类作为底层HashMap的value

构造方法

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
public HashSet() {
map = new HashMap<>();//构造一个空的HashMap
}

public HashSet(Collection<? extends E> c) {
//构造一个c集合中所有元素的HashSet
//HashMap加载因子为0.75
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
//创建指定初始容量以及加载因子的底层HashMap
map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
//创建指定初始容量以及加载因子为0.75的HashMap
map = new HashMap<>(initialCapacity);
}


HashSet(int initialCapacity, float loadFactor, boolean dummy) {
//以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合
//此方法不是public,只对同一个包有效果
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

HashSet常用方法

add(E e)

1
2
3
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

add的代码是将元素添加到底层的HashMap中,value和前面说的一样使用的PRESENT,到这个地方,可以理解HashSet中元素的互异性的原因了,HashSet的元素是以Key的形式存在底层的HashMap中的,而HashMap中的Key是不允许有相同出现的,故HashSet中的元素也是不允许相同的。而return map.put(e, PRESENT)==null也很好理解,通过上一节对HashMap的put的学习,当put一个键值对时,如果Key存在,则替换原来的value,并且返回oldvalue,如果不存在,则创建新的entry,返回null值.

remove(Object o)

1
2
3
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}

这里则直接使用了HashMap的remove方法,如果删除成功(有该元素)则返回value值(实际就是PRESENT),否则返回null。关于HashMap的方法可看上节学习。

contains(Object o)

1
2
3
4
5
6
7
public boolean contains(Object o) {
return map.containsKey(o);
}

public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}

contains方法返回该元素是否在集合中,依然使用的是HashMap的containsKey方法,返回是否存在该Key的entry

isEmpty()

1
2
3
4
5
6
7
public boolean isEmpty() {
return map.isEmpty();
}

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

这个方法非常简单,判断的是HashMap的size是否为0

size()

1
2
3
public int size() {
return map.size();
}

返回的是底层HashMap的size

Iterator()

1
2
3
public Iterator<E> iterator() {  
return map.keySet().iterator();
}

Iterator方法返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。返回的是map中Key组成的集合keySet的迭代器。

clone()

1
2
3
4
5
6
7
8
9
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(e);
}
}

返回此HashSet实例的浅表副本

关于浅表副本

意思是方法中newSet只复制了当前HashSet的值,并没有复制其引用,换言之,当克隆下来的newSet中元素发生改变时,对原来的HashSet不会造成影响。

HashSet总结

  • HashSet本身方法并不难,但是因为底层使用的是HashMap来实现,HashSet的大多数方法调用的都是HashMap的方法,所以,在学习HashSet方法之前,需要学习HashMap,而HashMap的方法并不简单;
  • 正是因为底层是HashMap,HashSet的元素都是存在HashMap的entry的Key中,这也实现了HashSet中元素不允许相同;
  • 无序性,因为底层的HashMap是无序的,自然HashSet是无序的;
  • HashSet不是线程安全的。