unordered系列关联式容器

内部是无序的，查询很快

几个函数说明：

函数声明 功能介绍
operator[] 返回与key对应的value值
bucket_count() 返回桶的个数
size_t bucket_size(size_t n)const 返回n号桶有效元素的个数
size_t bucket(const K& key) 返回元素key对应的桶号

底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

概念

通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

例如：数据集合{1，7，6，4，5，9}
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小

哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：

  • 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值
    域必须在0到m-1之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数应该比较简单

除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

字符串哈希算法

字符串哈希算法

解决哈希冲突

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置

线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同
关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降
低

二次探测

每次平方的探测：hash+i^2 (i>=0)

负载因子

负载因子：填入表中元素个数 / 散列表的长度

负载因子越小越不容易冲突，但是空间利用率比较低，一般设置0.7左右

代码

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
namespace CloseHash
{
    enum State
    {
        EXIST,
        DELETE,
        EMPTY
    };
    template <class K, class V>
    struct HashData
    {
        std::pair<K, V> _kv;
        State _state = EMPTY;
    };

    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 val = 0;
            for (auto ch : key)
            {
                val *= 131;
                val += ch;
            }

            return val;
        }
    };

    template <class K, class V, class Hash = HashFunc<K>>
    class HashTable
    {
    public:
        bool insert(const pair<K, V> &data)
        {
            if (find(data.first))
            {
                return false;
            }

            if (_tables.size() == 0 || _size * 10 / _tables.size() >= 7)
            {
                size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                HashTable<K, V, Hash> newHT;
                newHT._tables.resize(newSize);
                for (auto e : _tables)
                {
                    if (e._state == EXIST)
                    {
                        newHT.insert(e._kv);
                    }
                }

                _tables.swap(newHT._tables);
            }

            Hash hash;
            size_t hashi = hash(data.first) % _tables.size();

            while (_tables[hashi]._state == EXIST)
            {
                hashi++;
                hashi %= _tables.size();
            }

            _tables[hashi]._kv = data;
            _tables[hashi]._state = EXIST;
            _size++;

            return true;
        }

        HashData<K, V> *find(const K &key)
        {
            if (_tables.size() == 0)
            {
                return nullptr;
            }
            Hash hash;
            size_t start = hash(key) % _tables.size();
            size_t hashi = start;
            while (_tables[hashi]._state != EMPTY)
            {
                if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
                {
                    return &_tables[hashi];
                }

                hashi++;
                hashi %= _tables.size();

                if (hashi == start)
                {
                    break;
                }
            }

            return nullptr;
        }

        bool erase(const K &key)
        {
            HashData<K, V> *ret = find(key);
            if (ret)
            {
                ret->_state = DELETE;
                --_size;
                return true;
            }
            else
            {
                return false;
            }
        }

        void print()
        {
            for (size_t i = 0; i < _tables.size(); i++)
            {
                if (_tables[i]._state == EXIST)
                {
                    printf("[%llu:%d] ", i, _tables[i]._kv.first);
                }
                else
                {
                    printf("[%llu:*] ", i);
                }
            }
            cout << endl;
        }

    private:
        vector<HashData<K, V>> _tables;
        size_t _size = 0;
    };

    void test1()
    {
        int a[] = {1, 11, 4, 15, 26, 7, 44};
        HashTable<int, int> ht;
        for (auto e : a)
        {
            ht.insert(make_pair(e, e));
        }
        ht.print();

        ht.erase(4);

        cout << ht.find(44)->_kv.first << endl;
        cout << ht.find(4) << endl;
        ht.print();
    }
}

开散列

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

开散列闭散列比较

应用链地址法（开散列）处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

unordered_map和unordered_set封装

hash表（开散列）

几个点：

  • 模板类，第一个模板参数是K，第二个参数T，上层决定这个T是什么
  • 传入仿函数KeyOfT，这个可以从T类型中取K
  • insert插入，返回值设为迭代器和bool的键值对
  • 迭代器（一个是节点指针，一个是哈希表指针）
  • 迭代器用了哈希表，需要在迭代器前面进行哈希表的声明
  • 迭代器有哈希表的指针，所以要将迭代器类，声明为哈希表类的友元
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
#pragma once

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 val = 0;
        for (auto ch : key)
        {
            val *= 131;
            val += ch;
        }

        return val;
    }
};

namespace OpenHash
{

    template <class T>
    struct HashData
    {
        T _data;
        HashData<T> *_next;
        HashData(const T &data)
            : _data(data), _next(nullptr)
        {
        }
    };

    template <class K, class T, class Hash, class KeyOfT>
    class HashTable;

    template <class K, class T, class Hash, class KeyOfT>
    struct __HashIterator
    {
        typedef HashData<T> Node;
        typedef HashTable<K, T, Hash, KeyOfT> HT;
        typedef __HashIterator<K, T, Hash, KeyOfT> self;

        Node *_node;
        HT *_pht;

        __HashIterator(Node *node, HT *pht)
            : _node(node), _pht(pht)
        {
        }

        T &operator*()
        {
            return _node->_data;
        }

        T *operator->()
        {
            return &_node->_data;
        }

        self &operator++()
        {
            if (_node->_next)
            {
                // 如果当前桶的下一个不为空，直接走到下一个位置
                _node = _node->_next;
            }
            else
            {
                // 说明当前位置为空，要找下一个不为空的桶
                Hash hash;
                KeyOfT kot;
                size_t i = hash(kot(_node->_data)) % _pht->size();
                ++i;
                for (; i < _pht->size(); ++i)
                {
                    if (_pht->_tables[i])
                    {
                        _node = _pht->_tables[i];
                        break;
                    }
                }

                if (i == _pht->size())
                {
                    _node = nullptr;
                }
            }

            return *this;
        }

        bool operator!=(const self &s) const
        {
            return _node != s._node;
        }
        bool operator==(const self &s) const
        {
            return _node == s._node;
        }
    };

    template <class K, class T, class Hash, class KeyOfT>
    class HashTable
    {
        friend struct __HashIterator<K,T,Hash,KeyOfT>;

    public:
        typedef HashData<T>
            Node;
        typedef __HashIterator<K, T, Hash, KeyOfT> iterator;

        iterator begin()
        {
            for (size_t i = 0; i < size(); i++)
            {
                if (_tables[i])
                {
                    return iterator(_tables[i], this);
                }
            }

            return end();
        }

        iterator end()
        {
            return iterator(nullptr, this);
        }

        inline size_t __stl_next_prime(size_t n)
        {
            static const size_t __stl_num_primes = 28;
            // 按素数，扩容，stl源码中
            static const size_t __stl_prime_list[__stl_num_primes] =
                {
                    53, 97, 193, 389, 769,
                    1543, 3079, 6151, 12289, 24593,
                    49157, 98317, 196613, 393241, 786433,
                    1572869, 3145739, 6291469, 12582917, 25165843,
                    50331653, 100663319, 201326611, 402653189, 805306457,
                    1610612741, 3221225473, 4294967291};

            for (size_t i = 0; i < __stl_num_primes; ++i)
            {
                if (__stl_prime_list[i] > n)
                {
                    return __stl_prime_list[i];
                }
            }

            return -1;
        }

        ~HashTable()
        {
            for (size_t i = 0; i < _tables.size(); i++)
            {
                Node *cur = _tables[i];
                while (cur)
                {
                    Node *next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
        }
        pair<iterator, bool> insert(const T &data)
        {
            KeyOfT kot;
            Hash hash;

            iterator ret = find(kot(data));

            if (ret != end())
            {
                return make_pair(ret, false);
            }
            if (_tables.size() == _size)
            {
                // size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
                vector<Node *> newTables;
                newTables.resize(__stl_next_prime(_tables.size()), nullptr);
                for (size_t i = 0; i < _tables.size(); i++)
                {
                    Node *cur = _tables[i];
                    while (cur)
                    {
                        Node *next = cur->_next;
                        size_t hashi = hash(kot(cur->_data)) % newTables.size();
                        cur->_next = newTables[hashi];
                        newTables[hashi] = cur;
                        cur = next;
                    }

                    _tables[i] = nullptr;
                }

                _tables.swap(newTables);
            }

            size_t hashi = hash(kot(data)) % _tables.size();
            Node *newNode = new Node(data);
            newNode->_next = _tables[hashi];
            _tables[hashi] = newNode;
            ++_size;

            return make_pair(iterator(newNode, this), true);
        }

        iterator find(const K &key)
        {
            Hash hash;
            KeyOfT kot;
            if (_tables.size() == 0)
                return end();
            size_t hashi = hash(key) % _tables.size();

            Node *cur = _tables[hashi];
            while (cur)
            {
                if (kot(cur->_data) == key)
                {
                    return iterator(cur, this);
                }

                cur = cur->_next;
            }

            return end();
        }

        bool erase(const K &key)
        {
            if (_tables.size() == 0)
            {
                return false;
            }
            Hash hash;
            size_t hashi = hash(key) % _tables.size();

            Node *cur = _tables[hashi];
            Node *parent = nullptr;
            while (cur)
            {
                if (cur->_kv.first == key)
                {
                    // 1、头删
                    // 2、中间删

                    if (parent == nullptr)
                    {
                        _tables[hashi] = cur->_next;
                    }
                    else
                    {
                        parent->_next = cur->_next;
                    }
                    delete cur;

                    return true;
                }
                parent = cur;
                cur = cur->_next;
            }

            return false;
        }

        size_t size()
        {
            return _tables.size();
        }

        // 桶的个数
        size_t bucket_num()
        {
            size_t num = 0;
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                if (_tables[i])
                {
                    ++num;
                }
            }
            return num;
        }

        size_t maxbucket_lenth()
        {
            size_t maxlen = 0;
            for (size_t i = 0; i < size(); i++)
            {
                size_t len = 0;
                Node *cur = _tables[i];
                while (cur)
                {
                    len++;
                    cur = cur->_next;
                }

                if (len > maxlen)
                {
                    maxlen = len;
                }
            }

            return maxlen;
        }

    private:
        vector<Node *> _tables;
        size_t _size = 0;
    };
}

unordered_map

unordered_map的底层是哈希表，第二个模板参数传个pair<K,V>，同时要配对应的仿函数，返回first

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
#pragma once

#include "hash.h"

namespace st
{
    template <class K, class V, class Hash = HashFunc<K>>
    class unordered_map
    {
        struct KeyOfT
        {
            const K &operator()(const pair<K, V> &kv)
            {
                return kv.first;
            }
        };

    public:
        typedef typename OpenHash::HashTable<K, pair<K, V>, Hash, KeyOfT>::iterator iterator;

        iterator begin()
        {
            return _ht.begin();
        }

        iterator end()
        {
            return _ht.end();
        }

        pair<iterator, bool> insert(const pair<K, V> &kv)
        {
            return _ht.insert(kv);
        }

        V &operator[](const K &key)
        {
            pair<iterator, bool> ret = _ht.insert(make_pair(key, V()));
            return ret.first->second;
        }

    private:
        OpenHash::HashTable<K, pair<K, V>, Hash, KeyOfT> _ht;
    };

    void test()
    {
        unordered_map<string, int> countMap;
        string arr[] = {"a", "a", "b", "a", "b", "c", "c", "c", "d", "d", "d"};
        for (auto e : arr)
        {
            countMap[e]++;
        }

        for (auto &kv : countMap)
        {
            cout << kv.first << ":" << kv.second << endl;
        }
    }
}

unordered_set

unordered_set的底层也是哈希表，第二个模板参数传个K，同时要配对应的仿函数，返回K就好了

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
#pragma once

#include "hash.h"

namespace st
{
    template <class K, class Hash = HashFunc<K>>
    class unordered_set
    {
        struct KeyOfT
        {
            const K &operator()(const K& key)
            {
                return key;
            }
        };

    public:
        typedef typename OpenHash::HashTable<K, K, Hash, KeyOfT>::iterator iterator;

        iterator begin()
        {
            return _ht.begin();
        }

        iterator end()
        {
            return _ht.end();
        }

        pair<iterator, bool> insert(const K& key)
        {
            return _ht.insert(key);
        }

    private:
        OpenHash::HashTable<K, K, Hash, KeyOfT> _ht;
    };

    void test_set()
    {
        unordered_set<string> s;
        string arr[] = {"a", "a", "b", "a", "b", "c", "c", "c", "d", "d", "d"};
        for(auto e: arr)
        {
            s.insert(e);
        }

        for(auto e: s)
        {
            cout << e << endl;
        }
    }
}