容器深入研究--Set和存储顺序

Leefs 2020-01-15 AM 2067℃ 0条

# 容器深入研究--Set和存储顺序

### 前言

本篇讲述《Java编程思想》第17.6小节，Set和存储顺序。

### 1. 示例

对Set中的`TreeSet`、`HashSet`、`LinkedHashSet`功能进行比较

**代码**

```java
public class SetTest {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(6);
        list.add(4);
        list.add(3);
        list.add(7);
        list.add(8);
        list.add(1);
        list.add(8);
        list.add(4);
        Set<Integer> treeSet = new TreeSet<Integer>(list);
        Set<Integer> hashSet = new HashSet<Integer>(list);
        Set<Integer> linkedHashSet = new LinkedHashSet<Integer>(list);
        System.out.println("原始顺序：");
        Iterator iterator = list.iterator();
        while(iterator.hasNext()){
            System.out.print(iterator.next()+"、");
        }
        System.out.println();
        System.out.println("treeSet顺序：");
        Iterator iteratorTreeSet = treeSet.iterator();
        while(iteratorTreeSet.hasNext()){
            System.out.print(iteratorTreeSet.next()+"、");
        }
        System.out.println();
        System.out.println("hashSet顺序：");
        Iterator iteratorHashSet = hashSet.iterator();
        while(iteratorHashSet.hasNext()){
            System.out.print(iteratorHashSet.next()+"、");
        }
        System.out.println();
        System.out.println("LinkedHashSet顺序");
        Iterator iteratorLinkedHashSet = linkedHashSet.iterator();
        while(iteratorLinkedHashSet.hasNext()){
            System.out.print(iteratorLinkedHashSet.next()+"、");
        }
    }
}
```

> 运行结果

```java
原始顺序：
6、4、3、7、8、1、8、4、
treeSet顺序：
1、3、4、6、7、8、
hashSet顺序：
1、3、4、6、7、8、
LinkedHashSet顺序
6、4、3、7、8、1、
```

Set可以完成去重操作，其中`LinkedHashSet`可以保留顺序、`TreeSet`和`HashSet` 不可以保留顺序

因为`LinkedHashSet`底层是链表实现的，是Set集合中唯一一个能保证怎么存就怎么取的集合对象，因为是`HashSet`的子类,所以也是保证元素唯一的,与`HashSet`的原理一样。

### 2. 概述

在java中使用set容器存储时，除非是使用了诸如Integer和String 的java预定义的类型，这些类型是被设计可以在容器内部使用的。当我们自己创建类型时，我们需要怎么样的形式来维护存储顺序呢？其实在不同的Set实现是具有不同的行为，所以对于在特定的Set实现中，放置的类型也有不同的要求：

| **类型**      | **规定**                                                     |
| ------------- | ------------------------------------------------------------ |
| Set           | 存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。 |
| HashSet       | 为快速查找而设计的Set。存入HashSet的元素必须定义hashCode()   |
| TreeSet       | 保存次序的Set、底层为树结构。使用它可以从Set中提取有序的序列。元素必须实现Comparable接口 |
| LinkedHashSet | 具有HashSet的查询速度，且内部使用链表维护元素的顺序（插入的顺序）。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。元素也必须定义hashCode()方法 |

下面的实例演示为了成功使用特定的Set实现类型而必须定义的方法：

```java
class SetType{
    int i;
    public SetType(int i){
        this.i = i;
    }
    // 重写 equals方法
    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 i) {
        super(i);
    }
    //定义hashCode
    public  int hashCode(){
        return i;
    }
}
//有序Set
class TreeType extends SetType implements Comparable<TreeType>{

public TreeType(int i) {
        super(i);
    }
    @Override
    public int compareTo(TreeType treeType) {
        //不建议使用i-i2 因为很可能溢出
        return treeType.i<i?-1:(treeType.i==i?0:1);
    }
}

public class TypeOfSets {
    static <T> Set<T> fill(Set<T> set, Class<T> type){
        for(int i=0;i<10;i++){
            try {
                set.add(type.getConstructor(int.class).newInstance(i));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        return set;
    }
    static <T> void test(Set<T> set,Class<T> type){
        fill(set,type);
        fill(set,type);
        fill(set,type);
        System.out.println(set);
    }
    public static void main(String[] args) {
        //先走我们自定义的hashCode，如果set中有重复哈希值，那么再走equals方法
        test(new HashSet<HashType>(),HashType.class);
        //先走我们自定义的hashCode，如果set中有重复哈希值，那么再走equals方法
        test(new LinkedHashSet<HashType>(),HashType.class);
        // 此处我定义为降序
        test(new TreeSet<TreeType>(),TreeType.class);
        // 大家思考此处为什么会有重复值呢?toString的话
        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 {
            //报异常 SetType cannot be cast to java.lang.Comparable
            test(new TreeSet<SetType>(),SetType.class);
        }catch (Exception e){
            System.out.println(e.getMessage());
        }
        try {
            //报异常 SetType cannot be cast to java.lang.Comparable
            test(new TreeSet<HashType>(),HashType.class);
        }catch (Exception e){
            System.out.println(e.getMessage());
        }
    }
}
```

> 运行结果

```java
[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, 0, 7, 6, 9, 3, 4, 6, 0, 0, 8, 7, 1, 1, 8, 5, 5, 3, 2, 4, 1, 3, 6, 4, 9, 2, 5, 2, 9, 8]
[7, 5, 6, 4, 3, 9, 0, 8, 1, 5, 8, 1, 0, 7, 6, 2, 5, 0, 4, 3, 1, 9, 2, 7, 6, 9, 4, 8, 2, 3]
[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: SetType cannot be cast to java.lang.Comparable
```

为了证明哪些方法是对于某种特殊的Set是必须的，同时也为了避免代码重复，我们创建了三个类型。

> + 基类SetType只存储了一个int，并且通过toString()方法产生它的值。因为所有在Set中存储的类型都必须具有equals()方法，因此在基类中也有该方法。
> + HashSetType继承自SetType，并添加了hashCode()方法，该方法对于放入Set的散列实现中的对象来说是必需的。
> + TreeType实现了Comparable接口，如果一个对象被用于任何种类的排序容器中，例如TreeSet，那么它必须实现这个接口。

注意：在compareTo()方法中，我没有使用简洁明了的形式return o.i-i，因为这是一个常见的编程错误，它只有在i和i2都是无符号的int（如果Java确实有unsigned关键字的话）才能正常工作。对于有符号的int，它就会出错，因为int不够大，不足以表现两个有符号的int的差。例如o.i是很大的正数而且i是很小的负数时，i-j就会溢出并返回负值，这就不对了。

你通常希望compareTo()产生与equals()一致的自然顺序。如果equals()对于某个特定的比较返回true，那么compareTo()对于该比较就应该返回0，反之亦然。

在TypesForSets中，fill()和test()方法都是用泛型定义的，这是为了避免代码重复。为了验证某个Set的行为，test()会在被测Set上调用三次，尝试着在其中添加重复对象。fill()方法接受任意类型的Set，以及对应类型的Class对象，它使用Class对象来发现构造器并构造对象后添加到Set中。

如果我们尝试着将没有恰当地支持必须操作的类型用于这些方法的Set，那么就会有麻烦了。对于没有重新定义hashCode()方法的SetType或TreeType，如果将它们放置到任何散列表中都会产生重复值，这样就违反了Set的基本约定。这相当烦人，因为这种情况甚至不会有运行时错误。

### 3. SortedSet

SortedSet中的元素可以保证处于排序状态，这使得它可以通过在SortedSet接口的下列方法提供附加的功能：**Comparator comparator（）**返回当前Set使用的Comparator；或者返回null，表示以自然方式排序。

> **Object first():** 返回容器中的第一个元素。
> **Object last():** 返回容器中的最末一个元素。
> SortedSet subSet(fromElement,toElement)生成此Set的子集 范围从 fromElement（包含）,toElement（不包含）
>
> SortedSet HedSet(toElement)生成此Set的子集由小于toElement的元素组成。
> SortedSet HedSet(toElement)生成此Set的子集由小于toElement的元素组成。

**代码**

```java
public class SortedSetDemo {
    public static void main(String[] args) {
        SortedSet<String> sortedSet = new TreeSet<String>();
        Collections.addAll(sortedSet,
                "one two three four five six seven eight"
                        .split(" "));
        System.out.println(sortedSet);
        String low = sortedSet.first();
        String high = sortedSet.last();
        System.out.println(low);
        System.out.println(high);
        Iterator<String> it = sortedSet.iterator();
        for(int i = 0; i <= 6; i++) {
            if(i == 3) low = it.next();
            if(i == 6) high = it.next();
            else it.next();
        }
        System.out.println(low);
        System.out.println(high);
        System.out.println(sortedSet.subSet(low, high));
        System.out.println(sortedSet.headSet(high));
        System.out.println(sortedSet.tailSet(low));
    }
}
```

> 运行结果

```java
[eight, five, four, one, seven, six, three, two]
eight
two
one
two
[one, seven, six, three]
[eight, five, four, one, seven, six, three]
[one, seven, six, three, two]
```

**注意： SortedSet意思是“按对象的比较函数对元素排序 ”，而不是指“元素插入的次序”。插入顺序可以用LinkedHashSet来保存。**

标签: Java, Java编程思想, 容器深入研究

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/432.html

上一篇容器深入研究--List的功能方法

下一篇【转载】MyBatis一次性插入多条数据

容器深入研究--Set和存储顺序

评论已关闭

栏目分类

标签云

友情链接申请

容器深入研究--Set和存储顺序

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请