Set接口及其实现类HashSet、TreeSet的底层结构与区别

2021年09月15日 阅读数:1
这篇文章主要向大家介绍Set接口及其实现类HashSet、TreeSet的底层结构与区别,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

据说微信搜索《Java鱼仔》会变动强哦!java

本文收录于githubgitee ,里面有我完整的Java系列文章,学习或面试均可以看看哦
git

(一)Set接口的特色

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its namegithub

Set接口是Collection的子接口,经过上面这段官方文档对Set的介绍能够看出Set的两个特色:面试

1.无序(插入和取出的顺序不一致)微信

2.不可重复(全部元素只能出现一次,所以null也只能有一个)markdown

Set的全部方法均来自Collection,没有本身的特有方法。HashSet和TreeSet是Set接口最经常使用的实现类ide

(二)HashSet的底层结构

首先仍是先来看看官方文档对HashSet的介绍:性能

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.学习

总结一下:HashSet继承Set接口,底层是一个哈希表,可是其实是HashMap(这点能够从源码中看出来)。它是无序的(插入和取出的顺序不一致),它容许空节点。优化

咱们先看一下源码:

image.png

HashSet在构造方法中构造了一个HashMap,所以对源码的解读会放到HashMap中,如今主要说一下HashSet的底层实现结构。

2.1 HashSet为何是不重复和无序的

这个问题其实知道Hash表如何构造就很容易理解。

1.当有一个元素要进入hash表时,先获取该元素的哈希值,再经过一系列运算获得一个索引。(每一个元素都能计算出一个索引值,但索引值并不是是有序的,所以最终获得一个无序的哈希表。)

2.当该索引处没有元素,则直接插入

3.若该索引处有元素,则须要逐个经过equals判断,若是依旧不相等,则将元素以链表的形式添加在该索引的后面。若是相等,则覆盖原来的元素,实现不重复。

哈希表的链地址法如图所示:

image.png

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

可是结果却并无把咱们认为的重复元素(名称和价格相等就算重复)给去重

image.png

咱们前面讲过,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, 是由于他是一个奇素数。若是乘数是偶数,而且乘法溢出的话,信息就会丢失,由于与2相乘等价于移位运算(低位补0)。使用素数的好处并不很明显,可是习惯上使用素数来计算散列结果。 31 有个很好的性能,即用移位和减法来代替乘法,能够获得更好的性能: 31 * i == (i << 5)- i, 现代的 VM 能够自动完成这种优化。这个公式能够很简单的推导出来。

简而言之,使用 31 最主要的仍是为了性能。

(四)TreeSet的结构和运行原理

首先仍是来看看官方文档对TreeSet的介绍:

A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

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接口

image.png

解决办法一(天然排序):在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的区别:

一、TreeSet 是二叉树(红黑树)实现的,Treeset中的数据是自动排好序的,不容许放入null值。

二、HashSet 是哈希表实现的,HashSet中的数据是无序的,能够放入null,但只能放入一个null,二者中的值都不能重复。

三、HashSet要求放入的对象实现HashCode()和equals()方法,TreeSet要求放入的对象继承Comparable接口并实现compareTo方法或者在建TreeMap对象时,传入一个Comparator接口,并实现里面的compare方法。

扫码_搜索联合传播样式白色版 中号 小号.jpg