java集合框架——Set

一、Set概述

　　Set集合的特点是元素不允许重复，而且是无序的（添加和取出的顺序不一致）。

　　Set接口中的方法和Collection接口中的方法几乎相同，略。

　　Set接口下常用的两个类：HashSet、TreeSet。

二、HashSet类

1、概述

HashSet内部的数据结构是哈希表，而且是不同步的。

如果添加了重复元素，则重复的元素不会被添加，只保留第一次的对象

2.底层实现

HashSet底层的数据结构是哈希表. 哈希表根据对象的不同特点将对象放在内存中的不同地方，根据的是一个算法，类似这样的结构：

1 function (element)
2 {
3     //一个算法，对元素进行计算，并获取其位置。
4     return index;
5 }

因此，如果想要查找这个对象，只需要通过此算法再算一次，即可找到该对象，这就使得通过哈希表查找元素的速度非常快，而不需要从头遍历。

注意，每个对象都有哈希值，不同的对象拥有不同的哈希值

3.哈希表是怎么判断相同元素的？

（1）哈希表确定元素是否相同第一步判断的是两个元素的哈希值是否相同。如果相同再判断两个对象的内容是否相同。
（2）判断哈希值是否相同其实判断的就是hashCode方法。判断内容是否相同，使用equals方法（自定义对象的时候两个方法均要重写）。
　　注意：如果哈希值不同，则不需要判断equals方法。

4.当哈希值相同，而内容不同的时候，该怎么将对象存储？

　　通过顺延、挂上新链等方式。

5.示例代码：

使用HashSet存储自定义对象。

初始代码：

package p01.BaseCollectionDemo;

import java.util.HashSet;

class Person
{
    private String name;
    private int age;
    public String getName() {
        return name;
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public Person() {
        super();
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]\n";
    }
}

public class HashSetDemo {

    public static void main(String[] args) {
        Demo1();

    }

    private static void Demo1() {
        HashSet hs=new HashSet();
        hs.add(new Person("张三",13));
        hs.add(new Person("李四",14));
        hs.add(new Person("王五",15));
        hs.add(new Person("赵六",16));
        hs.add(new Person("陈七",17));

        hs.add(new Person("张三",13));
        hs.add(new Person("李四",14));
        System.out.println(hs);
    }

}

运行结果：

可以看出，张三、李四添加了两次，这和Set集合不允许添加重复元素相违背。

分析：每次调用add方法都需要和已有的对象做比较，先比较哈希值是否同，如果相同再比较内容是否相同，两个比较是通过hashCode方法、equals方法实现的，但是我们没有重写这两个方法，所以调用了默认的方法，即在Object类中继承而来的方法，hashCode方法是将内存地址转换成整数得到的哈希吗，而equals比较的是对象第至是否相同。因为创建的对象在内存中地址不可能相同，所以HashSet认为是不同的对象。

解决方法：重写hashCode方法和equals方法(这里由于使用了代码补全的功能，所以包括健壮性的判断等做的都很好，可以自定义做出自己的风格)。

package p01.BaseCollectionDemo;

import java.util.HashSet;

class Person
{
    private String name;
    private int age;
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Person other = (Person) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }
    public String getName() {
        return name;
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public Person() {
        super();
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]\n";
    }
}

public class HashSetDemo {

    public static void main(String[] args) {
        Demo1();

    }

    private static void Demo1() {
        HashSet hs=new HashSet();
        hs.add(new Person("张三",13));
        hs.add(new Person("李四",14));
        hs.add(new Person("王五",15));
        hs.add(new Person("赵六",16));
        hs.add(new Person("陈七",17));

        hs.add(new Person("张三",13));
        hs.add(new Person("李四",14));
        System.out.println(hs);
    }

}

6.思考题：去除重复元素（自定义对象）

代码一：

package p01.BaseCollectionDemo;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
class Person
{
    private String name;
    private int age;
    public String getName() {
        return name;
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public Person() {
        super();
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]\n";
    }
}

public class HashSetDemo {

    public static void main(String[] args) {
        Demo1();
    }

    private static void Demo1() {
        ArrayList hs=new ArrayList();
        hs.add(new Person("张三",13));
        hs.add(new Person("李四",14));
        hs.add(new Person("王五",15));
        hs.add(new Person("赵六",16));
        hs.add(new Person("陈七",17));

        hs.add(new Person("张三",13));
        hs.add(new Person("李四",14));
        System.out.println(hs);
        ArrayList la=removeCF(hs);
        System.out.println(la);
    }

    private static ArrayList removeCF(ArrayList hs) {
        ArrayList la=new ArrayList();
        for(Iterator it=hs.iterator();it.hasNext();)
        {
            Person p=(Person)it.next();
            if(!la.contains(p))
            {
                la.add(p);
            }
        }
        return la;
    }

}

运行结果：

经过比较，发现去除重复元素失败。

原因分析：问题代码肯定出现在

1 if(!la.contains(p))

这里，也就是说contains方法的实现有问题。

查找API，API的描述如下：

如果此列表中包含指定的元素，则返回 true。更确切地讲，当且仅当此列表包含至少一个满足 (o==null ? e==null : o.equals(e)) 的元素 e 时，则返回 true。 

所以我们知道了ArrayList 中的contain是方法底层使用的是equals方法，但是我们并没有重写equals方法，这就使得调用了继承自Object类的equals方法，比较的是对象的地址。所以肯定不相同。

解决方法：重写equals方法。

package p01.BaseCollectionDemo;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
class Person
{
    private String name;
    private int age;
    public String getName() {
        return name;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Person other = (Person) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public Person() {
        super();
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]\n";
    }
}

public class HashSetDemo {

    public static void main(String[] args) {
        Demo1();
    }

    private static void Demo1() {
        ArrayList hs=new ArrayList();
        hs.add(new Person("张三",13));
        hs.add(new Person("李四",14));
        hs.add(new Person("王五",15));
        hs.add(new Person("赵六",16));
        hs.add(new Person("陈七",17));

        hs.add(new Person("张三",13));
        hs.add(new Person("李四",14));
        System.out.println(hs);
        ArrayList la=removeCF(hs);
        System.out.println(la);
    }

    private static ArrayList removeCF(ArrayList hs) {
        ArrayList la=new ArrayList();
        for(Iterator it=hs.iterator();it.hasNext();)
        {
            Person p=(Person)it.next();
            if(!la.contains(p))
            {
                la.add(p);
            }
        }
        return la;
    }

}

运行结果。

假设我们将ArrayList换成HashSet，将以上的过程走一遍，结果又如何？结果是两次都失败！原因还在contains方法上。

contains方法的底层实现是

 1  final Entry<K,V> getEntry(Object key) {
 2         int hash = (key == null) ? 0 : hash(key);
 3         for (Entry<K,V> e = table[indexFor(hash, table.length)];
 4              e != null;
 5              e = e.next) {
 6             Object k;
 7             if (e.hash == hash &&
 8                 ((k = e.key) == key || (key != null && key.equals(k))))
 9                 return e;
10         }
11         return null;
12     }

通过这段代码我们可以发现其中一句非常关键：

1 if (e.hash == hash &&
2  8                 ((k = e.key) == key || (key != null && key.equals(k))))
3  9                 return e;

它将不仅使用equals比较对象内容，而且还比较两个对象的哈希值是否相同。即e.hash==hash这一句。所以，还必须重写hashCode方法才行。

package p01.BaseCollectionDemo;
import java.util.HashSet;
import java.util.Iterator;
class Person
{
    private String name;
    private int age;
    public String getName() {
        return name;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Person other = (Person) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public Person() {
        super();
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]\n";
    }
}

public class HashSetDemo {

    public static void main(String[] args) {
        Demo1();
    }

    private static void Demo1() {
        HashSet hs=new HashSet();
        hs.add(new Person("张三",13));
        hs.add(new Person("李四",14));
        hs.add(new Person("王五",15));
        hs.add(new Person("赵六",16));
        hs.add(new Person("陈七",17));

        hs.add(new Person("张三",13));
        hs.add(new Person("李四",14));
        System.out.println(hs);
        HashSet la=removeCF(hs);
        System.out.println(la);
    }

    private static HashSet removeCF(HashSet hs) {
        HashSet la=new HashSet();
        for(Iterator it=hs.iterator();it.hasNext();)
        {
            Person p=(Person)it.next();
            if(!la.contains(p))
            {
                la.add(p);
            }
        }
        return la;
    }

}

运行结果是，重写hashCode方法之后，第一次的添加就已经将重复元素去掉了，这体现了JAVA高度的安全机制。

结论：不同的容器虽然有相同的方法，但是底层实现却不相同。例如，ArrayList的contains方法只需要使用equals方法比较内容是否相同就可以了；但是HashSet的contains方法却需要比较哈希的值同时使用equals方法比较对象的内容，而后面讲到的TreeSet判断元素是否存在的依据就是使用方法compareTo；这种不同是容器底层不同的数据结构导致的。remove方法同理。

三、HashSet子类：LinkedHashSet类

HashSet类是属于Set旗下的类，这就导致了对象的唯一性和有序性不能共存，但是其子类LinkedHashSet弥补了这一缺点，他拥有HashSet的所有特性，同时它又保证了元素的有序。

API1.6的描述：LinkedHashSet：具有可预知迭代顺序的哈希表和链表实现。

也就是说如果我们想让元素唯一，同时又想让元素有序，则使用LinkedHashSet类。

四、TreeSet类

TreeSet类中的方法和其父类基本相同，不再赘述，但是应当掌握其底层实现。

1.引例。

向容器中添加字符串对象，并输出，观察结果。

package p03.TreeSetDemo;

import java.util.TreeSet;

public class TreeSetDemo {

    public static void main(String[] args) {
        Demo1();

    }

    private static void Demo1() {
        TreeSet ts=new TreeSet();
        ts.add("abc1");
        ts.add("abc3");
        ts.add("abc4");
        ts.add("abc2");
        System.out.println(ts);
    }

}

运行结果：[abc1, abc2, abc3, abc4]

观察结果我们可以发现，虽然并不是“有序”的，但是结果却有一些规律，重复添加其它对象，也可以观察到类似的结果。

原因：TreeSet底层的数据结构是一棵排序树，在添加元素的时候其位置就已经被决定了。

这个示例没有问题，现在添加自定义对象。

package p03.TreeSetDemo;

import java.util.TreeSet;

class Person
{
    private String name;
    private int age;
    public Person() {
        super();
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
}
public class TreeSetDemo {

    public static void main(String[] args) {
        //Demo1();
        Demo2();
    }

    private static void Demo2() {
        TreeSet ts=new TreeSet();
        ts.add(new Person("zhangsan",13));
        ts.add(new Person("chenqi",17));
        ts.add(new Person("wangwu",15));
        ts.add(new Person("lisi",14));
        ts.add(new Person("zhaoliu",16));

        System.out.println(ts);
    }

    private static void Demo1() {
        TreeSet ts=new TreeSet();
        ts.add("abc1");
        ts.add("abc3");
        ts.add("abc4");
        ts.add("abc2");
        System.out.println(ts);
    }

}

运行时，出现了异常信息：

根据错误信息，我们可以知道错误发生在第39行，重复操作数次，仍然失败，证明了程序有了问题，但是我们的思路和之前完全相同，应当是没有什么问题。

查找API，查看TreeSet的add方法，发现了和上图相同的异常：ClassCastExceptin。

API描述：ClassCastException - 如果指定对象无法与此 set 的当前元素进行比较 。

也就是说Person类的对象没有比较性导致的异常。怎样让对象具有比较性？

2.使对象具有可比性：使用Comparable接口。

Comparable接口的完整包名为：java.lang.Comparable。

这个接口中只封装了一个方法：compareTo方法。

API描述：

int	compareTo(T o)            比较此对象与指定对象的顺序。

该方法功能： 比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。

更改之前的代码，使得Person类具有可比性，这里是以年龄为参照，并按照年龄大小升序排列。

package p03.TreeSetDemo;

import java.util.TreeSet;

class Person implements Comparable
{
    private String name;
    private int age;
    public Person() {
        super();
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public int compareTo(Object o) {
        Person p=(Person)o;
        if(this.age>p.age)
        {
            return 1;
        }
        else if(this.age<p.age)
        {
            return -1;
        }
        else
        {
            return 0;
        }
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]"+"\n";
    }

}
public class TreeSetDemo {

    public static void main(String[] args) {
        //Demo1();
        Demo2();
    }

    private static void Demo2() {
        TreeSet<Person> ts=new TreeSet();
        ts.add(new Person("zhangsan",13));
        ts.add(new Person("chenqi",17));
        ts.add(new Person("wangwu",15));
        ts.add(new Person("lisi",14));
        ts.add(new Person("zhaoliu",16));

        System.out.println(ts);
    }

    private static void Demo1() {
        TreeSet ts=new TreeSet();
        ts.add("abc1");
        ts.add("abc3");
        ts.add("abc4");
        ts.add("abc2");
        System.out.println(ts);
    }

}

运行结果：

从结果中我们可以看出年龄确实是按照从小到大排序了。

思考：如果我们又想要按照名字排序，该怎么做？只需要更改compareTo方法即可，但是反复的更改程序并不是治本的方法。解决方法是使用比较器。

3.使集合具有比较功能：使用Comparator接口

Comparator的完整包名为：java.util.Comparator。

实现Comparator接口的对象称为比较器。它封装了两个方法：

方法摘要
int	compare(T o1, T o2)            比较用来排序的两个参数。
boolean	equals(Object obj)            指示某个其他对象是否“等于”此 Comparator。

我们最常使用的就是compare方法了。

API对于compare方法的描述：比较用来排序的两个参数。根据第一个参数小于、等于或大于第二个参数分别返回负整数、零或正整数。

我们知道TreeSet在使用add方法的时候就已经具有比较功能了，所以它在构造的时候就必须拥有比较器（本来应当有set方法，但是很遗憾API中并没有提及），即构造方法中必定有一个方法参数是比较器。

TreeSet(Comparator<? super E> comparator)            构造一个新的空 TreeSet，它根据指定比较器进行排序。

改造之前的代码，使其按照名字的字典序排序。

package p03.TreeSetDemo;

import java.util.Comparator;
import java.util.TreeSet;
class NewComparator implements Comparator
{

    @Override
    public int compare(Object o1, Object o2) {
        Person p1=(Person)o1;
        Person p2=(Person)o2;
        int temp=p1.getName().compareTo(p2.getName());
        return temp==0?(p1.getAge()-p2.getAge()):temp;//按照字典序将名字排序，如果名字相同，则
        //按照年龄大小从小到大排序。
    }
}
class Person implements Comparable
{
    private String name;
    private int age;
    public Person() {
        super();
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public int compareTo(Object o) {
        Person p=(Person)o;
        if(this.age>p.age)
        {
            return 1;
        }
        else if(this.age<p.age)
        {
            return -1;
        }
        else
        {
            return 0;
        }
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]"+"\n";
    }

}
public class TreeSetDemo {

    public static void main(String[] args) {
        //Demo1();
        //Demo2();
        Demo3();
    }

    private static void Demo3() {
        TreeSet ts=new TreeSet(new NewComparator());
        ts.add(new Person("zhangsan",13));
        ts.add(new Person("chenqi",17));
        ts.add(new Person("wangwu",15));
        ts.add(new Person("lisi",14));
        ts.add(new Person("zhaoliu",16));

        ts.add(new Person("zhangsan",11));//加入了名字相同但是年龄不同的对象

        System.out.println(ts);
    }

    private static void Demo2() {
        TreeSet<Person> ts=new TreeSet();
        ts.add(new Person("zhangsan",13));
        ts.add(new Person("chenqi",17));
        ts.add(new Person("wangwu",15));
        ts.add(new Person("lisi",14));
        ts.add(new Person("zhaoliu",16));

        System.out.println(ts);
    }

    private static void Demo1() {
        TreeSet ts=new TreeSet();
        ts.add("abc1");
        ts.add("abc3");
        ts.add("abc4");
        ts.add("abc2");
        System.out.println(ts);
    }

}

运行结果：

观察结果，和预期结果相同。

4.比较两种比较方法

实现Comparable接口的对象具有比较的功能，这种使对象具有比较性的方法为自然比较方法。实现这个接口的类有很多，比如之前使用的字符串类，使用它作为TreeSet容器的元素的时候没有报错正是因为String类实现了Comparable接口。所有的基本数据类型包装类都实现了此接口。除此之外还有很多类都实现了此接口，因为只要对象想要具备比较性，就需要此接口，此接口中的compareTo方法正是用于比较对象的。简单来说，该方法的功能就是让对象本身具备比较性。

实现Comparator接口的类称为比较器，如果对象具备了自然比较的属性，同时集合又拥有了比较器，则优先使用比较器。即对象的自然比较属性将会无效。简单来说，该方法的功能呢就是让集合具备比较性。

应当注意：compareTo方法中的this指的是当前对象，即正在插入的对象；而compare方法的第一个参数是当前对象，即正在插入的对象。

5.如何使得TreeSet有序？

所谓有序，即怎么添加的就怎么取出来，添加和取出的顺序相同。

假设此时对象已经拥有了比较性，则这时候只能使用Comparator接口。

思路：让当前的对象永远大于当前集合中的所有对象即可。即让compare方法返回1；

package p03.TreeSetDemo;

import java.util.Comparator;
import java.util.TreeSet;
class NewComparator implements Comparator
{

    @Override
    public int compare(Object o1, Object o2) {
//        Person p1=(Person)o1;
//        Person p2=(Person)o2;
//        int temp=p1.getName().compareTo(p2.getName());
//        return temp==0?(p1.getAge()-p2.getAge()):temp;//按照字典序将名字排序，如果名字相同，则
        //按照年龄大小从小到大排序。
        return 1;
    }
}
class Person implements Comparable
{
    private String name;
    private int age;
    public Person() {
        super();
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public int compareTo(Object o) {
        Person p=(Person)o;
        if(this.age>p.age)
        {
            return 1;
        }
        else if(this.age<p.age)
        {
            return -1;
        }
        else
        {
            return 0;
        }
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]"+"\n";
    }

}
public class TreeSetDemo {

    public static void main(String[] args) {
        //Demo1();
        //Demo2();
        Demo3();
    }

    private static void Demo3() {
        TreeSet ts=new TreeSet(new NewComparator());
        ts.add(new Person("zhangsan",13));
        ts.add(new Person("chenqi",17));
        ts.add(new Person("wangwu",15));
        ts.add(new Person("lisi",14));
        ts.add(new Person("zhaoliu",16));

        ts.add(new Person("zhangsan",11));//加入了名字相同但是年龄不同的对象

        System.out.println(ts);
    }

    private static void Demo2() {
        TreeSet<Person> ts=new TreeSet();
        ts.add(new Person("zhangsan",13));
        ts.add(new Person("chenqi",17));
        ts.add(new Person("wangwu",15));
        ts.add(new Person("lisi",14));
        ts.add(new Person("zhaoliu",16));

        System.out.println(ts);
    }

    private static void Demo1() {
        TreeSet ts=new TreeSet();
        ts.add("abc1");
        ts.add("abc3");
        ts.add("abc4");
        ts.add("abc2");
        System.out.println(ts);
    }

}