算法数据结构

【模板】哈希集合

字数统计: 2.6k字   |   阅读时长: 12分
, ,

摘要: 开散列表与闭散列表的哈希集合，代码模板

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们实现哈希集合的代码模板，开散列和闭散列两种处理冲突的方式均有实现。

之后再 705. 设计哈希集合 上测试代码模板，并应代码模板解决 1074. 元素和为目标值的子矩阵数量。

$1 哈希函数

(1) 取余

1
2
3
4
int hash1(const HashType& x) const
{
    return (key(x) + INF) % sizetable;
}

(2) 相乘取整

首先用关键字key乘上某个常数A(0 < A < 1)，并抽取出 key.A 的小数部分；然后用sizetable乘以该小数后取整。

Knuth 建议选取：

1
2
3
4
5
int hash2(const HashType& x) const
{
    double d = key(x) * A;
    return (int)(sizetable * (d - (int)d));
}

$2 哈希冲突

(1) 闭散列

线性探测

1
pos = (pos + 1) % sizetable;

平方探测

1
pos = (pos + i * i) % sizetable;

闭散列的缺点：

  • 容易产生堆积问题。
  • 需要额外的字段表示节点状态，记录数据是被删除的而不是空白的。下次查找的时候继续向后走。

参考：线性探测解决哈希冲突

(2) 开散列

在哈希表每一个节点持有一个链表，某个数据项对的关键字还是像通常一样映射到哈希表的节点中，而数据项本身插入到节点持有的链表中。发生冲突时，在链表后面追加数据。

开散列的缺点：

  • 存储的记录是随机分布在内存中的，这样在查询记录时，相比结构紧凑的数据类型，哈希表的跳转访问会带来额外的时间开销。

参考: 邻接表

(3) 再散列

多准备哈希函数，冲突了就换，但是有可能依然冲突。

$3 重哈希 (rehash)

原理

1
装填因子 load factor = 关键字个数 / 表长

当装填因子不断增大，插入元素的效率越来越低下，甚至导致失败，所以有了 rehashing 操作。

  • 对于闭散列表，装填因子变大之后线性探测容易形成主集团，二次探测容易形成次集团。重哈希后稀释集团效应，减少探测次数，此外之前标记删除的节点在重哈希时真正删除。
  • 对于开散列表，装填因子变大之后链表的长度会变长。重哈希后桶数增加，链表长度减小。

将原来的散列表扩大 2 倍，然后再将旧表中的元素，一个个插入到新表中。

可以查询大于原表长 2 倍的最小素数。

触发时机

依赖工程经验，比较基础的方法有以下几种：

  • 当插入失败时进行此操作。
  • 当装填因子达到某个临界值时进行此操作，常见的临界值是 1/2。

可重集合实现方式

对于集合，如果需要 key 可以重复。有两种直观的思路

(1) 在节点上单独维护一个 key 的次数的字段

  • 闭散列表：直接用 state 表示就可以，不用额外开变量
  • 开散列表：增加一个 cnt 字段表示次数

(2) 对于开散列表，在桶里找到相同 key 的节点后，在其前面插入新节点，相同 key 总是链表上连续的一段。这也是 STL 实现可重哈希集合unordered_multiset的方式。

模板中使用的是第一种方式。

$4 代码模板

闭散列表 (无重/可重集合)

以下内容可以根据实际情况修改。

  • 哈希函数
  • 哈希冲突时的探测方法
  • 重哈希，时机和新表长的选法

模板中为取余和乘法两种哈希函数 + 线性探测

模板中有针对多重集合的情况定义重哈希，但是没有使用。

把 key 的次数表示到节点状态里，不增加额外字段实现可重集合。

节点持有 key 和 state，状态定义: 0: 空, -1: 被删, >0: 有效，表示净插入次数

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
const int INF = 1e9;
typedef int HashType;
int defaultKey(const HashType &k)
{
    return k;
}


class CloseHashTable
{
private:
    struct Node
    {
        HashType data;
        int state;
        // 0: Empty  -1: deleted
        // >0: cnt / active
        Node()
        {
            state = 0;
        }
    };

    Node *arraytable;
    int sizetable;
    int (*key)(const HashType& x); // 将 key 变成一个整数，如果 key 本身是整数直接返回
    const double A = 0.6180339887;

    int hash1(const HashType& x) const
    {
        if(key(x) < 0)
            return key(x) % sizetable;
        return (key(x) + INF) % sizetable;
    }

    int hash2(const HashType& x) const
    {
        double d;
        if(key(x) < 0)
            d = (key(x) + INF) * A;
        else
            d = (key(x)) * A;
        return (int)(sizetable * (d - (int)d));
    }

public:
    CloseHashTable(int length=20011, int (*f)(const HashType &x) = defaultKey)
    {
        sizetable = length;
        arraytable = new Node[sizetable];
        key = f;
    }

    ~CloseHashTable()
    {
        delete [] arraytable;
    }

    int findx(const HashType &x) const;
    bool insertx(const HashType &x);
    bool removex(const HashType &x);
    void rehash();
};

int CloseHashTable::findx(const HashType &x) const
{
    int initPos = hash2(x);
    int pos = initPos;

    do
    {
        if(arraytable[pos].state == 0)
            return 0;
        if(arraytable[pos].state > 0 && arraytable[pos].data == x)
            return arraytable[pos].state;
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return 0;
}

bool CloseHashTable::insertx(const HashType &x)
{
    int initPos = hash2(x);
    int pos = initPos;

    do{
        if(arraytable[pos].state <= 0)
        {
            arraytable[pos].data = x;
            arraytable[pos].state = 1;
            return true;
        }
        else if(arraytable[pos].state > 0 && arraytable[pos].data == x)
        {
            // 无重集合改为直接返回 true
            ++arraytable[pos].state;
            return true;
        }
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return false;
}

bool CloseHashTable::removex(const HashType &x)
{
    int initPos = hash2(x);
    int pos = initPos;

    do
    {
        if(arraytable[pos].state == 0)
            return false;
        if(arraytable[pos].state > 0 && arraytable[pos].data == x)
        {
            // 无重集合改为将 arraytable[pos].state 改为 -1 后返回
            --arraytable[pos].state;
            if(arraytable[pos].state == 0)
                arraytable[pos].state = -1;
            return true;
        }
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return false;
}

void CloseHashTable::rehash()
{
    Node *tmp = arraytable;
    arraytable = new Node[sizetable * 2];

    for(int i = 0; i < sizetable; ++i)
    {
        if(tmp[i].state > 0)
        {
            for(int j = 0; i < tmp[j].state; ++j)
                insertx(tmp[i].data);
        }
    }
    sizetable *= 2;

    delete [] tmp;
}

开散列表 (无重/可重集合)

模板中为取余和乘法两种哈希函数，没有重哈希。

增加额外字段 cnt 表示 key 的次数。如果是无重集合，去掉 cnt 字段即可。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
typedef int HashType;
const int INF = 1e9;
int defaultKey(const int &k)
{
    return k;
}


class OpenHashTable
{
private:
    struct Node
    {
        HashType data;
        int cnt;
        Node *next;
        Node(const HashType &x)
        {
            data = x;
            cnt = 1;
            next = nullptr;
        }
        Node()
        {
            cnt = 0;
            next = nullptr;
        }
    };

    Node **arraytable;
    int sizetable;
    int (*key)(const HashType &x);
    const double A = 0.6180339887;

    int hash1(const HashType& x) const
    {
        if(key(x) < 0)
            return (key(x) + INF) % sizetable;
        return key(x) % sizetable;
    }

    int hash2(const HashType& x) const
    {
        double d;
        if(key(x) < 0)
            d = (key(x) + INF) * A;
        else
            d = (key(x)) * A;
        return (int)(sizetable * (d - (int)d));
    }

public:
    OpenHashTable(int length = 20011, int (*f)(const HashType &x) = defaultKey)
    {
        sizetable = length;
        arraytable = new Node*[sizetable];
        key = f;
        for(int i = 0; i < sizetable; ++i)
        {
            arraytable[i] = new Node;
        }
    }

    ~OpenHashTable()
    {
        Node *p,*q;
        for(int i = 0; i < sizetable; ++i)
        {
            p = arraytable[i];
            // 头删
            do
            {
                q = p -> next;
                delete p;
                p = q;
            }while(p != nullptr);
        }
        delete [] arraytable;
    }

    int findx(const HashType &x) const
    {
        int pos = hash2(x);
        Node *p = arraytable[pos];
        while(p -> next != nullptr && (p -> next -> data != x))
            p = p -> next;
        if(p -> next != nullptr)
            return p -> next -> cnt;
        else
            return 0;
    }

    bool insertx(const HashType &x)
    {
        int pos = hash2(x);
        Node *p = arraytable[pos] -> next;
        while(p != nullptr && p -> data != x)
            p = p -> next;
        // 没找到就头插
        if(p == nullptr)
        {
            p = new Node(x);
            p -> next = arraytable[pos] -> next;
            arraytable[pos] -> next = p;
            return true;
        }
        else
        {
            // 如果是无重集合，把这个分支去掉，找到了直接返回 false
            ++(p -> cnt);
            return true;
        }
        return false;
    }

    bool removex(const HashType &x)
    {
        int pos = hash2(x);
        Node *p = arraytable[pos];
        Node *q;
        while(p -> next != nullptr && p -> next -> data != x)
            p = p -> next;
        if(p -> next == nullptr)
            return false;
        else
        {
            // 如果是无重集合，直接删 p -> next 即可
            --(p -> next -> cnt);
            if(p -> next -> cnt == 0)
            {
                q = p -> next;
                p -> next = q -> next;
                delete q;
            }
            return true;
        }
    }
};

$5 代码测试

用散列表模板 (无重集合)。

1
2
开散列表 : OpenHashTable *table;
闭散列表 : CloseHashTable *table;

两种模板代码一样。

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
class MyHashSet {
public:
    /** Initialize your data structure here. */
    MyHashSet() {
        table = new OpenHashTable(N);
    }

    ~MyHashSet()
    {
        delete table;
        table = nullptr;
    }

    void add(int key) {
        table -> insertx(key);
    }

    void remove(int key) {
        table -> removex(key);
    }

    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        return table -> findx(key);
    }

private:
    const int N = 20011;
    OpenHashTable *table;
};

$6 应用：1074. 元素和为目标值的子矩阵数量

1. unordered_map

unordered_map 有时会触发扩容消耗时间。812ms，参考文章 力扣1074-元素和为目标值的子矩阵数量。

哈希表被卡常的时候可以尝试用哈希表模板，可以提前算好需要开出的空间一次开出，避免一些扩容操作。

2. CloseHashTable

定义 reset() 函数，将数组里的数据清空，但是不重开数组。

1
2
3
4
5
void reset()
{
    for(int i = 0; i < sizetable; ++i)
        arraytable[i].state = 0;
}

用模板 CloseHashTable，表长提前根据数据量算好，设为 613，不触发扩容且控制表长， 160ms。

3. OpenHashTable

定义 reset() 函数，将桶里的数据清空，但是不重新开桶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void OpenHashTable::reset()
{
    Node *p,*q;
    for(int i = 0; i < sizetable; ++i)
    {
        p = arraytable[i];
        // 头删
        while(p -> next != nullptr)
        {
            q = p -> next;
            p -> next = q -> next;
            delete q;
        }
    }
}

桶的个数度依然设为 613。492ms。

代码 (C++)

开散列表和闭散列表除了变量定义不一样之外，其他代码均一样。

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
54
class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return 0;
        int n = matrix.size();
        int m = matrix[0].size();

        sums2d = vector<vector<int> >(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                sums2d[i][j] = sums2d[i][j - 1] + sums2d[i - 1][j]
                    - sums2d[i - 1][j - 1] + matrix[i - 1][j - 1];

        mapping = new OpenHashTable(613);
        int ans = 0;
        for(int i = 0; i < n; ++i)
            for(int l = 0; l <= i; ++l)
            {
                vector<int> nums(m);
                for(int j = 0; j < m; ++j)
                    nums[j] = sum_region(l, j, i, j);
                ans += solve1d(nums, target);
            }
        return ans;
    }

private:
    vector<vector<int>> sums2d;
    OpenHashTable *mapping;

    int solve1d(const vector<int>& nums, const int target)
    {
        int m = nums.size();
        mapping -> reset();
        mapping -> insertx(0);
        int sum = 0;
        int ans = 0;
        for(int j = 0; j < m; ++j)
        {
            sum += nums[j];
            int gap = sum - target;
            ans += mapping -> findx(gap);
            mapping -> insertx(sum);
        }
        return ans;
    }

    int sum_region(int row1, int col1, int row2, int col2)
    {
        // row1 <= row2, col1 <= col2
        return sums2d[row2 + 1][col2 + 1] - sums2d[row2 + 1][col1]
            - sums2d[row1][col2 + 1] + sums2d[row1][col1];
    }
};
Share