【面试官】你说说对HashSet的理解？

• 面试官：你说说对HashSet的理解？
• 面试官：LinkedHashSet呢？
• 面试官：TreeSet和它们比有什么特性？
• 面试官：那TreeSet要怎么定制排序？

大家好，我是南哥。

一个Java学习与进阶的领路人，相信对你通关面试进入心心念念的公司有所帮助。

文章目录

1. Set集合
   1. HashSet
   2. LinkedHashSet
   3. TreeSet
   4. TreeSet自定义排序

1. Set集合

1.1 HashSet

面试官：你说说对HashSet的理解？

Set集合区别于其他三大集合的重要特性就是元素具有唯一性，南友们记不住这个特性的话，有个易记的方法。Set集合为什么要叫Set呢？因为Set集合的命名取自于我们小学数学里的集合论（Set Theory），数学集合一个很重要的概念就是每个元素的值都互不相同。

Set集合常见的有实例有：HashSet、LinkedHashSet、TreeSet，南哥先缕一缕HashSet。

// HashSet类源码
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {...}

HashSet底层实现其实是基于HashMap，HashMap的特点就是Key具有唯一性，这一点被HashSet利用了起来，每一个HashMap的Key对应的就是HashSet的元素值。来看看官方源码的解释。

此类实现Set接口，由哈希表（实际上是HashMap实例）支持。它不保证集合的迭代顺序；特别是，它不保证顺序随时间保持不变。此类允许null元素。

我们创建一个HashSet对象，实际上底层创建了一个HashMap对象。

    // HashSet构造方法源码
    public HashSet() {
        map = new HashMap<>();
    }

HashSet一共提供了以下常用方法，不得不说HahSet在业务开发中还是用的没那么多的，南哥在框架源码上看HashSet用的就比较多，比如由Java语言实现的zookeeper框架源码。

（1）添加元素

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

我们看上面add方法的源码，是不是调用了HashMap的put方法呢？而put方法添加的Key是HashSet的值，Val则是一个空的Object对象。PRESENT是这么定义的。

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

（2）判断元素是否存在

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

HashSet的contains方法同样是调用HashMap判断Key是否存在的方法：containsKey。

（3）移除元素

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

1.2 LinkedHashSet

面试官：LinkedHashSet呢？

接着轮到LinkedHashSet，同为Set集合之一，它和上文的HashSet有什么区别？南哥卖个关子。

源码对LinkedHashSet的解释。

Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).

源码的大概意思就是：Set接口的哈希表和链表实现，具有可预测的迭代顺序。此实现与HashSet的不同之处在于，它维护一个贯穿其所有条目的双向链表。此链表定义迭代顺序，即**元素插入集合的顺序 (**插入顺序)。

底层数据结构是一条双向链表，每个元素通过指针进行相连，也就有了按插入顺序排序的功能。

知道了LinkedHashSet的特性，看看他的构造方法。

    /**
     * 构造一个新的、空的链接哈希集，具有默认初始容量（16）和负载因子（0.75）。
     */
    public LinkedHashSet() {
        super(16, .75f, true);
    }

这个方法向上调用了底层C语言源码实现的LinedHashMap