Java集合之Set、HashSet、LinkedHashSet和TreeSet深度解析

目录Set HashSet 1 HashSet是什么2 HashSet的特点3 HashSet如何检查重复4 HashSet常用方法5 HashSet与HashMap的区别HashSet源码1 构造方法2 添加元素3 删除元素4 查找元素5 清空集合/判断是否为空/获取HashSet元素个数6 迭代器LinkedHashSet 1 LinkedHashSet是什么2 LinkedHashSet的特点3 LinkedHashSet支持按元素访问顺序排序吗4 LinkedHashSet常用方法LinkedHashSet源码TreeSet 1 TreeSet是什么2 TreeSet特点3 TreeSet常用方法TreeSet源码Set List是有序集合的根接口， Set是无序集合的根接口，无序也就意味着元素不重复 。

更严格地说，Set集合不包含一对元素e1和e2 ，使得eequals(e2) ，并且最多一个空元素。

使用Set存储的特点与List相反：元素无序、不可重复。

常用的实现方式：HashSet、LinkedHashSet和TreeSet。

具体实现优点缺点HashSet底层数据结构是哈希表，可以存储Null元素，效率高线程不安全，需要重写hashCode()和equals()来保证元素唯一性LinkedHashSet底层数据结构是链表和哈希表(链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性)，效率高线程不安全TreeSet底层数据结构是二叉树，元素唯一且已经排好序需要重写hashCode和equals()来保证元素唯一性当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。

简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值也相等。

LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。

这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

在使用Set存储数据时，为保障元素唯一性，常常要重写hashCode。

重写hashCode方法时，尽量遵循以下原则：相同的对象返回相同的hashCode值不同的对象返回不同的hashCode值，否则，就会增加冲突的概率尽量的让hashCode值散列开（用异或运算可使结果的范围更广）

HashSet HashSet中没有重复元素，底层由HashMap实现，不保证元素的顺序(此处的没有顺序是指：元素插入的顺序与输出的顺序不一致)，HashSet允许使用Null元素，HashSet是非同步的。

LinkedHashSet LinkedHashSet继承自HashSet，其底层是基于LinkedHashMap来实现的，有序，非同步。

LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。

TreeSet TreeSet底层是基于TreeMap实现的，所以元素有序。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。当我们构造TreeSet时，若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。

TreeSet是线程不安全的。

自然排序要求元素必须实现Compareable接口，并重写里面的compareTo()方法，元素通过比较返回的int值来判断排序序列，返回0说明两个对象相同。

比较器排序需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法。

TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0。

在使用Set存储元素时，元素虽然无放入顺序，但Set的底层实现其实是Map，元素在Set中的位置是有该元素的HashCode决定的，所以其位置其实是固定的。

TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。

至于具体使用哪种集合时，参考：

在List和Set两个分支中，ArrayList和HashSet是对应分支中适应性最广的，两者再比较，ArrayList则适用性更广一些。也就是说如果要确定用List，但不确定用哪种List，就可以使用ArrayList；如果确定用Set，但不确定用哪种Set，就可以使用HashSet。如果只知道用集合，就用ArrayList 。

HashSet 1 HashSet是什么

HashSet的继承关系：

public class HashSetextends AbstractSetimplements Set, Cloneable, java.io.Serializable

HashSet是一个无序集合，其底层结构是HashMap，简单来说，HashSet是value是固定值（ Object PRESENT = new Object() ）的HashMap。

2 HashSet的特点HashSet的 底层实现是HashMap （HashSet的值存放于HashMap的key上，HashMap的value是一个统一的值）。

HashSet中的 元素无序且不能重复 （从插入HashSet元素的顺序和遍历HashSet的顺序对比可以看出）。

HashSet是 线程不安全 的。如果要保证线程安全，其中一种方法是将其改造成线程安全的类，示例：Set set = Collections.synchronizedSet(new HashSet(...));HashSet 允许存入null 。

3 HashSet如何检查重复当你把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相同的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用 equals() 方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。

hashCode()与 equals()的相关规定如果两个对象相等，则hashcode一定也是相同的；

两个对象相等，对两个equals方法返回true；

两个对象有相同的hashcode值，它们也不一定是相等的；

如果equals方法被覆盖过，则hashCode方法也必须被覆盖；

hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该 class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

4 HashSet常用方法构造一个新的空HashSet，默认初始容量为16，负载因子为0.75public HashSet()构造一个新的空HashSet，指定初始容量，负载因子为0.75public HashSet(int initialCapacity)构造一个新的空HashSet，指定初始容量和负载因子public HashSet(int initialCapacity, float loadFactor)添加元素public boolean add(E e)清空集合public void clear()如果此集合包含指定的元素，则返回 truepublic boolean contains(Object o)如果此集合不包含任何元素，则返回 truepublic boolean isEmpty()获取此集合中元素的迭代器public Iterator iterator()删除元素public boolean remove(Object o)返回此集合中的元素数public int size()5 HashSet与HashMap的区别HashMap HashSet实现了Map接口实现了Set接口存储键值对仅存储对象调用put()向map中添加元素调用 add()方法向Set中添加元素HashMap使用键（Key）计算Hashcode HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false HashMap相对于HashSet 较快，因为它是使用唯一的键获取对象HashSet较HashMap来说比较慢HashSet源码由于HashSet的底层实现HashMap，所以其方法的实现基本都是对HashMap的操作。

变量：

//HashSet集合中的内容是通过HashMap数据结构来存储的private transient HashMap map;//向HashSet中添加数据，数据在上面的map结构是作为key存在的，而value统一都是//PRESENT，这样做是因为Set只使用到了HashMap的key，所以此处定义一个静态的常//量Object类，来充当HashMap的value private static final Object PRESENT = new Object();1 构造方法HashSet() //直接 new 一个HashMap对象出来，采用无参的 HashMap 构造函数，//HashMap对象具有默认初始容量（16）和加载因子（0.75）

public HashSet() {map = new HashMap<>();}HashSet(int initialCapacity, float loadFactor)//指定初始容量和加载因子，创建HashMap实例public HashSet(int initialCapacity, float loadFactor) {map = new HashMap<>(initialCapacity, loadFactor);}HashSet(int initialCapacity)//指定初始容量，创建HashMap public HashSet(int initialCapacity) {map = new HashMap<>(initialCapacity);}HashSet(int initialCapacity, float loadFactor, boolean dummy)//以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。

HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);}加载因子指的是能存储的元素占总的容量的比例。

在 HashMap 中，能够存储元素的数量就是： 总的容量*加载因子 。

每当向HashSet新增元素时，如果HashMap集合中的元素大于前面公式计算的结果，就必须要进行扩容操作，从时间和空间考虑，加载因子一般都选默认的0.75。

2 添加元素当把对象加入HashSet时，HashSet会先计算对象的 hashcode 值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。

但是如果发现有相同hashcode 值的对象，这时会调用 equals()方法来检查hashcode相等的对象是否真的相同。如果两者相同，则覆盖旧元素。

//将 e 作为 key，PRESENT 作为 value 插入到 map 集合中，如果 e//不存在，则插入成功返回 true;如果存在，则返回false//本质上是调用HashMap的put方法来实现的public boolean add(E e) {return map.put(e, PRESENT)==null;}3 删除元素//删除成功返回 true，删除的元素不存在会返回 false//本质上是调用HashMap的remove方法来实现的public boolean remove(Object o) {return map.remove(o)==PRESENT;}4 查找元素//调用 HashMap 的 containsKey(Object o) 方法，找到了返回 true，找不到返回 false//因为HashSet的本质上是用HashMap来存储元素的，HashSet的值是HashMap中的key，所以//此处调用了HashMap的containsKey方法来判断public boolean contains(Object o) {return map.containsKey(o);}5 清空集合/判断是否为空/获取HashSet元素个数这几个方法都是直接调用其底层实现HashMap的方法的，源码：//清空集合public void clear() {map.clear();}//判断是否为空public boolean isEmpty() {return map.isEmpty();}//获取集合元素个数public int size() {return map.size();}6 迭代器//因为HashSet的本质上是用HashMap来存储元素的，HashSet的值是HashMap中的key，所以//此处调用了HashMap的keySet方法来遍历HashSet中的元素public Iterator iterator() {return map.keySet().iterator();}LinkedHashSet 1 LinkedHashSet是什么LinkedHashSet是有序集合，其继承关系：public class LinkedHashSetextends HashSetimplements Set, Cloneable, java.io.Serializable

LinkedHashSet底层是通过LinkedHashMap来实现的，LinkedHashMap其实也就是value是固定值的LinkedHashMap。

因此LinkedHashSet中的元素顺序是可以保证 的，也就是说遍历序和插入序是一致的。

2 LinkedHashSet的特点底层是用LinkedHashMap来实现的。

线程不安全 。

元素有序，是按照插入的顺序排序的。

最多只能存一个Null。

3 LinkedHashSet支持按元素访问顺序排序吗LinkedHashSet所有的构造方法都是调用HashSet的同一个构造方法： HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);}然后，通过调用LinkedHashMap的构造方法初始化Map： public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;}可以看出：这里把accessOrder写死为false。所以，LinkedHashSet是不支持按访问顺序对元素排序的，只能按插入顺序排序 。

4 LinkedHashSet常用方法1、构造一个具有默认初始容量（16）和负载因子（0.75）的LinkedHashSetpublic LinkedHashSet()2、构造一个具有指定初始容量和默认负载因子（0.75）的LinkedHashSetpublic HashSet(int initialCapacity)

3、构造具有指定的初始容量和负载因子的LinkedHashSet

public HashSet(int initialCapacity, float loadFactor)LinkedHashSet源码LinkedHashSet源码很简单，大都和其父类HashSet相同，此处只介绍其构造方法。

1、LinkedHashSet(int initialCapacity, float loadFactor) public LinkedHashSet(int initialCapacity, float loadFactor) {//调用其父类HashSet的构造器，指定初始容量和增长因子，构造一个LinkedHashMap super(initialCapacity, loadFactor, true);}2、LinkedHashSet(int initialCapacity) public LinkedHashSet(int initialCapacity) {//调用其父类HashSet的构造器，指定初始容量，增长因子为0.75，构造一个LinkedHashMap super(initialCapacity, .75f, true);}3、public LinkedHashSet() public LinkedHashSet() {//调用其父类HashSet的构造器，初始容量为16，增长因子为0.75，构造一个LinkedHashMap super(16, .75f, true);}TreeSet 1 TreeSet是什么TreeSet是一个有序集合，基于TreeMap实现。

TreeSet的继承关系：

public class TreeSet extends AbstractSetimplements NavigableSet, Cloneable, java.io.Serializable2 TreeSet特点TreeSet支持元素的自然排序和按照在创建时指定的Comparator比较器进行排序。

TreeSet()是使用二叉树的原理对新 add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。

TreeSet中要存储自定义类的对象时， 自己定义的类必须实现 Comparable 接口，并且覆写相应的 compareTo()函数，才可以正常使用。

当自定义对象之间进行比较时，如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。

TreeSet的基本操作（add、remove 和 contains）的时间复杂度是log(n) 。

TreeSet是非线程安全的。

TreeSet的迭代器是fail-fast策略的。

TreeSet中元素不允许为Null，不允许重复值。

3 TreeSet常用方法构造方法//创建一个空的 TreeSet，使用自然排序public TreeSet()//指定比较器，如果比较器是 null 将使用自然排序public TreeSet(Comparator comparator)添加元素//添加一个元素public boolean add(E e)//添加集合中的元素public boolean addAll(Collection c)删除元素 public boolean remove(Object o)查找元素 public boolean contains(Object o)获取TreeSet元素个数/判断TreeSet是否为空/清空TreeSet//获取TreeSet元素个数public int size()//判断TreeSet是否为空public boolean isEmpty()//清空TreeSet public void clear()返回此TreeSet中存在的最大元素/最小元素//返回此TreeSet中存在的最大元素public E last() {return m.lastKey();}//返回此TreeSet中存在的最小元素public E first() {return m.firstKey();} 返回此集合中小于某个元素的最大的元素 public E lower(E e)返回此集合中大于某个元素的最小的元素 public E higher(E e)floor/ceiling//返回在这个集合中小于或者等于给定元素的最大元素public E floor(E e)//返回在这个集合中大于或者等于给定元素的最小元素public E ceiling(E e)检索和删除最小（第一个）元素 public E pollFirst()检索和删除最大（最后）元素 public E pollLast()TreeSet源码//存储数据的底层数据结构private transient NavigableMap m;//由于 TreeSet 只需要使用 Key 进行存储，因此 Value 存储的是一个虚拟值private static final Object PRESENT = new Object();

1、构造方法

//使用 TreeMap 创建一个空的 TreeSet，使用自然排序，//添加的元素需要实现 Comparable 接口，即是可比较的public TreeSet() {this(new TreeMap());}//指定比较器，如果比较器是 null 将使用自然排序public TreeSet(Comparator comparator) {this(new TreeMap<>(comparator));}//构建一个treeSet，包含参数c中的元素，排序是基于元素的自然顺序public TreeSet(Collection c) {this();addAll(c);}

2、添加元素

调用TreeMap中的put()方法进行添加元素。

public boolean add(E e) {return m.put(e, PRESENT)==null;}将集合C中的所有元素添加到TreeSet中。

public boolean addAll(Collection c) {// Use linear-time version if applicable if (m.size()==0 && c.size() > 0 &&c instanceof SortedSet &&m instanceof TreeMap) {SortedSet set = (SortedSet) c;TreeMap map = (TreeMap) m;Comparator cc = set.comparator();Comparator mc = map.comparator();if (cc==mc || (cc != null && cc.equals(mc))) {map.addAllForTreeSet(set, PRESENT);return true;}}return super.addAll(c);}

3、删除元素

调用TreeMap中的remove()方法来删除TreeSet中的元素，若set中存在要删除的元素，删除，返回true，不存在，返回false。

内部调用navigableMap的remove方法，因为treeMap是其实现类，所以实际执行的时候，调用的是treeMap的remove方法。

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

4、查找元素

若set中存在该元素，返回true，不存在，返回false。

public boolean contains(Object o) {return m.containsKey(o);}5、获取TreeSet元素个数/判断TreeSet是否为空/清空TreeSet//获取TreeSet元素个数public int size() {return m.size();}//判断TreeSet是否为空public boolean isEmpty() {return m.isEmpty();}//清空TreeSet public void clear() {m.clear();}

6、返回此TreeSet中存在的最大元素/最小元素

//返回此TreeSet中存在的最大元素public E last() {return m.lastKey();}//返回此TreeSet中存在的最小元素public E first() {return m.firstKey();}

7、返回此集合中小于某个元素的最大的元素

返回此集合中最大的元素，该元素严格小于给定的元素。如果此TreeSet集合中不存在这样的元素，则此方法返回Null。

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

8、返回此集合中大于某个元素的最小的元素

从集合中返回指定元素中最接近的最大元素，如果没有，则返回Null。

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

9、floor/ceiling

floor(E e)方法返回在这个集合中小于或者等于给定元素的最大元素，如果不存在这样的元素，返回null。

ceiling(E e)方法返回在这个集合中大于或者等于给定元素的最小元素，如果不存在这样的元素，返回null。

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

10、检索和删除最小（第一个）元素

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

11、检索和删除最大（最后）元素

public E pollLast() {Map.Entry e = m.pollLastEntry();return (e == null) ? null : e.getKey();}到此这篇关于Java集合之Set、HashSet、LinkedHashSet和TreeSet深度解析的文章就介绍到这了,更多相关Java的set集合内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！

您可能感兴趣的文章:java集合中HashSet LinkedHashSet TreeSet三者异同面试精讲Java中HashSet、LinkedHashSet和TreeSet区别详解Java中的LinkedHashSet和TreeSet解读Java LinkedHashSet集合的底层原理和TreeSet集合