HashSet、LinkedHashSet和TreeSet需要的元素类型

野性酷女 2023-06-18 10:53 7阅读 0赞

根据三种Set的性质，这里先给出它们需要的元素类型，之后再用例子进行佐证：

*  HashSet是一种哈希容器，所以元素类型如果重写了equals方法，那么也必须重写hashCode方法。
 *  LinkedHashSet本质也是一种哈希容器，只不过加了链表来维护元素的插入顺序。同样的，元素类型如果重写了equals方法，那么也必须重写hashCode方法。
 *  TreeSet不是一种哈希容器，它内部使用二叉树结构来保存元素的升序或降序。所以它对元素类型的要求是需实现Comparable接口。

本文例子来自Java编程思想——17.6Set和存储顺序——TypesForSets类。

import java.util.*;
    
    class SetType { 
        int i;
        public SetType(int n) {  i = n; }
        public boolean equals(Object o) { 
            return o instanceof SetType && (i == ((SetType)o).i);
        }
        public String toString() {  return Integer.toString(i); }
    }
    
    class HashType extends SetType { 
        public HashType(int n) {  super(n); }
        public int hashCode() {  return i; }
    }
    
    class TreeType extends SetType implements Comparable<TreeType> { 
        public TreeType(int n) {  super(n); }
        public int compareTo(TreeType arg) { 
            return (arg.i < i ? -1 : (arg.i == i ? 0 : 1));
        }
    }
    
    public class TypesForSets { 
        static <T> Set<T> fill(Set<T> set, Class<T> type) { 
            try { 
                for(int i = 0; i < 10; i++)
                    set.add(type.getConstructor(int.class).newInstance(i));
            } catch(Exception e) { 
                throw new RuntimeException(e);
            }
            return set;
        }
        static <T> void test(Set<T> set, Class<T> type) { 
            fill(set, type);
            fill(set, type); // Try to add duplicates
            fill(set, type);
            for(T t:set){ 
                System.out.print(t+" ");
            }
            System.out.println();
        }
        public static void main(String[] args) { 
            test(new HashSet<HashType>(), HashType.class);
            test(new LinkedHashSet<HashType>(), HashType.class);
            test(new TreeSet<TreeType>(), TreeType.class);
            // Things that don't work:
            test(new HashSet<SetType>(), SetType.class);
            test(new HashSet<TreeType>(), TreeType.class);
            test(new LinkedHashSet<SetType>(), SetType.class);
            test(new LinkedHashSet<TreeType>(), TreeType.class);
            try { 
                test(new TreeSet<SetType>(), SetType.class);
            } catch(Exception e) { 
                System.out.println(e.getMessage());
            }
            try { 
                test(new TreeSet<HashType>(), HashType.class);
            } catch(Exception e) { 
                System.out.println(e.getMessage());
            }
        }
    } /* Output: (这是我的机器的运行结果，其中第4、5排打印结果和书中不一样，因为同一个java程序产生出来的hashcode可能不一样的) 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0 7 7 0 8 5 9 4 1 1 3 2 3 1 9 2 8 4 6 5 4 6 8 0 3 7 5 0 6 2 9 2 6 1 7 1 4 0 0 9 9 9 4 7 8 0 3 8 8 7 6 3 5 5 1 6 2 2 4 3 5 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 java.lang.ClassCastException: SetType cannot be cast to java.lang.Comparable java.lang.ClassCastException: HashType cannot be cast to java.lang.Comparable *///:~

*  SetType作为一种基本的元素类型。它重写了equals，让其在和其他SetType对象equals比较时，就比较它们的成员变量就行。SetType不能放入哈希容器中，否则将产生错误的结果。
 *  HashType继承了SetType，并重写了hashCode方法。重写的hashCode逻辑用到了成员变量`i`，同样的，父类SetType的equals逻辑也用到了成员变量`i`，所以说，这样的重写才是标准的。HashType可以放入哈希容器中。
 *  TreeType继承了SetType并实现了Comparable接口。TreeType不能放入哈希容器中，否则将产生错误的结果。
 *  `fill`是一个静态的泛型方法。`set.add(type.getConstructor(int.class).newInstance(i))`这里通过传入的Class对象获得其参数类型为int的构造器，然后给构造器传参循环变量`i`。所以这个方法会循环10次，分别将0到9传参给有参构造器，并将新对象添加到set中。
 *  `test`是一个静态的泛型方法。它将执行`fill`方法三次。

接下来说说TreeType对Comparable接口的实现：

*  实现上来说，`arg.i < i ? -1 : (arg.i == i ? 0 : 1)`这句会让TreeSet排降序，因为当参数的`i`比自身的`i`大时，compareTo会返回一个大于0的值（这里也就是1，正值即代表this对象会排到arg对象的后面去），这样，插入时更大的元素将会插入到前面去。
 *  之所以没有简单地用`arg.i - i`（这样看起来好像，当参数的`i`比自身的`i`大时，也会产生一个大于0的值），是因为java里的数值类型全是有符号类型，当`arg.i`是一个很大的正数而`i`是一个很大的负数时，此时就会溢出而产生负值（本来应该返回正值的）。虽然实现看起来有点麻烦，但由于没有用到`-`号而只是用到`< =`，所以不会溢出的。

分析一下打印结果：

*  `test(new HashSet<HashType>(), HashType.class);`的打印结果是`0 1 2 3 4 5 6 7 8 9`。因为HashType重写了hashCode方法，当有重复元素加入时，重复的元素调用hashCode返回的hash值和已加入的元素调用hashCode返回的hash值一样，此时会将已加入的元素和重复的元素用equals进行比较，再执行相应的策略（替换已有、保持不变）。所以，打印结果里没有重复的元素。
 *  `test(new LinkedHashSet<HashType>(), HashType.class);`的打印结果是`0 1 2 3 4 5 6 7 8 9`。同上，因为LinkedHashSet本质上也是HashSet，只是它用链表保持了元素插入时顺序。
 *  `test(new TreeSet<TreeType>(), TreeType.class);`的打印结果是`0 1 2 3 4 5 6 7 8 9`。在元素加入TreeSet时，只会依靠compareTo方法，不会依靠equals方法。如果原有元素和新增元素的compareTo的结果为0，那么原有元素保持不变。所以，打印结果里没有重复的元素。
 *  `test(new HashSet<SetType>(), SetType.class);`。从打印结果看，重复元素不会被检测到，因为SetType没有重写hashCode，这将会使用到native的hashCode方法，这样的话，所有的元素的hash值都不一样，然后所有的元素都会被放到不同的hash桶里。
 *  `test(new HashSet<TreeType>(), TreeType.class);`。同上。
 *  `test(new LinkedHashSet<SetType>(), SetType.class);`和`test(new LinkedHashSet<TreeType>(), TreeType.class);`同上，不能检测到重复元素。但它能保持元素插入时的顺序。
 *  剩下两个抛出异常很正常，因为元素类型没有实现Comparable接口。