Java集合(五)：Set集

怼烎@ 2022-07-29 11:38 218阅读 0赞

在上一讲中介绍了散列映射表HashMap和树映射表TreeMap，知道了HashMap的底层实现机制。这一讲将介绍Set接口和实现类：HashSet和TreeSet。由于HashSet的实现是基于HashMap的，TreeSet的实现是基于TreeMap的，所以这里不做过多底层的讨论，毕竟这部分已经在[Java集合(四)：Map映射][Java_Map]中讨论过了。

1 散列表与Set接口

链表和数组可以按照人们的意愿排列元素的顺序。但是，如果想要查看某个指定的元素，但却忘了它的位置，就需要访问所有的元素，直到找到为止。如果集合中的元素很多，将会消耗很长时间。如果不在意元素的顺序，可以有几种能够快速查找元素的数据结构。但是缺点是不能控制元素的顺序。它们将按照有利于其操作目的的原则组织数据。

有一种常见的数据结构，就是散列表（hash table）。散列表可以根据每个对象计算一个整数，称为散列码（hash code）。不同的对象产生不同的散列码。

在Java中，散列表用链表数组实现。每个列表称为桶，这个已经在Map映射中介绍了。

散列表的特点就是：元素没有顺序，元素不能重复。

Set接口的定义如下：

public interface java.util.Set<E> extends java.util.Collection<E> {
      public abstract int size();
      public abstract boolean isEmpty();
      public abstract boolean contains(java.lang.Object);
      public abstract java.util.Iterator<E> iterator();
      public abstract java.lang.Object[] toArray();
      public abstract <T> T[] toArray(T[]);
      public abstract boolean add(E);
      public abstract boolean remove(java.lang.Object);
      public abstract boolean containsAll(java.util.Collection<?>);
      public abstract boolean addAll(java.util.Collection<? extends E>);
      public abstract boolean retainAll(java.util.Collection<?>);
      public abstract boolean removeAll(java.util.Collection<?>);
      public abstract void clear();
      public abstract boolean equals(java.lang.Object);
      public abstract int hashCode();
      public java.util.Spliterator<E> spliterator();
    }

这些方法的含义也很简单。

2 HashSet类

Java集合类库中提供了HashSet类实现了Set接口。这个类的底层是使用HashMap实现的：

private transient HashMap<E,Object> map;
    
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

我们知道，HashMap是一个键值对，而HashSet存储的不是键值对，因此为了使用HashMap存储HashSet的元素，就需要构造一个键值对。可以使用需要存储在HashSet中的元素作为键，而上面的PRESENT作为值，就构成了一个键值对，这样就可以存在HashMap中了。

也就是说，HashSet与HashMap的原理一样，不同的是HashSet的值都一样，都是PRESENT。

由于在前一节中已经详细介绍了HashMap的原理，这里不再叙述了。只说一下HashSet的使用。

下面的代码从System.in中读取单词，然后将它们添加到HashSet中，再打印出所有的单词。由于HashSet中不存储相同的元素，所以打印出来的单词是不重复的。运行这个程序时使用下面的命令行：

java SetTest < alice.txt

这样就把alice.txt作为输入，程序就会读取所有的单词。代码如下：

import java.util.*;
    
    public class SetTest
    {
       public static void main(String[] args)
       {
          Set<String> words = new HashSet<>(); // HashSet implements Set
          long totalTime = 0;
    
          Scanner in = new Scanner(System.in);
          while (in.hasNext())
          {
             String word = in.next();
             long callTime = System.currentTimeMillis();
             words.add(word);
             callTime = System.currentTimeMillis() - callTime;
             totalTime += callTime;
          }
    
          Iterator<String> iter = words.iterator();
          for (int i = 1; i <= 20 && iter.hasNext(); i++)
             System.out.println(iter.next());
          System.out.println(". . .");
          System.out.println(words.size() + " distinct words. " + totalTime + " milliseconds.");
       }
    }

结果如下：

![20160416114056965][]

可以看见，一共有5392个不同的单词。

3 TreeSet类

TreeSet和HashSet类似，不过，它比HashSet有所改进。TreeSet是一个有序集合，可以以任意顺序将元素插入到集合中。在对集合进行遍历时，每个值将自动按照排序后的顺序呈现。例如，假设插入三个字符串，然后访问添加的所有元素：

SortedSet<String> sorter=new TreeSet<>();
    sorter.add("B");
    sorter.add("A");
    sorter.add("C");
    for(String s:sorter)System.out.println(s);

结果是：A B C

TreeSet的底层是使用TreeMap实现的，是一个红黑树。每次添加一个元素到树中时，都被放置在正确的排序位置上。因此，迭代器总是以排好序的顺序访问每个元素。

将一个元素添加到树中要比添加到一个散列表中要慢，但是，与将元素添加到数组中或链表中要快。如果树中一共有n个元素，将元素插入到正确位置的时间为logn。

与TreeMap一样，构造一个TreeSet也需要一个比较器，可以使用默认的比较器，也可以使用自己的比较器。使用自己的比较器时，需要给TreeSet的构造器传递一个Comparator对象。

下面的程序创建了两个Item对象的树集。第一个按照部件编号排序，这是Item对象的默认顺序。第二个通过使用一个定制的比较器来按照描述信息排序：

import java.util.*;
    
    
    public class TreeSetTest
    {  
       public static void main(String[] args)
       {  
          SortedSet<Item> parts = new TreeSet<>();
          parts.add(new Item("Toaster", 1234));
          parts.add(new Item("Widget", 4562));
          parts.add(new Item("Modem", 9912));
          System.out.println(parts);
    
          SortedSet<Item> sortByDescription = new TreeSet<>(new
             Comparator<Item>()
             {  
                public int compare(Item a, Item b)
                {  
                   String descrA = a.getDescription();
                   String descrB = b.getDescription();
                   return descrA.compareTo(descrB);
                }
             });
    
          sortByDescription.addAll(parts);
          System.out.println(sortByDescription);
       }
    }

import java.util.*;
    
    /**
     * An item with a description and a part number.
     */
    public class Item implements Comparable<Item>
    {
       private String description;
       private int partNumber;
    
       /**
        * Constructs an item.
        * 
        * @param aDescription
        *           the item's description
        * @param aPartNumber
        *           the item's part number
        */
       public Item(String aDescription, int aPartNumber)
       {
          description = aDescription;
          partNumber = aPartNumber;
       }
    
       /**
        * Gets the description of this item.
        * 
        * @return the description
        */
       public String getDescription()
       {
          return description;
       }
    
       public String toString()
       {
    
          return "[\n\tdescripion=" + description + ",\n\tpartNumber=" + partNumber +"\n]\n";
       }
    
       public boolean equals(Object otherObject)
       {
          if (this == otherObject) return true;
          if (otherObject == null) return false;
          if (getClass() != otherObject.getClass()) return false;
          Item other = (Item) otherObject;
          return Objects.equals(description, other.description) && partNumber == other.partNumber;
       }
    
       public int hashCode()
       {
          return Objects.hash(description, partNumber);
       }
    
       public int compareTo(Item other)
       {
          return Integer.compare(partNumber, other.partNumber);
       }
    }

结果如下：

![20160416140244096][]

[Java_Map]: http://blog.csdn.net/u012877472/article/details/51149450
[20160416114056965]: /images/20220724/3442fb618eb349df9f0f4d5a95277ec0.png
[20160416140244096]: /images/20220724/ac3d263a446e4b33a1b0342ab2a47bda.png

发表评论取消回复

表情：

评论列表（有 0 条评论，218人围观）

还没有评论，来说两句吧...

相关阅读

相关 java——集合——Set集合——LinkedHashSet集合

![95ab2c694c7a502e0b4d3c2e5f39c1bb.png][] > LinkedHashSet集合 java.util.LinkedHashSet集合

约定不等于承诺〃/ 2024年03月31日 09:42/ 0 赞/ 201 阅读

相关 JAVA面向对象学习——java集合———Set——Set集合

import java.util.HashSet; import java.util.Iterator; import java.util.Set; public cla

冷不防/ 2023年09月30日 10:18/ 0 赞/ 77 阅读

相关 Java集合：Set

Set集合，我们常见的Set有HashSet，TreeSet，LinkedHashSet，我们先来看下HashSet。一、HashSet 成员变量：成员变量只有可怜

分手后的思念是犯贱/ 2022年12月03日 09:18/ 0 赞/ 238 阅读

相关 STL Set 交集合集差集

set是关联容器。其键值就是实值，实值就是键值，不可以有重复，所以我们不能通过set的迭代器来改变set的元素的值，set拥有和list相同的特性：当对他进行插入和删除操作的时

女爷i/ 2022年08月24日 11:37/ 0 赞/ 256 阅读

相关 Java集合(五)：Set集

在上一讲中介绍了散列映射表HashMap和树映射表TreeMap，知道了HashMap的底层实现机制。这一讲将介绍Set接口和实现类：HashSet和TreeSet。由于Has

怼烎@/ 2022年07月29日 11:38/ 0 赞/ 219 阅读

相关 java 集合Set

Set集合： package zxy.list; import java.util.HashSet; import java.util.Set; import j

古城微笑少年丶/ 2022年06月15日 07:27/ 0 赞/ 297 阅读

相关【Java集合】Set

继续Java集合类的总结学习，上篇博客总结的List类，本篇博客总结的是Set类。一. Set的定义 Set集合类似于一个罐子，”丢进”Set集合里的多个对

迷南。/ 2022年05月18日 07:23/ 0 赞/ 294 阅读

相关 java集合——Set

set是无序(无下标)，不允许重复的测试类： package com.ysu.test; import java.util.HashSet;

灰太狼/ 2022年05月17日 03:46/ 0 赞/ 301 阅读

相关 java-Set集合

83.set集合的概述 -概述：一个不包含重复元素的collection，set集合的方法与collection集合的方法一样，没有特有的方法，主要研究它的子类。 -特点：

桃扇骨/ 2022年01月28日 10:15/ 0 赞/ 411 阅读

相关【Java】set集合

set集合作为Collection集合的一个子类，其特点== 1）无序，不可重复 2）无索引。== 在所有构造方法以及 add、equals 和 hashCode 方

叁歲伎倆/ 2021年11月01日 13:36/ 0 赞/ 467 阅读