Java集合详解7一文搞清楚HashSetTreeSet与LinkedHashSet的异同

《Java 集合详解系列》是我在完成夯实 Java 基础篇的系列博客后准备开始写的新系列。

这些文章将整理到我在 GitHub 上的《Java 面试指南》仓库，更多精彩内容请到我的仓库里查看

https://github.com/h2pl/Java-…

喜欢的话麻烦点下 Star、fork 哈

文章首发于我的个人博客：

www.how2playlife.com

今天我们来探索一下 HashSet，TreeSet 与 LinkedHashSet 的基本原理与源码实现，由于这三个 set 都是基于之前文章的三个 map 进行实现的，所以推荐大家先看一下前面有关 map 的文章，结合使用味道更佳。

本文参考
http://cmsblogs.com/?p=599

HashSet

定义

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

HashSet 继承 AbstractSet 类，实现 Set、Cloneable、Serializable 接口。其中 AbstractSet 提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。
==Set 接口是一种不包括重复元素的 Collection，它维持它自己的内部排序，所以随机访问没有任何意义。==

本文基于 1.8jdk 进行源码分析。

基本属性

基于 HashMap 实现，底层使用 HashMap 保存所有元素

private transient HashMap<E,Object> map;

// 定义一个 Object 对象作为 HashMap 的 value
private static final Object PRESENT = new Object();

构造函数

/**
     * 默认构造函数
     * 初始化一个空的 HashMap，并使用默认初始容量为 16 和加载因子 0.75。*/
    public HashSet() {map = new HashMap<>();
    }

    /**
     * 构造一个包含指定 collection 中的元素的新 set。*/
    public HashSet(Collection<? extends E> c) {map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    /**
     * 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和指定的加载因子
     */
    public HashSet(int initialCapacity, float loadFactor) {map = new HashMap<>(initialCapacity, loadFactor);
    }

    /**
     * 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。*/
    public HashSet(int initialCapacity) {map = new HashMap<>(initialCapacity);
    }

    /**
     * 在 API 中我没有看到这个构造函数，今天看源码才发现（原来访问权限为包权限，不对外公开的）* 以指定的 initialCapacity 和 loadFactor 构造一个新的空链接哈希集合。* dummy 为标识 该构造函数主要作用是对 LinkedHashSet 起到一个支持作用
     */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
 从构造函数中可以看出 HashSet 所有的构造都是构造出一个新的 HashMap，其中最后一个构造函数，为包访问权限是不对外公开，仅仅只在使用 LinkedHashSet 时才会发生作用。

方法

既然 HashSet 是基于 HashMap，那么对于 HashSet 而言，其方法的实现过程是非常简单的。

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

iterator()方法返回对此 set 中元素进行迭代的迭代器。返回元素的顺序并不是特定的。

底层调用 HashMap 的 keySet 返回所有的 key，这点反应了 HashSet 中的所有元素都是保存在 HashMap 的 key 中，value 则是使用的 PRESENT 对象，该对象为 static final。

public int size() {return map.size();
    }
   size()返回此 set 中的元素的数量（set 的容量）。底层调用 HashMap 的 size 方法，返回 HashMap 容器的大小。

public boolean isEmpty() {return map.isEmpty();
    }
    isEmpty()，判断 HashSet()集合是否为空，为空返回 true，否则返回 false。public boolean contains(Object o) {return map.containsKey(o);
}

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

// 最终调用该方法进行节点查找
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 先检查桶的头结点是否存在
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
            // 不是头结点，则遍历链表，如果是树节点则使用树节点的方法遍历，直到找到，或者为 null
        if ((e = first.next) != null) {if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

contains()，判断某个元素是否存在于 HashSet()中，存在返回 true，否则返回 false。更加确切的讲应该是要满足这种关系才能返回 true：(o==null ? e==null : o.equals(e))。底层调用 containsKey 判断 HashMap 的 key 值是否为空。

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

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

map 的 put 方法：final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 确认初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        
    // 如果桶为空，直接插入新元素，也就是 entry
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果冲突，分为三种情况
        //key 相等时让旧 entry 等于新 entry 即可
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 红黑树情况
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 如果 key 不相等，则连成链表
            for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

这里注意一点，hashset 只是不允许重复的元素加入，而不是不允许元素连成链表，因为只要 key 的 equals 方法判断为 true 时它们是相等的，此时会发生 value 的替换，因为所有 entry 的 value 一样，所以和没有插入时一样的。

而当两个 hashcode 相同但 key 不相等的 entry 插入时，仍然会连成一个链表，长度超过 8 时依然会和 hashmap 一样扩展成红黑树，看完源码之后笔者才明白自己之前理解错了。所以看源码还是蛮有好处的。hashset 基本上就是使用 hashmap 的方法再次实现了一遍而已，只不过 value 全都是同一个 object，让你以为相同元素没有插入，事实上只是 value 替换成和原来相同的值而已。

当 add 方法发生冲突时，如果 key 相同，则替换 value，如果 key 不同，则连成链表。

add()如果此 set 中尚未包含指定元素，则添加指定元素。如果此 Set 没有包含满足(e==null ? e2==null : e.equals(e2)) 的 e2 时，则将 e2 添加到 Set 中，否则不添加且返回 false。

由于底层使用 HashMap 的 put 方法将 key = e，value=PRESENT 构建成 key-value 键值对，当此 e 存在于 HashMap 的 key 中，则 value 将会覆盖原有 value，但是 key 保持不变，所以如果将一个已经存在的 e 元素添加中 HashSet 中，新添加的元素是不会保存到 HashMap 中，所以这就满足了 HashSet 中元素不会重复的特性。

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

remove 如果指定元素存在于此 set 中，则将其移除。底层使用 HashMap 的 remove 方法删除指定的 Entry。

public void clear() {map.clear();
}

clear 从此 set 中移除所有元素。底层调用 HashMap 的 clear 方法清除所有的 Entry。

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();
        }
    }

clone 返回此 HashSet 实例的浅表副本：并没有复制这些元素本身。

后记：

由于 HashSet 底层使用了 HashMap 实现，使其的实现过程变得非常简单，如果你对 HashMap 比较了解，那么 HashSet 简直是小菜一碟。有两个方法对 HashMap 和 HashSet 而言是非常重要的，下篇将详细讲解 hashcode 和 equals。

TreeSet

与 HashSet 是基于 HashMap 实现一样，TreeSet 同样是基于 TreeMap 实现的。在《Java 提高篇（二七）—–TreeMap》中 LZ 详细讲解了 TreeMap 实现机制，如果客官详情看了这篇博文或者多 TreeMap 有比较详细的了解，那么 TreeSet 的实现对您是喝口水那么简单。

TreeSet 定义

我们知道 TreeMap 是一个有序的二叉树，那么同理 TreeSet 同样也是一个有序的，它的作用是提供有序的 Set 集合。通过源码我们知道 TreeSet 基础 AbstractSet，实现 NavigableSet、Cloneable、Serializable 接口。

其中 AbstractSet 提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。

NavigableSet 是扩展的 SortedSet，具有了为给定搜索目标报告最接近匹配项的导航方法，这就意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。Cloneable 支持克隆，Serializable 支持序列化。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

同时在 TreeSet 中定义了如下几个变量。

private transient NavigableMap<E,Object> m;
    
//PRESENT 会被当做 Map 的 value 与 key 构建成键值对
 private static final Object PRESENT = new Object();

其构造方法：

// 默认构造方法，根据其元素的自然顺序进行排序

public TreeSet() {this(new TreeMap<E,Object>());
}

// 构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的自然顺序进行排序。public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));
}

// 构造一个新的空 TreeSet，它根据指定比较器进行排序。public TreeSet(Collection<? extends E> c) {this();
    addAll(c);
}

// 构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。public TreeSet(SortedSet<E> s) {this(s.comparator());
    addAll(s);
}

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

TreeSet 主要方法

1、add：将指定的元素添加到此 set（如果该元素尚未存在于 set 中）。

public boolean add(E e) {return m.put(e, PRESENT)==null;
    }
 
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
    // 空树时，判断节点是否为空
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    // 非空树，根据传入比较器进行节点的插入位置查找
    if (cpr != null) {
        do {
            parent = t;
            // 节点比根节点小，则找左子树，否则找右子树
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
                // 如果 key 的比较返回值相等，直接更新值（一般 compareto 相等时 equals 方法也相等）else
                return t.setValue(value);
        } while (t != null);
    }
    else {
    // 如果没有传入比较器，则按照自然排序
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 查找的节点为空，直接插入，默认为红节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
        // 插入后进行红黑树调整
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}    

2、get：获取元素

public V get(Object key) {Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

该方法与 put 的流程类似，只不过是把插入换成了查找

3、ceiling：返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。

public E ceiling(E e) {return m.ceilingKey(e);
    }

4、clear：移除此 set 中的所有元素。

public void clear() {m.clear();
    }

5、clone：返回 TreeSet 实例的浅表副本。属于浅拷贝。

public Object clone() {
        TreeSet<E> clone = null;
        try {clone = (TreeSet<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError();
        }

        clone.m = new TreeMap<>(m);
        return clone;
    }

6、comparator：返回对此 set 中的元素进行排序的比较器；如果此 set 使用其元素的自然顺序，则返回 null。

public Comparator<? super E> comparator() {return m.comparator();
    }

7、contains：如果此 set 包含指定的元素，则返回 true。

public boolean contains(Object o) {return m.containsKey(o);
    }

8、descendingIterator：返回在此 set 元素上按降序进行迭代的迭代器。

public Iterator<E> descendingIterator() {return m.descendingKeySet().iterator();}

9、descendingSet：返回此 set 中所包含元素的逆序视图。

public NavigableSet<E> descendingSet() {return new TreeSet<>(m.descendingMap());
    }

10、first：返回此 set 中当前第一个（最低）元素。

public E first() {return m.firstKey();
    }

11、floor：返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。

public E floor(E e) {return m.floorKey(e);
    }

12、headSet：返回此 set 的部分视图，其元素严格小于 toElement。

public SortedSet<E> headSet(E toElement) {return headSet(toElement, false);
    }

13、higher：返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。

public E higher(E e) {return m.higherKey(e);
    }

14、isEmpty：如果此 set 不包含任何元素，则返回 true。

public boolean isEmpty() {return m.isEmpty();
    }

15、iterator：返回在此 set 中的元素上按升序进行迭代的迭代器。

public Iterator<E> iterator() {return m.navigableKeySet().iterator();}

16、last：返回此 set 中当前最后一个（最高）元素。

public E last() {return m.lastKey();
    }

17、lower：返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。

public E lower(E e) {return m.lowerKey(e);
    }

18、pollFirst：获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。

public E pollFirst() {Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();}

19、pollLast：获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。

public E pollLast() {Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null) ? null : e.getKey();}

20、remove：将指定的元素从 set 中移除（如果该元素存在于此 set 中）。

public boolean remove(Object o) {return m.remove(o)==PRESENT;
    }

该方法与 put 类似，只不过把插入换成了删除，并且要进行删除后调整

21、size：返回 set 中的元素数（set 的容量）。

public int size() {return m.size();
    }

22、subSet：返回此 set 的部分视图

/**
     * 返回此 set 的部分视图，其元素范围从 fromElement 到 toElement。*/
     public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
             E toElement,   boolean toInclusive) {
             return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                  toElement,   toInclusive));
     }
     
     /**
      * 返回此 set 的部分视图，其元素从 fromElement（包括）到 toElement（不包括）。*/
     public SortedSet<E> subSet(E fromElement, E toElement) {return subSet(fromElement, true, toElement, false);
     }

23、tailSet：返回此 set 的部分视图

/**
     * 返回此 set 的部分视图，其元素大于（或等于，如果 inclusive 为 true）fromElement。*/
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {return new TreeSet<>(m.tailMap(fromElement, inclusive));
    }
    
    /**
     * 返回此 set 的部分视图，其元素大于等于 fromElement。*/
    public SortedSet<E> tailSet(E fromElement) {return tailSet(fromElement, true);
    }

最后

由于 TreeSet 是基于 TreeMap 实现的，所以如果我们对 treeMap 有了一定的了解，对 TreeSet 那是小菜一碟，我们从 TreeSet 中的源码可以看出，其实现过程非常简单，几乎所有的方法实现全部都是基于 TreeMap 的。

LinkedHashSet

LinkedHashSet 内部是如何工作的

LinkedHashSet 是 HashSet 的一个“扩展版本”，HashSet 并不管什么顺序，不同的是 LinkedHashSet 会维护“插入顺序”。HashSet 内部使用 HashMap 对象来存储它的元素，而 LinkedHashSet 内部使用 LinkedHashMap 对象来存储和处理它的元素。这篇文章，我们将会看到 LinkedHashSet 内部是如何运作的及如何维护插入顺序的。

我们首先着眼 LinkedHashSet 的构造函数。在 LinkedHashSet 类中一共有 4 个构造函数。这些构造函数都只是简单地调用父类构造函数（如 HashSet 类的构造函数）。
下面看看 LinkedHashSet 的构造函数是如何定义的。

//Constructor - 1
 
public LinkedHashSet(int initialCapacity, float loadFactor)
{super(initialCapacity, loadFactor, true);              //Calling super class constructor
}
 
//Constructor - 2
 
public LinkedHashSet(int initialCapacity)
{super(initialCapacity, .75f, true);             //Calling super class constructor
}
 
//Constructor - 3
 
public LinkedHashSet()
{super(16, .75f, true);                //Calling super class constructor
}
 
//Constructor - 4
 
public LinkedHashSet(Collection<? extends E> c)
{super(Math.max(2*c.size(), 11), .75f, true);          //Calling super class constructor
        addAll(c);
}

在上面的代码片段中，你可能注意到 4 个构造函数调用的是同一个父类的构造函数。这个构造函数（父类的，译者注）是一个包内私有构造函数（见下面的代码，HashSet 的构造函数没有使用 public 公开，译者注），它只能被 LinkedHashSet 使用。

这个构造函数需要初始容量，负载因子和一个 boolean 类型的哑值（没有什么用处的参数，作为标记，译者注）等参数。这个哑参数只是用来区别这个构造函数与 HashSet 的其他拥有初始容量和负载因子参数的构造函数，下面是这个构造函数的定义，

HashSet(int initialCapacity, float loadFactor, boolean dummy)
{map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

显然，这个构造函数内部初始化了一个 LinkedHashMap 对象，这个对象恰好被 LinkedHashSet 用来存储它的元素。

LinkedHashSet 并没有自己的方法，所有的方法都继承自它的父类 HashSet，因此，对 LinkedHashSet 的所有操作方式就好像对 HashSet 操作一样。

唯一的不同是内部使用不同的对象去存储元素。在 HashSet 中，插入的元素是被当做 HashMap 的键来保存的，而在 LinkedHashSet 中被看作是 LinkedHashMap 的键。

这些键对应的值都是常量 PRESENT（PRESENT 是 HashSet 的静态成员变量，译者注）。

LinkedHashSet 是如何维护插入顺序的

LinkedHashSet 使用 LinkedHashMap 对象来存储它的元素，插入到 LinkedHashSet 中的元素实际上是被当作 LinkedHashMap 的键保存起来的。

LinkedHashMap 的每一个键值对都是通过内部的静态类 Entry<K, V> 实例化的。这个 Entry<K, V> 类继承了 HashMap.Entry 类。

这个静态类增加了两个成员变量，before 和 after 来维护 LinkedHasMap 元素的插入顺序。这两个成员变量分别指向前一个和后一个元素，这让 LinkedHashMap 也有类似双向链表的表现。

private static class Entry<K,V> extends HashMap.Entry<K,V>
{
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;
 
        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {super(hash, key, value, next);
        }
}

从上面代码看到的 LinkedHashMap 内部类的前面两个成员变量——before 和 after 负责维护 LinkedHashSet 的插入顺序。LinkedHashMap 定义的成员变量 header 保存的是
这个双向链表的头节点。header 的定义就像下面这样，

接下来看一个例子就知道 LinkedHashSet 内部是如何工作的了。

public class LinkedHashSetExample
{public static void main(String[] args)
    {
        //Creating LinkedHashSet
 
        LinkedHashSet<String> set = new LinkedHashSet<String>();
 
        //Adding elements to LinkedHashSet
 
        set.add("BLUE");
 
        set.add("RED");
 
        set.add("GREEN");    
 
        set.add("BLACK");
    }
}

如果你知道 LinkedHashMap 内部是如何工作的，就非常容易明白 LinkedHashSet 内部是如何工作的。看一遍 LinkedHashSet 和 LinkedHashMap 的源码，
你就能够准确地理解在 Java 中 LinkedHashSet 内部是如何工作的。

参考文章

http://cmsblogs.com/?p=599

https://www.cnblogs.com/one-a…

https://blog.csdn.net/learnin…

微信公众号

Java 技术江湖

如果大家想要实时关注我更新的文章以及分享的干货的话，可以关注我的公众号【Java 技术江湖】一位阿里 Java 工程师的技术小站，作者黄小斜，专注 Java 相关技术：SSM、SpringBoot、MySQL、分布式、中间件、集群、Linux、网络、多线程，偶尔讲点 Docker、ELK，同时也分享技术干货和学习经验，致力于 Java 全栈开发！

Java 工程师必备学习资源: 一些 Java 工程师常用学习资源，关注公众号后，后台回复关键字 “Java” 即可免费无套路获取。

个人公众号：黄小斜

黄小斜是跨考软件工程的 985 硕士，自学 Java 两年，拿到了 BAT 等近十家大厂 offer，从技术小白成长为阿里工程师。

作者专注于 JAVA 后端技术栈，热衷于分享程序员干货、学习经验、求职心得和程序人生，目前黄小斜的 CSDN 博客有百万 + 访问量，知乎粉丝 2W+，全网已有 10W+ 读者。

黄小斜是一个斜杠青年，坚持学习和写作，相信终身学习的力量，希望和更多的程序员交朋友，一起进步和成长！关注公众号【黄小斜】后回复【原创电子书】即可领取我原创的电子书《菜鸟程序员修炼手册：从技术小白到阿里巴巴 Java 工程师》

程序员 3T 技术学习资源： 一些程序员学习技术的资源大礼包，关注公众号后，后台回复关键字 “资料” 即可免费无套路获取。

​

本文由博客一文多发平台 OpenWrite 发布！