跳至主要內容

 

labuladong原创约 912 字大约 3 分钟

我讲解前面每种数据结构时,都会把原理和代码实现分到两篇文章里讲解,而这里讲哈希集合时,把原理和实现同时放在本文讲解,且本章节只有本文一篇文章,你有没有觉得奇怪?

哈哈,因为哈希集合没什么好讲的,它就是把前文讲的哈希表简单封装了一下:哈希表的键,其实就是哈希集合

这么一句话就可以讲完了,不过我们还是稍微具体讲一下,照顾一下哈希集合的面子。

哈希集合原理

哈希集合的主要使用场景是「去重」,因为它的特性是:不会出现重复元素,可以在 O(1) 的时间增删元素,可以在 O(1) 的时间判断一个元素是否存在

哈希集合的主要 API 如下:

class HashSet {
    // 增,向哈希集合中添加一个元素,复杂度 O(1)
    // 如果元素已存在,则什么都不会发生
    public void add(int key);

    // 删,从哈希集合中移除一个元素,复杂度 O(1)
    // 如果元素不存在,则什么都不会发生
    public void remove(int key);

    // 查,判断元素是否存在,复杂度 O(1)
    public boolean contains(int key);
}

这几个 API 咋实现?其实根本用不着实现,直接把前文教给你的哈希表拿来用就行了。

你往哈希表里插入一个键值对 put(key, value),时间复杂度是 O(1);你往哈希表里删除一个键值对 remove(key),时间复杂度是 O(1);判断一个键是否存在哈希表中,就是判断 get(key) 是否得到空指针 null,所以时间复杂度也是 O(1)

综上,这几个哈希集合的 API 可以直接复用哈希表的 API 来实现。操作哈希集合,其实就是操作哈希表的键

那就有读者问了,哈希表里面的值呢,如何处理?答案是不处理,直接忽略掉就行了,我们可以用一个占位符来填充值,等会看代码实现你就懂了。

虽然只是简单封装了哈希表,但是大部分高级编程语言还是提供哈希集合的数据结构的,比如 Python 的 set,Java 的 HashSet,C++ 的 unordered_set 等等。但是像 Go 语言,标准库干脆就不提供哈希集合这种数据结构,你要用的话需要自己用哈希表 map 来模拟。

重要

因为哈希集合的元素就是哈希表里面的键,所以哈希集合和哈希表具有相同的限制,比如不能依赖哈希集合的元素遍历顺序、哈希集合中的元素应该是不可变的等等,具体限制和原因可以回顾前文 哈希表特性及原理

哈希集合代码实现

有了上面的铺垫,代码实现应该没有任何难度了。因为太简单了,我就只给出一个 Java 实现,其他语言可以自行使用标准库提供的哈希表,或者我们前文动手实现的哈希表来封装哈希集合:

import java.util.HashMap;

public class MyHashSet<K> {
    // 随便创建一个值,作为 value 占位符
    private static final Object PRESENT = new Object();
    // 底层 HashMap,我这里直接用标准库了,你用前文自己实现的哈希表也可以
    private final HashMap<K, Object> map = new HashMap<>();

    public void add(K key) {
        // 向哈希表添加一个键值对
        map.put(key, PRESENT);
    }

    public void remove(K key) {
        // 从哈希表中移除键 key
        map.remove(key);
    }

    public boolean contains(K key) {
        // 判断哈希表中是否包含键 key
        return map.containsKey(key);
    }

    public int size() {
        return map.size();
    }
}
上次编辑于: