(41) 剖析HashSet / 计算机程序的思维逻辑

查看历史文章,请点击上方链接关注公众号。

上节介绍了HashMap,提到了Set接口,Map接口的两个方法keySet和entrySet返回的都是Set,本节,我们来看Set接口的一个重要实现类HashSet。

与HashMap类似,字面上看,HashSet由两个单词组成,Hash和Set,Set表示接口,实现Set接口也有多种方式,各有特点,HashSet实现的方式利用了Hash。

下面,我们先来看HashSet的用法,然后看实现原理,最后我们总结分析下HashSet的特点。

用法

Set接口

Set表示的是没有重复元素、且不保证顺序的容器接口,它扩展了Collection,但没有定义任何新的方法,不过,对于其中的一些方法,它有自己的规范。

Set接口的完整定义为:

public interface Set<E> extends Collection<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

与Collection接口中定义的方法是一样的,不过,一些方法有一些不同的规范要求。

添加元素

boolean add(E e);

如果集合中已经存在相同元素了,则不会改变集合,直接返回false,只有不存在时,才会添加,并返回true。

批量添加

boolean addAll(Collection<? extends E> c);

重复的元素不添加,不重复的添加,如果集合有变化,返回true,没变化返回false。

迭代器

Iterator<E> iterator();

迭代遍历时,不要求元素之间有特别的顺序。HashSet的实现就是没有顺序,但有的Set实现可能会有特定的顺序,比如TreeSet,我们后续章节介绍。

HashSet

与HashMap类似,HashSet的构造方法有:

public HashSet()
public HashSet(int initialCapacity)
public HashSet(int initialCapacity, float loadFactor)
public HashSet(Collection<? extends E> c)

initialCapacity和loadFactor的含义与HashMap中的是一样的,待会我们再细看。

HashSet的使用也很简单,比如:

Set<String> set = new HashSet<String>();
set.add("hello");
set.add("world");
set.addAll(Arrays.asList(new String[]{"hello","老马"}));

for(String s : set){
    System.out.print(s+" ");
}

输出为:

hello 老马 world

"hello"被添加了两次,但只会保存一份,输出也没有什么特别的顺序。

hashCode与equals

与HashMap类似,HashSet要求元素重写hashCode和equals方法,且对两个对象,equals相同,则hashCode也必须相同,如果元素是自定义的类,需要注意这一点。

比如说,有一个表示规格的类Spec,有大小和颜色两个属性:

class Spec {
    String size;
    String color;
 
    public Spec(String size, String color) {
        this.size = size;
        this.color = color;
    }

    @Override
    public String toString() {
        return "[size=" + size + ", color=" + color + "]";
    }
}

看一个Spec的Set:

Set<Spec> set = new HashSet<Spec>();
set.add(new Spec("M","red"));
set.add(new Spec("M","red"));

System.out.println(set);

输出为:

[[size=M, color=red], [size=M, color=red]]

同一个规格输出了两次,为避免这一点,需要为Spec重写hashCode和equals方法,利用IDE开发工具往往可以自动生成这两个方法,比如Eclipse中,可以通过"Source"->"Generate hashCode() and equals() ...",我们就不赘述了。

应用场景

HashSet有很多应用场景,比如说:

  • 排重,如果对排重后的元素没有顺序要求,则HashSet可以方便的用于排重。
  • 保存特殊值,Set可以用于保存各种特殊值,程序处理用户请求或数据记录时,根据是否为特殊值,进行特殊处理,比如保存IP地址的黑名单或白名单。
  • 集合运算,使用Set可以方便的进行数学集合中的运算,如交集、并集等运算,这些运算有一些很现实的意义。比如用户标签计算,每个用户都有一些标签,两个用户的标签交集就表示他们的共同特征,交集大小除以并集大小可以表示他们的相似长度。

实现原理

内部组成

HashSet内部是用HashMap实现的,它内部有一个HashMap实例变量,如下所示:

private transient HashMap<E,Object> map;

我们知道,Map有键和值,HashSet相当于只有键,值都是相同的固定值,这个值的定义为:

private static final Object PRESENT = new Object();

理解了这个内部组成,它的实现方法也就比较容易理解了,我们来看下代码。

构造方法

HashSet的构造方法,主要就是调用了对应的HashMap的构造方法,比如:

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

public HashSet() {
    map = new HashMap<>();
}

接受Collection参数的构造方法稍微不一样,代码为:

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

也很容易理解,c.size()/.75f用于计算initialCapacity,0.75f是loadFactor的默认值。

添加元素

我们看add方法的代码:

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

就是调用map的put方法,元素e用于键,值就是那个固定值PRESENT,put返回null表示原来没有对应的键,添加成功了。HashMap中一个键只会保存一份,所以重复添加HashMap不会变化。

检查是否包含元素

代码为:

public boolean contains(Object o) {
    return map.containsKey(o);
}

就是检查map中是否包含对应的键。

删除元素

代码为:

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

就是调用map的remove方法,返回值为PRESENT表示原来有对应的键且删除成功了。

迭代器

代码为:

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

就是返回map的keySet的迭代器。

HashSet特点分析

HashSet实现了Set接口,内部是通过HashMap实现的,这决定了它有如下特点:

  • 没有重复元素
  • 可以高效的添加、删除元素、判断元素是否存在,效率都为O(1)。
  • 没有顺序

如果需求正好符合这些特点,那HashSet就是一个理想的选择。

小结

本节介绍了HashSet的用法和实现原理,它实现了Set接口,不含重复元素,内部实现利用了HashMap,可以方便高效地实现如去重、集合运算等功能。

同HashMap一样,HashSet没有顺序,如果要保持添加的顺序,可以使用HashSet的一个子类LinkedHashSet。Set还有一个重要的实现类,TreeSet,它可以排序。这两个类,我们留待后续章节介绍。

HashMap和HashSet的共同实现机制是哈希表,Map和Set还有一个重要的共同实现机制,树,实现类分别是TreeMap和TreeSet,让我们在接下来的两节中探讨。

原文发布于微信公众号 - 老马说编程(laoma_shuo)

原文发表时间:2016-09-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏电光石火

HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用...

22710
来自专栏TechBox

数据结构与算法之线性表前言线性表

1855
来自专栏Android研究院

数据结构-线性表(顺序表与链表的基本知识 以及ArrayList 源码分析)

比如:美女和野兽,抽象的事物表示美女:头发长 前凸后翘。。。 可以表示为一个数据单元,野兽也是一个数据单元。

2201
来自专栏用户画像

6.2.2 折半查找

折半查找,又称二分查找,它适用于有序的顺序表。基本思路是:首先将给定值key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则...

601
来自专栏Java爬坑系列

【Java入门提高篇】Day28 Java容器类详解(十)LinkedHashMap详解

  今天来介绍一下容器类中的另一个哈希表———》LinkedHashMap。这是HashMap的关门弟子,直接继承了HashMap的衣钵,所以拥有HashMap...

892
来自专栏赵俊的Java专栏

LeetCode 804 Unique Morse Code Words

首先为每个单词的每个字符进行转码, 将转码后的数据放到 Set 集合中, 最后返回 Set 的长度。

1044
来自专栏用户3030674的专栏

Java 工具类—日期获得,随机数,系统命令,数据类型转换

1401
来自专栏自学笔记

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

973
来自专栏desperate633

LintCode 子集题目代码

783
来自专栏用户画像

7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

711

扫码关注云+社区

领取腾讯云代金券