Java的Set接口

Set接口简介

Set接口是Collection的子接口，set接口没有提供额外的方法。

Set集合不允许包含相同的元素，如果试把两个相同的元素加入同一个 Set 集合中，则添加操作失败。

Set判断两个对象是否相同不是使用 == 运算符，而是根据 equals 方法。

Set接口的实例无法像List接口那样进行双向输出。

Set实现类之一：HashSet（散列存放）

HashSet 是 Set 接口的典型实现，由哈希表（实际上是一个 HashMap 实例）支持。大多数时候使用 Set 集合时都使用这个实现类。

HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取和查找性能。

HashSet 具有以下特点：

1）不能保证元素的排列顺序（里面不能存放重复元素，而且是采用散列的存储方式）

2）HashSet 不是线程安全的

3）集合元素可以是 null

当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值，然后根据 hashCode 值决定该对象在 HashSet 中的存储位置。

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

HashSet的实现

对于 HashSet 而言，它是基于 HashMap 实现的， HashSet 底层使用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成。

hashCode() 方法

如果两个元素的 equals() 方法返回 true，但它们的 hashCode() 返回值不相等，hashSet 将会把它们存储在不同的位置，但依然可以添加成功。

对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。

重写 hashCode() 方法的基本原则：

1）在程序运行时，同一个对象多次调用 hashCode() 方法应该返回相同的值

2）当两个对象的 equals() 方法比较返回 true 时，这两个对象的 hashCode() 方法的返回值也应相等

3）对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值

Set实现类之二：LinkedHashSet

LinkedHashSet 是 HashSet 的子类。

LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的。

LinkedHashSet插入性能略低于HashSet，但在迭代访问Set 里的全部元素时有很好的性能。

LinkedHashSet 不允许集合元素重复。

Set实现类之三：TreeSet（有序存放）

TreeSet 是 SortedSet 接口的实现类，TreeSet可以确保集合元素处于排序状态。

Comparator comparator()

Object first()

Object last()

Object lower(Object e)

Object higher(Object e)

SortedSet subSet(fromElement, toElement)

SortedSet headSet(toElement)

SortedSet tailSet(fromElement)

注：    [1]一个普通的类对象是不能向TreeSet集合中加入的，否则会出现异常：java.lang.ClassCastException。

[2]如果要想使用TreeSet则对象所在的类必须实现Comparable接口。

TreeSet的排序方法

TreeSet 两种排序方法：自然排序和定制排序。默认情况下，TreeSet采用自然排序。

自然排序：

TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系，然后将集合元素按升序排列。

如果试图把一个对象添加到TreeSet时，则该对象的类必须实现Comparable接口。

实现 Comparable 的类必须实现 compareTo(Object obj) 方法，两个对象即通过 compareTo(Object obj) 方法的返回值来比较大小。

Comparable 的典型实现：

BigDecimal、BigInteger 以及所有的数值型对应的包装类：按它们对应的数值大小进行比较

Character：按字符的 unicode值来进行比较

Boolean：true 对应的包装类实例大于 false 对应的包装类实例

String：按字符串中字符的 unicode 值进行比较

Date、Time：后边的时间、日期比前面的时间、日期大

向 TreeSet 中添加元素时，只有第一个元素无须比较compareTo()方法，后面添加的所有元素都会调用compareTo()方法进行比较。

因为只有相同类的两个实例才会比较大小，所以向 TreeSet 中添加的应该是同一个类的对象。

对于TreeSet 集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过 compareTo(Object obj) 方法比较返回值。

当需要把一个对象放入 TreeSet 中，重写该对象对应的 equals() 方法时，应保证该方法与 compareTo(Object obj) 方法有一致的结果：如果两个对象通过 equals() 方法比较返回 true，则通过 compareTo(Object obj) 方法比较应返回 0。

示例：

@Test

public void testTreeSet1() {

Set set = new TreeSet();

// 当Person类没有实现Comparable接口时，当向TreeSet中添加Person对象时，

报ClassCastException

set.add(new Person("CC", 23));

set.add(new Person("MM", 21));

set.add(new Person("GG", 25));

set.add(new Person("JJ", 24));

set.add(new Person("KK", 20));

set.add(new Person("DD", 20));

for (Object str : set) {

          System.out.println(str);

}

}

public class Person implements Comparable{

private String name;

private Integer age;

//getter&setter&const…

@Override

public int hashCode() {

//return age.hashCode() + name.hashCode();没下述的健壮性好。

final int prime = 31;

int result = 1;

result = prime * result + ((age == null) ? 0 : age.hashCode());

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 == null) {

    if (other.age != null)

        return false;

    } else if (!age.equals(other.age))

        return false;

if (name == null) {

    if (other.name != null)

        return false;

} else if (!name.equals(other.name))

    return false;

return true;

}

//当向TreeSet中添加Person类的对象时，依据此方法，确定按照哪个属性排列。

@Override

public int compareTo(Object o) {

if(o instanceof Person){

    Person p = (Person)o;

    int i = this.age.compareTo(p.age);

    if(i == 0){

        return this.name.compareTo(p.name);

    }else{

        return i;

    }

}

return 0;

}

}

定制排序：

TreeSet的自然排序是根据集合元素的大小，进行元素升序排列。如果需要定制排序，比如降序排列，可通过Comparator接口的帮助。需要重写compare(T o1,T o2)方法。

利用int compare(T o1,T o2)方法，比较o1和o2的大小：如果方法返回正整数，则表示o1大于o2；如果返回0，表示相等；返回负整数，表示o1小于o2。

要实现定制排序，需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。此时，仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。

使用定制排序判断两个元素相等的标准是：通过Comparator比较两个元素返回了0。

示例：

测试类：

public void testTreeSet3() {

      TreeSet set = new TreeSet(new Comparator() {

public int compare(Object o1, Object o2) {

    if (o1 instanceof Customer && o2 instanceof Customer) {

        Customer c1 = (Customer) o1;

        Customer c2 = (Customer) o2;

        int i = c1.getId().compareTo(c2.getId());

        if (i == 0) {

            return c1.getName().compareTo(c2.getName());

        }

        return i;

    }

    return 0;

}

      });

      set.add(new Customer("AA", 1003));

      set.add(new Customer("BB", 1002));

      set.add(new Customer("GG", 1004));

      set.add(new Customer("CC", 1001));

      set.add(new Customer("DD", 1001));

      for (Object str : set) {

            System.out.println(str);

      }

}

Customer类：

public class Customer {

private String name;

private Integer id;

//getter&setter&cosntr…

@Override

public int hashCode() {

      final int prime = 31;

      int result = 1;

      result = prime * result + ((id == null) ? 0 : id.hashCode());

      result = prime * result + ((name == null) ? 0 : name.hashCode());

      return result;

}

@Override

public boolean equals(Object obj) {

//……

}

}

Comparable 和 Comparator 接口是干什么的？

Java 提供了只包含一个 compareTo()方法的 Comparable 接口。这个方法可以个给两个对象排序。具体来说，它返回负数， 0，正数来表明输入对象小于，等于，大于已经存在的对象。

Java 提供了包含 compare()和 equals()两个方法的 Comparator 接口。 compare()方法用来给两个输入参数排序，返回负数， 0，正数表明第一个参数是小于，等于，大于第二个参数。 equals()方法需要一个对象作为参数，它用来决定输入参数是否和 comparator 相等。只有当输入参数也是一个 comparator 并且输入参数和当前 comparator 的排序结果是相同的时候，这个方法才返回 true。

HashSet 和 TreeSet 有什么区别？

HashSet 是由一个 hash 表来实现的，因此，它的元素是无序的。 add()， remove()， contains()方法的时间复杂度是 O(1)。

另一方面， TreeSet 是由一个树形的结构来实现的，它里面的元素是有序的。因此， add()，remove()， contains()方法的时间复杂度是 O(logn)。