Set接口及其实现类HashSetTreeSet的底层结构与区别 _TreeSet

青春须早为，岂能长少年。这篇文章主要讲述Set接口及其实现类HashSetTreeSet的底层结构与区别相关的知识，希望能为你提供帮助。
Set接口是Collection的子接口，通过上面这段官方文档对Set的介绍可以看出Set的两个特点：
1.无序（插入和取出的顺序不一致）
2.不可重复（所有元素只能出现一次，因此null也只能有一个）
Set的所有方法均来自Collection，没有自己的特有方法。HashSet和TreeSet是Set接口最常用的实现类
（二）HashSet的底层结构首先还是先来看看官方文档对HashSet的介绍：
总结一下：HashSet继承Set接口，底层是一个哈希表，但是实际上是HashMap（这点可以从源码中看出来）。它是无序的（插入和取出的顺序不一致），它允许空节点。
我们先看一下源码：

文章图片

HashSet在构造方法中构造了一个HashMap，因此对源码的解读会放到HashMap中，现在主要说一下HashSet的底层实现结构。
2.1 HashSet为什么是不重复和无序的这个问题其实知道Hash表如何构造就很容易理解。
1.当有一个元素要进入hash表时，先获取该元素的哈希值，再通过一系列运算得到一个索引。（每个元素都能计算出一个索引值，但索引值并非是有序的，因此最终得到一个无序的哈希表。）
2.当该索引处没有元素，则直接插入
3.若该索引处有元素，则需要逐个通过equals判断，如果依旧不相等，则将元素以链表的形式添加在该索引的后面。如果相等，则覆盖原来的元素，实现不重复。
哈希表的链地址法如图所示：

文章图片

（三）HashSet的底层实现为了更加清除的了解HashSet底层实现，我们通过代码来演示一下，按照以往的思路，我们先创建一个简单的类：

public class Book { private String name; private float price; public Book(String name, float price){ this.name=name; this.price=price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public float getPrice() { return price; } public void setPrice(float price) { this.price = price; } @Override public String toString() { return "Book{" + "name=\'" + name + \'\\\'\' + ", price=" + price + \'}\'; } }

然后再实现HashSet,在这里我故意让两个元素重复

public class HashSettest1 { public static void main(String[] args) { HashSet hashSet=new HashSet(); hashSet.add(new Book("aa",20)); hashSet.add(new Book("bb",10)); hashSet.add(new Book("bb",10)); System.out.println(hashSet); } }

但是结果却并没有把我们认为的重复元素（名称和价格相等就算重复）给去重

文章图片

我们前面讲过，HashSet会先计算一个元素的哈希值，然后通过得到的索引用equals和已存在元素进行比较。但是在Book类中没有重写hashcode和equals方法，相当于它并不是按照我们的想法（名称和价格相等就算重复）去判断是否重复，而是根据这个对象计算了一个哈希值。
因此在Book中重写一个HashCode方法和equals方法，这两个方法编译器可以直接生成，为了让大家能理解我自己手写一个简单的HashCode方法和equals方法

@Override public int hashCode() { return name.hashCode()+(int)price; } @Override public boolean equals(Object o) { if (this == o) return true; if (getClass() != o.getClass()) return false; Book book = (Book) o; return price==book.price & & name.equals(book.name); }

我通过名称和价格生成一个hashcode去生成哈希值，equals只有当名称和价格都相等时才算相等。
但是我现在手写的这个hashcode方式存在一个问题，即使name的hash值和price不同，但是加起来是有可能相同的，虽然后续还有equals方法可以防止hashcode的误差，但是增加了计算负担。
idea自动生成的两个方法如下：

@Override public int hashCode() { return Objects.hash(name, price); } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Book book = (Book) o; return Float.compare(book.price, price) == 0 & & Objects.equals(name, book.name); }

进入hashcode源码后可以看到，对于计算出的值它又乘了一个31，避免哈希值一致但是实际不一致的情况

public static int hashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) result = 31 * result + (element == null ? 0 : element.hashCode()); return result; }

为什么选择31作为这个因子，《Effective java》作了这样的解释：
简而言之，使用 31 最主要的还是为了性能。
（四）TreeSet的结构和运行原理首先还是来看看官方文档对TreeSet的介绍：
TreeSet底层结构是基于TreeMap的，这一点和HashSet类似。
4.1 TreeSet的特点1.不允许重复（不允许有null值）
2.可以实现对元素的排序（自然排序、定制排序）
自然排序：添加的元素实现Comparable接口，实现里面的compareTo方法
定制排序：创建TreeMap对象时，传入一个Comparator接口，并实现里面的compare方法
3.底层是一个TreeMap，TreeMap底层是一个红黑树结构，可以实现对元素的排序
4.2 TreeSet的实际操作还是新建一个最普通的Book类：

public class Book { private String name; private float price; public Book(String name, float price){ this.name=name; this.price=price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public float getPrice() { return price; } public void setPrice(float price) { this.price = price; } @Override public String toString() { return "Book{" + "name=\'" + name + \'\\\'\' + ", price=" + price + \'}\'; } }

然后新建一个类去使用TreeSet：

public class TreeSetTest { public static void main(String[] args) { TreeSet treeSet=new TreeSet(); treeSet.add(new Book("a",10)); treeSet.add(new Book("b",5)); treeSet.add(new Book("c",20)); System.out.println(treeSet); } }

但是结果是报错的，报错的原因是Book类没有继承Comparable接口

文章图片

解决办法一(自然排序)：在Book类中继承Comparable接口，重写compareTo方法：

public class Book implements Comparable{ ...... @Override public int compareTo(Object o) { Book book= (Book) o; return Float.compare(this.price,book.price); } }

解决办法二（定制排序）：在建TreeMap对象时，传入一个Comparator接口，并实现里面的compare方法。

public class TreeSetTest { public static void main(String[] args) { TreeSet treeSet=new TreeSet(new Comparator() { @Override public int compare(Object o1, Object o2) { Book book1= (Book) o1; Book book2= (Book) o2; return Float.compare(book1.getPrice(),book2.getPrice()); } }); treeSet.add(new Book("a",10)); treeSet.add(new Book("b",5)); treeSet.add(new Book("c",20)); System.out.println(treeSet); } }

4.3 TreeSet去重的方法前面讲到hashSet去重的方法是hashcode和equals方法判断相同则覆盖，TreeSet是通过compareTo方法的返回值来判断是否相同，如果返回值为0则认定是重复元素。
（五）总结最后来总结一些HashSet和TreeSet的区别：
1、TreeSet 是二叉树（红黑树）实现的,Treeset中的数据是自动排好序的，不允许放入null值。
2、HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复。
3、HashSet要求放入的对象实现HashCode()和equals()方法，TreeSet要求放入的对象继承Comparable接口并实现compareTo方法或者在建TreeMap对象时，传入一个Comparator接口，并实现里面的compare方法。
【Set接口及其实现类HashSetTreeSet的底层结构与区别】?