Java集合(二)-Set集合

Love The Way You Lie 2022-12-11 15:30 229阅读 0赞

> 来源：流浪舟 https://www.maliaoblog.cn/2020/1003  
> 公众号： 菜鸡干Java

### 文章目录 ###

*   *   *   *  HashSet类
             *   *  重写hashCode方法步骤
             *  LinkedHashSet
             *  TreeSet(SortedSet的实现类)
             *   *  1.自然排序
                 *  2.定制排序
             *  EnumSet类
             *  各Set实现类的性能分析

Set集合和Collection基本相同，没有提供额外的方法，主要是行为上的不同，Set不允许包含重复元素，否则 `add()`方法会返回 `false`。接下来将主要介绍四种 `Set`类， `HashSet`， `TreeSet`， `LinkedHashSet`， `EnumSet`四种。

#### HashSet类 ####

HashSet使用`hash算法`来储存集合中的元素，具有很好的查找和存取性能，它的特点如下：

1.  不能保证元素的顺序，可能变化
2.  `HashSet`不是同步的，如果多个线程同时访问并修改一个`HashSet`，则必须保证其同步。
3.  集合的元素可以是`null`

当向`HashSet`集合中存入一个元素时，`HashSet`会调用对象的`hashCode()`方法来得到该对象的`hashCode`值，然后根据该`hashCode`值决定该对象在`HashSet`中的位置。但是如果两个元素通过`equals()`方法返回`true`，而它们的`hahCode()`方法返回值不相等，`HashSet`将会把他们储存在不同的位置，依然可以添加成功。也就是说，HashSet集合判断元素相等的标准是通过`equals`方法比较相等，并且两个对象的`hashCode`值一样。

Class A{ 
        public boolean equals(Object obj){ 
            return true;
        }
    }
    Class B{ 
        public int hashCode(){ 
            return 1;
        }
    }
    Class C{ 
        public int hashCode(){ 
            return 2;
        }
        public boolean equals(Object obj){ 
            return true;
        }
    }
    public Class HashSet{ 
        public static void main(String[] args){ 
            HashSet books = new HashSet();
            books.add(new A());
            books.add(new A());
            books.add(new B());
            books.add(new B());
            books.add(new C());
            books.add(new C());
        }
    }//添加两A,B,C对象

[B@1 ,B@1 ,C@2 ,A@54d ,A@8773f2]

从上面看出，即使A对象equals方法返回true，依然被当作两个对象；即使两个B对象`hashCode`方法返回值一样，但HashSet集合储存了两个hash值一样的对象。如果equals返回true，但是会放在不同的地方，不太好。如果hash值一样，但equals返回的false也麻烦了，集合会尝试保存把对象保存在同一个位置，并采用链式结构来保存多个对象，这样会导致利用哈希值查找的时候，性能下降。

所以总结一句：如果需要把对象保存到HashSet集合中去，重写类的`equals`和`hashCode`方法，保证equals返回true时，hashCode返回值一样。

HashSet中每个能储存元素的位置通常称为桶(bucket)，如果有多个元素的哈希值相同，但它们通过equals方法返回`false`，就需要在一个桶内放多个元素，然而这样会导致性能下降。

##### 重写hashCode方法步骤 #####

1.  把对象内的每个参与`equals`方法比较的实例变量计算处一个`int`类型的哈希值

<table> 
 <thead> 
  <tr> 
   <th>实例变量类型</th> 
   <th>计算方式</th> 
   <th>实例变量类型</th> 
   <th>计算方式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean</td> 
   <td>hashCode = (f ? 0 : 1)</td> 
   <td>float</td> 
   <td>hashCode = Float.floatToIntBits(f)</td> 
  </tr> 
  <tr> 
   <td>整型byte、char、short、int</td> 
   <td>hashCode = (int)f</td> 
   <td>double</td> 
   <td>long L = Double.doubleToLongBits(f);<br>hashCode = (int)(L^(L&gt;&gt;&gt;32));</td> 
  </tr> 
  <tr> 
   <td>Long</td> 
   <td>hashCode = (int)(f^(f&gt;&gt;&gt;32));</td> 
   <td>引用</td> 
   <td>hashCode = f.hashCode();</td> 
  </tr> 
 </tbody> 
</table>

2.用第一步计算出的多个哈希值组合计算出一个哈希值返回，例如：

return f1.hashCode() + (int)f2;//f1,f2为实例变量

为避免直接相加产生的偶然，可以为各实例变量的哈希值乘以任意质数后再相加。但还有一点需要了解的是，这样并不能完全保证之后就不会产生两个相同的对象，向HashSet中添加可变对象后，后面修改了可变对象的实例变量，可能导致它和集合中其他元素相同，甚至不能正确访问(储存在不同位置，hash值不一样)。

#### LinkedHashSet ####

HashSet还有一个子类`LinkedHashSet`，同样也是根据元素的`hashCode`值来决定元素的储存位置，不同的是它使用链表维护元素的次序，这样可以以插入顺序保存元素。`LinkedHashSet`需要链表维护次序，所以性能略低于`HashSet`，但优势在于遍历集合内元素上。另外注意一点，它还是`Set`，所以依然不允许元素重复！

LinkedHashSet names = new LinkedHashSet();
    names.add("James");
    names.add("Jodan");
    System.out.println(names);
    //James,Jodan

#### TreeSet(SortedSet的实现类) ####

既然是实现类，那`SortedSet`就是`TreeSet`的接口了，顾名思义，`TreeSet`可以让元素处于一定次序状态。与`HashSet`相比，TreeSet额外提供了如下方法：

*  Comparator comparator()：如果TreeSet采用定制排序，则返回定制排序所使用的Comparator，如果采用自然排序，则返回`null`
 *  Object first()：返回第一个元素
 *  Object last()：返回最后一个元素
 *  Object lower(Object e)：返回处于指定元素(任意元素，不需要在集合中)之前的元素
 *  Object higner(Object e)：返回处于指定元素之后(更大的元素)的元素
 *  SortedSet subSet(Object e1,Object e2)：返回从e1到e2的子集合(不包含e1,e2)
 *  SortedSet headSet(Object max)：返回子集合，元素都小于max
 *  SortedSet tailSet(Object min)：返回子集合，元素大于等于min

综上，大概就是提供了访问第一个、最后一个、前一个、后一个元素的方法，并提供了三个截取子集合的方法。与此同时，`TreeSet`采用红黑树的数据结构来储存数据，默认情况下使用`自然排序`。它的排序规则有以下两种：

##### 1.自然排序 #####

TreeSet调用集合元素的compareTo(Object obj)方法来比较元素之间的大小关系，然后将集合元素按升序排列，这种就是自然排序。Java提供了`Comparable`接口，该接口内定义了一个`compareTo(Object o)`方法，方法返回一个整数。实现接口就必须实现该方法。当一个对象之间进行比较时，例如：obj1.compareTo(obj2)，如果返回0，则表明这两个对象相等；如果返回一个正整数，则obj1大于obj2；如果返回一个负整数，则obj1小于obj2。

下面提供了实现`Comparable`接口的类，并提供了比较大小的标准。

*  BigDecimal、BigInteger以及所有数值类型对应的包装类：按数值大小比较
 *  Character：按字符的`Unicode`进行比较
 *  Boolean：true对应的包装类实例大于`false`对应的包装类实例
 *  String：按字符串中字符的`Unicode`值比较
 *  Date、Time：后面的时间、日期比前面的日期大

所以TreeSet会自动地给集合中地大小进行排序，但前提是对象实现了`Comparable`接口，否则将不可行。还有一点需要说明，大部分类在实现compareTo(Object o)方法时，都需要将被比较对象强制类型转换成相同类型，否则无法比较。然而当添加一个对象到集合中去时，集合会调用对象`compareTo()`方法与集合中的其他元素进行比较，比较要是同一类的对象。

如果向TreeSet添加对象是自定义对象，则可以向TreeSet中添加多种类型对象，但这并不表明这是最好的选择，也不推荐这样干，当取出对象时，元素之间会报`ClassCastException`异常。

当把一个对象加入集合中时，集合调用对象的`compareTo`方法与容器的其他对象比较，然后根据红黑树结构找到它的储存位置。如果两个对象通过`compareTo(Object obj)`方法比较相等，新对象将无法添加到集合中。总之，如果要不报错，TreeSet中只能添加同一种类型的对象。

对于TreeSet集合而言，判断两个对象相等的唯一标准是：两个对象通过`compareTo(Object obj)`方法比较相等，返回0，则相等。所以它的添加元素的规则和`HashSet`一样，假如通过`equals`方法比较相等，则它们记为同一对象，因此通过`compareTo()`方法返回0，只能存放一个对象，集合不会让第二个元素进去。同样，如果添加了可变对象，并且还修改了对象的`实例变量`，将导致集合中对象的顺序变化，然而`TreeSet`不会调整顺序(甚至会导致删除对象失败，TreeSet性能降低)。

##### 2.定制排序 #####

实现定制排序则可以通过`Comparator`接口，该接口内包含一个`int compare(T o1,T o2)`方法，用于比较o1、o2的大小，如果返回正整数，则o1>o2；若返回0，则o1=o2；若返回负整数，则o1<o2。但依然不可以添加不同类型的对象。

在实现定制排序之前，需要提供一个`Comparator`对象与`TreeSet`集合关联，由该对象对集合元素进行排序。

class M{ 
        int age;
        public M(int age){ 
            this.age = age;
        }
        public String toString(){ 
            return "M(age:" + age +" )";
        }
    }
    public class Test{ 
        public static void main(String[] args){ //Lambda表达式
            TreeSet t = new TreeSet((o1,o2)->{ //o1,02这里没有具体类型
                M m1 = (M)o1;
                M m2 = (M)o2;
                return m1.age>m2.age ? -1:m1.age<m2.age ? 1:0;
            });
            t.add(new M(5));
            t.add(new M(-3));
            t.add(new M(9));
            System.out.println(t);
        }//Lambda表达式实现了Comparator类型的对象
    }//输出[M(age:9),M(age:5),M(age:-3)]降序排列

#### EnumSet类 ####

专门为枚举类设计的集合类，`EnumSet`中所有元素必须是指定枚举类型的枚举值。值得一提的是`EnumSet`集合也是有序的，但它以枚举值在类中的定义顺序来决定集合元素的顺序。`EnumSet`在内部以位向量的形式储存元素，因此占用内存非常小，运行效率很好，特别是在批量操作时。

`EnumSet`不允许加入`null`元素，如果试图插入将会抛出`NullPointerException`异常。而如果只是判断集合中是否有`null`元素或删除它，将不会抛出异常，删除的话会返回`false`，因为没有`null`元素。

`EnumSet`集合没有给出任何构造器来创建对象，但还是提供了一些方法去创建的对象的。如下：

*  EnumSet allOf(Class elementType)：创建一个包含指定枚举类所有枚举值的集合
 *  EnumSet complementOf(EnumSet s)：创建一个其元素类型与指定EnumSet里元素类型相同的EnumSet集合，新集合包含原集合不包含的、此枚举类剩下的枚举值
 *  EnumSet copyOf(Collection c)：使用一个普通集合来创建`EnumSet`类
 *  EnumSet copyOf(EnumSet e)：创建一个与指定`EnumSet`具有相同类型、相同元素的EnumSet集合
 *  EnumSet noneOf(Class elementType)：创建一个元素类型为指定枚举类型的空EnumSet
 *  EnumSet range(E from ,E to)：创建一个包含从from枚举值到to枚举值范围内枚举值的EnumSet集合
 *  EnumSet of(E first…E rest )：创建一个包含一个或多个枚举值的EnumSet集合(传入的枚举值必须属于同一个枚举类)

enum Colors{ WHITE,YELLOW,RED,GREEN}
    public class Test{ 
        public static void main(String[] args){ 
            EnumSet e1 = EnumSet.allOf(Colors.class);
            EnumSet e2 = EnumSet.noneOf(Colors.class);//这里为[]
            e2.add(Colors.WHITE);//这里为[WHITE]
            EnumSet e3 = EnumSet.of(Colors.RED,Colors.GREEN);
            System.out.println(e3);//输出[RED,GREEN]
            EnumSet e4 = EnumSet.range(Colors.YELLOW,Colors.GREEN);
            System.out.println(e4);
            //[YELLOW,RED,GREEN]
            EnumSet e5 = EnumSet.complementOf(e4);
            //这里为[WHITE]
        }
    }

此外还可以复制另一个`EnumSet`集合中的元素来创建新集合，或者复制一个`Collection`集合元素来创建新的EnumSet集合。当复制`Collection`集合元素创建时，要求元素都来自**同一个枚举类**，否则抛出`ClassCastException`异常。

Collection c = new HashSet();
    c.clear();
    c.add(Colors.RED);
    c.add(Colors.YELLOW);
    EnumSet e = EnumSet.copyOf(c);
    System.out.println(e);
    //[RED,YELLOW]

#### 各Set实现类的性能分析 ####

`HashSet`总是比`TreeSet`的性能好，主要体现在添加、查询元素上，因为`TreeSet`采用了红黑树来维护集合的次序。而`HashSet`的子类`LinkedHashSet`对插入、查询操作比父类要稍慢些，这是由于采用了链表维护的缘故，造成了额外开销。但这并不影响`LinkedHashSet`发挥威力，然而这恰恰是它的优势，在遍历等批量操作上，`LinkedHashSet`更快。

`EnumSet`是所有Set类中性能最好的，缺点是只能保存一个枚举类的枚举值。总的说，Set的这三个实现类都是线程不安全的，即当有多个线程访问时，如果修改了Set集合，将不能同步，必须手动保证同步。方法是在创建Set集合时，通过`Collections`工具类的`sychronizedXxx()`方法来包装该集合(之后会提到)。