【C++】哈希表模拟：开散列技术与哈希冲突处理

25-03-07 10:22

13365

blog.csdn.net

id="article_content" class="article_content clearfix"> id="content_views" class="markdown_views prism-kimbie-light">

在这里插入图片描述

class="table-box">

C++语法	相关知识点	可以通过点击	以下链接进行学习	一起加油！
命名空间	缺省参数与函数重载	C++相关特性	类和对象-上篇	类和对象-中篇
类和对象-下篇	日期类	C/C++内存管理	模板初阶	String使用
String模拟实现	Vector使用及其模拟实现	List使用及其模拟实现	容器适配器Stack与Queue	Priority Queue与仿函数
模板进阶-模板特化	面向对象三大特性-继承机制	面向对象三大特性-多态机制	STL 树形结构容器	二叉搜索树
AVL树	红黑树	红黑树封装map/set	哈希-开篇	闭散列-模拟实现哈希

在上篇中，我们使用闭散列技术解决了哈希冲突并实现了哈希表。然而，我们发现闭散列并不理想，因此本篇将探讨如何通过开散列方法来处理哈希冲突。

请添加图片描述
Alt
🌈个人主页：是店小二呀
🌈C语言专栏：C语言
🌈C++专栏： C++
🌈初阶数据结构专栏：初阶数据结构
🌈高阶数据结构专栏：高阶数据结构
🌈Linux专栏： Linux

🌈喜欢的诗句:无人扶我青云志我自踏雪至山巅请添加图片描述

class="toc">

一、开散列(哈希桶)

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
在这里插入图片描述

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素

二、实现哈希表

2.1 哈希表基本构架

template<class K>
    struct HashFunc
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };

template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for (auto ch : key)
        {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};
namespace hash_buck
{
    template<class K,class V>
        struct HashNode
        {
            pair<K, V> _kv;
            HashNode<K, V> _next;
        };

    template<class K, class V,class Hash = HashFunc<K>>
        class HashTable
        {
            public:
            typedef HashNode<K, V> Node;
            HashTable()
            {
                _tables.resize(10，nullptr);
            }

            private:
            vector<Node*> _tables;
            //vector> _tables;
            size_t _n = 0;
        };
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

class="hide-preCode-box">

这里如果想实现哈希桶结构，可以使用一个个节点连接起来或者直接套上一个链表容器。这里为了更好地实现迭代器，我们选择第一种方式，第二种方式实现迭代器有一丝麻烦。

开散列中每个桶中放的都是发生哈希冲突的元素，并没有顺序之分。

2.2 哈希表插入数据

bool Insert(const pair<K, V>& kv)
{
    Hash hs;
    size_t hashi = hs(kv.first) % _tables.size();

    //进行头插操作
    Node* newnode = new Node(kv);
    _tables[hashi]->_next = newnode;
    _tables[hashi] = newnode;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

这里链表节点只需要单纯地存储数据，那么只需要设计单链表即可，没有必要设双向链表。对于单链表插入数据，一般推荐采用头插，由于尾插需要找尾比较麻烦。

2.3 哈希表析构函数

这里涉及堆上空间资源的开辟，一般需要涉及析构函数进行资源处理。

由于vector容器元素为内置类型，析构函数对内置类型不进行处理，那么就导致指向空间没有得到释放，需要显式写析构函数，完成资源释放。

~HashTable()
{
    for (size_t i = 0; i < _tables.size(); i++)
    {
        Node* cur = _tables[i];
        while (cur)
        {
            Node* next = cur->_next;
            delete cur;
            cur = next;
        }

    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

2.4 哈希表扩容

由于哈希桶去解决哈希冲突对于哈希表空间需要相对比较小，不同于开发定址法去解决哈希冲突占用表内空间，而是表中一个指针指向一个空间。

【负载因子满足1即可扩容】:_n == _tables.size()

【第一个方案】:复用Insert完成CV操作

//扩容逻辑
    if (_n == _tables.size())
    {
        //这里可以忽略类型
        HashTable NewTable;
        NewTable._tables.resize(n * 10);

        //CV工作
        for (size_t i = 0; i < _tables.size(); i++)
        {
            Node* cur = _tables[i];
            while (cur)
            {
                NewTable.Insert(_tables[i]._kv);
                cur = cur->_next;
            }
        }
        _tables.swap(NewTable);
    }
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

【缺陷】:如果存在一万个节点，意味着需要复制一万个节点又要释放一万个节点，显得很浪费

【第二个方案】:直接将节点拿下来

if (_n == _tables.size())
{
    vector<Node*> NewTable(n * 10, nullptr);

    for (size_t i = 0; i < _tables.size(); i++)
    {
        Node* cur = _tables[i];
        while (cur)
        {
            Node* next = cur->_next;

            cur->_next = _tables[i];
            _tables[i] = cur;
            cur = cur->_next;
        }
        _tables[i] = nullptr;
    }
    _tables.swap(NewTable);
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

关于这段代码是比较难懂，每个指针指向一块空间，先cur->next = newTables[hashi]抓住新表的位置，newTables[hashi] = cur新表将旧表节点拿下来，可以好好理解拿下来的逻辑，得到了这个地址，这个地址指向一块节点。

这里会导致newTables[hashi]和_tables[i]共同指向一块空间，虽然不会去使用旧表去影响到新表，为了保险起见，可以将旧表这块位置指针置空。

2.5 哈希表删除数据

bool Erase(const K& key)
{
    Hash hs;
    size_t hashi = hs(kv.first) % _tables.size();

    Node* cur = _tables[hashi];
    Node* prev = nullptr;

    while (cur)
    {
        if (cur->_kv.first == key)
        {
            if (prev == nullptr)
            {
                _tables[hashi] = cur->_next;
            }
            else
            {
                prev->_next = cur->_next;
            }
            delete cur;

            return true;
        }
        else
        {
            prev = cur;
            cur = cur->_next;
        }
    }
    return false;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">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

这里删除数据，无非需要考虑两种情况的删除，一种是删除第一个节点，另一种是删除其他节点prev->_next = cur->_next。在删除节点需要前后兼顾，保存下前驱指针指向节点。

2.6 哈希桶中查找

Node* Find(const K& key)
{
    Hash hs;
    size_t hashi = hs(kv.first) % _tables.size();
    Node* cur = _tables[hashi];
    while (cur)
    {
        if (cur->_kv.first == key)
        {
            return &cur->_kv.first;
        }
        else
        {
            cur = cur->_next;
        }
    }
    return nullptr;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、HashTable.h

template<class K>
    struct HashFunc
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };

template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for (auto ch : key)
        {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

namespace hash_bucket
{
    template<class K,class V>
        struct HashNode
        {
            pair<K, V> _kv;
            HashNode<K, V> _next;
        };

    template<class K, class V,class Hash = HashFunc<K>>
        class HashTable
        {
            public:
            typedef HashNode<K, V> Node;
            HashTable()
            {
                _tables.resize(10,nullptr);

            }

            ~HashTable()
            {
                for (size_t i = 0; i < _tables.size(); i++)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;
                        delete cur;
                        cur = next;
                    }

                }
            }
            bool Insert(const pair<K, V>& kv)
            {
                Hash hs;
                size_t hashi = hs(kv.first) % _tables.size();

                //扩容逻辑
                //if (_n == _tables.size())
                //{
                //	//这里可以忽略类型
                //	HashTable NewTable;
                //	NewTable._tables.resize(n * 10);
                //	
                //	//CV工作
                //	for (size_t i = 0; i < _tables.size(); i++)
                //	{
                //		Node* cur = _tables[i];
                //		while (cur)
                //		{
                //			NewTable.Insert(_tables[i]._kv);
                //			cur = cur->_next;
                //		}
                //	}
                //	_tables.swap(NewTable);
                //}

                if (_n == _tables.size())
                {
                    vector<Node*> NewTable(n * 10, nullptr);

                    for (size_t i = 0; i < _tables.size(); i++)
                    {
                        Node* cur = _tables[i];
                        while (cur)
                        {
                            Node* next = cur->_next;
                            // 头插新表的位置
                            size_t hashi = hs(kot(cur->_data)) % NewTable.size();
                            cur->_next = NewTable[hashi];
                            NewTable[hashi] = cur;

                            cur = cur->_next;
                        }
                        _tables[i] = nullptr;
                    }
                    _tables.swap(NewTable);
                }

                //进行头插操作
                Node* newnode = new Node(kv);
                _tables[hashi]->_next = newnode;
                _tables[hashi] = newnode;
                ++_n;
            }

            Node* Find(const K& key)
            {
                Hash hs;
                size_t hashi = hs(kv.first) % _tables.size();
                Node* cur = _tables[hashi];
                while (cur)
                {
                    if (cur->_kv.first == key)
                    {
                        return &cur->_kv.first;
                    }
                    else
                    {
                        cur = cur->_next;
                    }
                }
                return nullptr;
            }

            bool Erase(const K& key)
            {
                Hash hs;
                size_t hashi = hs(kv.first) % _tables.size();

                Node* cur = _tables[hashi];
                Node* prev = nullptr;

                while (cur)
                {
                    if (cur->_kv.first == key)
                    {
                        if (prev == nullptr)
                        {
                            _tables[hashi] = cur->_next;
                        }
                        else
                        {
                            prev->_next = cur->_next;
                        }
                        delete cur;

                        return true;
                    }
                    else
                    {
                        prev = cur;
                        cur = cur->_next;
                    }
                }
                return false;
            }
            private:
            vector<Node*> _tables;
            size_t _n = 0;
        };
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二呀C++笔记，希望对你在学习C++语言旅途中有所帮助！

data-report-view="{"mod":"1585297308_001","spm":"1001.2101.3001.6548","dest":"https://blog.csdn.net/2302_79177254/article/details/142729975","extend1":"pc","ab":"new"}">>

注：本文转载自blog.csdn.net的是店小二呀的文章"https://blog.csdn.net/2302_79177254/article/details/142729975"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

/ 登录

评论记录：

未查询到任何数据！