设计哈希集合

发表于
本文字数： 3.4k 阅读时长 ≈ 3 分钟

LeetCode每日一题，705. Design HashSet

先看题目描述

6ajSEj.png

大意就是不用语言内置的哈希表库实现一个哈希集数据结构

算法和思路

实现哈希集合这一数据结构，主要需要解决：

  • 哈希函数：能够将集合中任意可能的元素映射到一个固定范围的整数值，并将该元素存储到整数值对应的地址上
  • 冲突处理：由于不同元素可能映射到相同的整数值，因此需要在整数值出现冲突时，进行冲突处理。有以下几种策略：
    • 链地址法：为每个哈希值维护一个链表，并将具有相同哈希值的元素都放入这一链表当中
    • 开放地址法：当发现哈希值 h 处产生冲突时，根据某种策略，从 h 处出发找到下一个不冲突的位置
    • 再哈希法：当发生哈希冲突后，使用另一个哈希函数产生一个新的地址
  • 扩容：当哈希表元素过多时，冲突的概率将越来越大，而在哈希表中查询一个元素的效率也会越来越低。因此，需要开辟一块更大的空间，来缓解哈希表中发生的冲突

算法源码

由于题目限定了添加的 key 范围为 0 - 10的6次方，因此可以创建一个长度为 10的6次方 + 1 的整型数组 data，直接将 key 存到 data[key] 中即可，所以使用的哈希函数实际上就是 x -> x，不会发生哈希冲突。类的初始化方式都是使用的饿汉式加载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MyHashSet {
    int[] data = new int[(int)1e6 + 1];

    /** Initialize your data structure here. */
    public MyHashSet() {
        data[0] = -1;
    }

    public void add(int key) {
        if (data[key] == key) {
            return;
        }
        data[key] = key;
    }

    public void remove(int key) {
        data[key] = -1;
    }

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        return data[key] == key;
    }
}

后来发现可以使用长度为 10 的 6 次方 + 1 的布尔数组，data[i] 为 true 就代表哈希集中有该值，否则没有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MyHashSet {
    boolean[] map = new boolean[(int)1e6 + 1];

    /** Initialize your data structure here. */
    public MyHashSet() {
        
    }

    public void add(int key) {
        map[key] = true;
    }

    public void remove(int key) {
        map[key] = false;
    }

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        return map[key];
    }
}

下面是题解使用的代码，哈希函数采用的是对素数取模的方法，哈希冲突处理的方法是链地址法，为每个哈希值维护一个链表，将具有相同哈希值的元素存入该链表中。代码如下，由于 Iterator 接口中有 remove() 方法但是没有定义 add() 方法，于是在该哈希集数据结构的 add() 方法中使用的是继承 Iterator 接口的 ListIterator 接口，其中额外定义了 add() 方法，previous() 方法和 hasPrevious() 方法等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class MyHashSet {
    private static final int BASE = 769;
    private LinkedList[] data;

    /** Initialize your data structure here. */
    public MyHashSet() {
        data = new LinkedList[BASE];
        for (int i = 0; i < BASE; ++i) {
            data[i] = new LinkedList<Integer>();
        }
    }

    public void add(int key) {
        int h = hash(key);
        ListIterator<Integer> iterator = data[h].listIterator();
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            if (element == key) {
                return;
            }
        }
        iterator.add(key);
    }

    public void remove(int key) {
        int h = hash(key);
        Iterator<Integer> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            if (element == key) {
                iterator.remove();
                return;
            }
        }
    }

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        int h = hash(key);
        Iterator<Integer> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            if (element == key) {
                return true;
            }
        }
        return false;
    }

    private static int hash(int key) {
        return key % BASE;
    }
}