当前位置：首页 > news >正文

【Java to Architect】HashSet TreeSet 集合红黑树

news 来源：原创 2024/5/3 3:39:44

概论

Set集合继承了AbstractCollection集合，它的核心特点是没有重复元素，无序。
TreeSet集合（红黑树），在没有重复元素的基础上，还能够将元素进行排序储存。

Set

我将通过典型的HashSet来了解Set的特性。HashSet实现Set的方式是通过Hash表确保元素的唯一性。而Hash表中，又将分别进行两个动作来判断将要储存的元素是否唯一。

*hashCode()*方法
equals() 方法

在往HashSet内添加值时，会分别进行以上两个步骤。HashSet允许储存：

与现有元素集哈希值不同的元素
与现有元素集哈希值相同，但是 equals() 返回false的元素。

除了以上两种元素，其他元素都会被拒之门外。
因此，在使用HashSet储存对象时，我们需要重写对象的这两个方法，以便满足我们对储存对象数据唯一性的要求。

HashSet例子：

在这个例子中，我写了一个Band类，在这个类中，有三个内部变量：name，style，rate，在判断HashCode上，我选择用name和rate判断，在equals上，我选择name和style判断。

class Band implements {
    private String name;
    private String style;
    private int rate;

    Band() {

    }

    public Band(String name, String style, int rate) {
        this.name = name;
        this.style = style;
        this.rate = rate;
    }

    public String getName() {
        return this.name;
    }

    public String getStyle() {
        return this.style;
    }

    public int getRate() {
        return this.rate;
    }

    public void setRate(int rate) {
        this.rate = rate;
    }

    @Override
    public int hashCode() {
        System.out.println(this.toString() + "'s hashCode: " + this.name.hashCode() + this.rate * 37);
        return this.name.hashCode() + this.rate * 37;
    }

    @Override
    public boolean equals(Object obj) {
        System.out.println(this + "---equals---" + obj);
        if (obj instanceof Band) {
            Band bd  = (Band)obj;
            return this.name.equals(bd.name) && this.style.equals(bd.style);
        } else {
            return false;
        }
    }

    @Override
    public String toString() {
        return "Band@name: " + this.name + " style: " + this.style + " rate: " + this.rate;
    }
}

在主方法中，我们来尝试一下HashSet判断一致性的过程：

public static void main(String[] args) {
        HashSet<Band> hs = new HashSet<Band>();
        hs.add(new Band("Smashing Pumpkins", "Rock", 99));
        hs.add(new Band("Smashing Pumpkins", "Rock", 98));
        hs.add(new Band("Smashing Pumpkins", "Rock", 98));
        hs.add(new Band("Smashing Pumpkins", "synth", 97));
        hs.add(new Band("Smashing Pumpkins", "synth", 97));
        hs.add(new Band("Smashing Pumpkins", "synth", 96));
        hs.add(new Band("Smashing Pumpkins", "alternative", 95));
        hs.add(new Band("Smashing Pumpkins", "alternative", 94));
        Iterator<Band> it = hs.iterator();
		while (it.hasNext()) {
			Object next = it.next();
			System.out.println(next);
        }
    }

终端输出：

Band@name: Smashing Pumpkins style: Rock rate: 99's hashCode: -2287338513663
Band@name: Smashing Pumpkins style: Rock rate: 98's hashCode: -2287338513626
Band@name: Smashing Pumpkins style: Rock rate: 98's hashCode: -2287338513626
Band@name: Smashing Pumpkins style: Rock rate: 98---equals---Band@name: Smashing Pumpkins style: Rock rate: 98  
Band@name: Smashing Pumpkins style: synth rate: 97's hashCode: -2287338513589
Band@name: Smashing Pumpkins style: synth rate: 97's hashCode: -2287338513589
Band@name: Smashing Pumpkins style: synth rate: 97---equals---Band@name: Smashing Pumpkins style: synth rate: 97
Band@name: Smashing Pumpkins style: synth rate: 96's hashCode: -2287338513552
Band@name: Smashing Pumpkins style: alternative rate: 95's hashCode: -2287338513515
Band@name: Smashing Pumpkins style: alternative rate: 94's hashCode: -2287338513478
------------------------------ HashSet Elements ----------------------------
Band@name: Smashing Pumpkins style: Rock rate: 98
Band@name: Smashing Pumpkins style: alternative rate: 94
Band@name: Smashing Pumpkins style: synth rate: 97
Band@name: Smashing Pumpkins style: synth rate: 96
Band@name: Smashing Pumpkins style: Rock rate: 99
Band@name: Smashing Pumpkins style: alternative rate: 95

从输出上看到，当发现有一个元素的hashCode撞到元素集中的某一个元素后，HashSet会调用对象的equals方法来看二者是否一致，如果判断不一致，则拒绝添加。在输出HashSet所有元素时，我们可以看到它是无序的，与添加顺序、对象值并无关系。

红黑树（TreeSet）

如果需求中，既需要不重复，又需要排序，则TreeSet是合理的选择。在唯一性的基础上，往红黑树里添加元素时，会有一个比较的过程。而这个比较的过程会有两种方法实现：

将对象继承Comparable，并重写实现compareTo方法
在红黑树容器中，指定一个比较器（Comparator）

红黑树例子：

对象自身比较方法 - 将Band对象实现Comparable接口并且重写compareTo方法

class Band implements Comparable<Band>{
    private String name;
    private String style;
    private int rate;

    Band() {

    }

    public Band(String name, String style, int rate) {
        this.name = name;
        this.style = style;
        this.rate = rate;
    }

    public String getName() {
        return this.name;
    }

    public String getStyle() {
        return this.style;
    }

    public int getRate() {
        return this.rate;
    }

    public void setRate(int rate) {
        this.rate = rate;
    }

    @Override
    public int hashCode() {
        System.out.println(this.toString() + "'s hashCode: " + this.name.hashCode() + this.rate * 37);
        return this.name.hashCode() + this.rate * 37;
    }

    @Override
    public boolean equals(Object obj) {
        System.out.println(this + "---equals---" + obj);
        if (obj instanceof Band) {
            Band bd  = (Band)obj;
            return this.name.equals(bd.name) && this.style.equals(bd.style);
        } else {
            return false;
        }
    }

    @Override
    public String toString() {
        return "Band@name: " + this.name + " style: " + this.style + " rate: " + this.rate;
    }

    @Override
    public int compareTo(Band obj) {
        Band bd = (Band)obj;
        System.out.println(this + " compare to: " + bd);
        if (this.rate > bd.rate) {
            return -1;
        }
        if (this.rate < bd.rate) {
            return 1;
        }
        return this.name.compareTo(bd.name);
    }
}

在这里，我用Band对象的rate值来比较两个band。在主函数中，我们看一下红黑树时怎么储存元素的：

public static void main(String[] args) {
	TreeSet<Band> ts = new TreeSet<Band>();
        ts.add(new Band("Smashing Pumpkins", "Alternative", 100));
        ts.add(new Band("Guns'n'Roses", "Rock", 95));
        ts.add(new Band("Radiohead", "Alternative", 98));
        ts.add(new Band("Oasis", "Rock", 75));
        ts.add(new Band("Queen", "Rock", 95));
        Iterator<Band> ib = ts.iterator();
        while (ib.hasNext()) {
            Object next = ib.next();
            System.out.println(next);
        }
 }

输出：

Band@name: Smashing Pumpkins style: Alternative rate: 100 compare to: Band@name: Smashing Pumpkins style: Alternative rate: 100
Band@name: Guns'n'Roses style: Rock rate: 95 compare to: Band@name: Smashing Pumpkins style: Alternative rate: 100
Band@name: Radiohead style: Alternative rate: 98 compare to: Band@name: Smashing Pumpkins style: Alternative rate: 100
Band@name: Radiohead style: Alternative rate: 98 compare to: Band@name: Guns'n'Roses style: Rock rate: 95       
Band@name: Oasis style: Rock rate: 75 compare to: Band@name: Radiohead style: Alternative rate: 98
Band@name: Oasis style: Rock rate: 75 compare to: Band@name: Guns'n'Roses style: Rock rate: 95
Band@name: Queen style: Rock rate: 95 compare to: Band@name: Radiohead style: Alternative rate: 98
Band@name: Queen style: Rock rate: 95 compare to: Band@name: Guns'n'Roses style: Rock rate: 95
Band@name: Queen style: Rock rate: 95 compare to: Band@name: Oasis style: Rock rate: 75
------------------------------ TreeSet Elements ----------------------------
Band@name: Smashing Pumpkins style: Alternative rate: 100
Band@name: Radiohead style: Alternative rate: 98
Band@name: Guns'n'Roses style: Rock rate: 95
Band@name: Queen style: Rock rate: 95
Band@name: Oasis style: Rock rate: 75

现在，红黑树中已经根据rate来排序了，从输出中，我们也看到在排到最终位置之前，元素会被与各种节点比较。

下面来看一下如何用比较器构造红黑树：

class BandComparator implements Comparator<Band> {
    public int compare(Band o1, Band o2) {
        Band b1 = (Band)o1;
        Band b2 = (Band)o2;
        System.out.println(b1 + " comparator " + b2);
        if (b1.getRate() > b2.getRate()) {
            return 1;
        }
        if (b1.getRate() < b2.getRate()) {
            return -1;
        }
        return b1.getName().compareTo(b2.getName());
    }
}

然后在主函数中，把构造器传入红黑树实例：

public static void main(String[] args) {
	TreeSet<Band> tswc = new TreeSet<Band>(new BandComparator());
        tswc.add(new Band("Smashing Pumpkins", "Alternative", 100));
        tswc.add(new Band("Guns'n'Roses", "Rock", 95));
        tswc.add(new Band("Radiohead", "Alternative", 98));
        tswc.add(new Band("Oasis", "Rock", 75));
        tswc.add(new Band("Queen", "Rock", 95));
        Iterator<Band> ic = tswc.iterator();
        while (ic.hasNext()) {
            Object next = ic.next();
            System.out.println(next);
        }
 }

输出：

Band@name: Smashing Pumpkins style: Alternative rate: 100 comparator Band@name: Smashing Pumpkins style: Alternative rate: 100
Band@name: Guns'n'Roses style: Rock rate: 95 comparator Band@name: Smashing Pumpkins style: Alternative rate: 100
Band@name: Radiohead style: Alternative rate: 98 comparator Band@name: Smashing Pumpkins style: Alternative rate: 100
Band@name: Radiohead style: Alternative rate: 98 comparator Band@name: Guns'n'Roses style: Rock rate: 95        
Band@name: Oasis style: Rock rate: 75 comparator Band@name: Radiohead style: Alternative rate: 98
Band@name: Oasis style: Rock rate: 75 comparator Band@name: Guns'n'Roses style: Rock rate: 95
Band@name: Queen style: Rock rate: 95 comparator Band@name: Radiohead style: Alternative rate: 98
Band@name: Queen style: Rock rate: 95 comparator Band@name: Guns'n'Roses style: Rock rate: 95
------------------------------ TreeSet Elements ----------------------------
Band@name: Oasis style: Rock rate: 75
Band@name: Guns'n'Roses style: Rock rate: 95
Band@name: Queen style: Rock rate: 95
Band@name: Radiohead style: Alternative rate: 98
Band@name: Smashing Pumpkins style: Alternative rate: 100