Java HashSet工作原理及实现

May 7th, 2017

Table of Contents

HashSet

HashSet是基于HashMap来实现的，操作很简单，更像是对HashMap做了一次“封装”，而且只使用了HashMap的key来实现各种特性

private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

map是整个HashSet的核心，而PRESENT则是用来造一个假的value来用的。

基本操作

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
public boolean contains(Object o) {
    return map.containsKey(o);
}
public int size() {
    return map.size();
}

LinkedHashSet

LinkedHashSet是基于HashMap和双向链表的实现，其实现基本和LinkedHashMap一样。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

TreeSet

TreeSet是基于TreeMap实现的，也非常简单，同样的只是用key及其操作，然后把value置为dummy的object。

ShengYg

Step after step the ladder is ascended.

Tags • set