首页 > STL源码剖析 > STL笔记之hashtable

STL笔记之hashtable

之前对hash一直存在恐惧感,毕竟没用过……最近在一个组件里面自己实现了一个hashtable,感觉也就这么回事;回头看看书上对hashtable的分析,发现是极其的相似。不过,旧版本的C++标准里面并没有hashtable这个东西,而C++11中引入了相关的容器(std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap),所以可以直接使用C++11里面的容器了。

1. hashtable结构
SGI STL中hash table使用的是开链法进行的冲突处理,其结构如图所示:
SGI STL hash table结构

hash table的节点定义如下:

template <class _Val>
struct _Hashtable_node
{
  _Hashtable_node* _M_next;
  _Val _M_val;
};

2. hashtable迭代器
这里省略了不必要的代码,只需要注意迭代器类型、成员组成以及几个关键的操作即可。

struct _Hashtable_iterator {
  typedef _Hashtable_node<_Val> _Node;
 
  typedef forward_iterator_tag iterator_category;
 
  _Node* _M_cur;
  _Hashtable* _M_ht;
 
  iterator& operator++();
  iterator operator++(int);
};

hashtable的迭代器类型为ForwardIterator,所以只支持operator++操作。

template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
          class _All>
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++()
{
  // 从当前的节点开始进行遍历操作
  const _Node* __old = _M_cur;
  // 取得下一个节点的指针
  _M_cur = _M_cur->_M_next;
  // 如果为空,表明当前的bucket已经没有节点了,需要指向下一个存在节点的bucket
  if (!_M_cur) {
    // 取得当前的bucket索引值
    size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
    // 寻找下一个存在节点的bucket
    while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
      _M_cur = _M_ht->_M_buckets[__bucket];
  }
  return *this;
}
 
// operator++(int)基于operator++()实现
template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
          class _All>
inline _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int)
{
  iterator __tmp = *this;
  ++*this;
  return __tmp;
}

3. hashtable关键实现
3.1 素数
很多书籍上提到最好取一个素数作为hash表格的大小,但是看了下网上似乎有两种观点:一种赞同,另一种说取其他数也可以。不过都认同的一个观点是,m不应该是进制数的幂,比如十进制的时候,m如果是10^n,那么结果总是和原始值的后n位相关的,这样冲突的概率会更大。所以,CLRS上面也提到了m常常选择与2的幂不太接近的质数。在这种情况下,取一个素数总是个不坏的选择。

SGI STL提供了28个素数最为备选方案,__stl_next_prime可以选出一个最接近n且比n要大的素数。

enum { __stl_num_primes = 28 };
 
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53ul,         97ul,         193ul,       389ul,       769ul,
  1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
  49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
  1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
  50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
  1610612741ul, 3221225473ul, 4294967291ul
};
 
inline unsigned long __stl_next_prime(unsigned long __n)
{
  const unsigned long* __first = __stl_prime_list;
  const unsigned long* __last = __stl_prime_list + (int)__stl_num_primes;
  const unsigned long* pos = lower_bound(__first, __last, __n);
  return pos == __last ? *(__last - 1) : *pos;
}
 
size_type max_bucket_count() const
{
  return __stl_prime_list[(int)__stl_num_primes - 1];
}

3.2 关键源码

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
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
template <class _Val, class _Key, class _HashFcn,
          class _ExtractKey, class _EqualKey, class _Alloc>
class hashtable {
public:
  typedef _Key key_type;
  typedef _Val value_type;
  typedef _HashFcn hasher;
  typedef _EqualKey key_equal;
 
  hasher hash_funct() const { return _M_hash; }
  key_equal key_eq() const { return _M_equals; }
 
private:
  // hash table 节点
  typedef _Hashtable_node<_Val> _Node;
 
private:
  hasher                _M_hash;
  key_equal             _M_equals;
  _ExtractKey           _M_get_key;
  // bucket vector : hash数组本身使用vector进行管理
  vector<_Node*,_Alloc> _M_buckets;
  size_type             _M_num_elements;
 
public:
  hashtable(size_type __n,
            const _HashFcn&    __hf,
            const _EqualKey&   __eql,
            const _ExtractKey& __ext,
            const allocator_type& __a = allocator_type())
    : __HASH_ALLOC_INIT(__a)
      _M_hash(__hf),
      _M_equals(__eql),
      _M_get_key(__ext),
      _M_buckets(__a),
      _M_num_elements(0)
  {
    // 调用_M_initialize_buckets进行初始化操作
    _M_initialize_buckets(__n);
  }
 
  hashtable(size_type __n,
            const _HashFcn&    __hf,
            const _EqualKey&   __eql,
            const allocator_type& __a = allocator_type())
    : __HASH_ALLOC_INIT(__a)
      _M_hash(__hf),
      _M_equals(__eql),
      _M_get_key(_ExtractKey()),
      _M_buckets(__a),
      _M_num_elements(0)
  {
    _M_initialize_buckets(__n);
  }
 
  hashtable(const hashtable& __ht)
    : __HASH_ALLOC_INIT(__ht.get_allocator())
      _M_hash(__ht._M_hash),
      _M_equals(__ht._M_equals),
      _M_get_key(__ht._M_get_key),
      _M_buckets(__ht.get_allocator()),
      _M_num_elements(0)
  {
    _M_copy_from(__ht);
  }
 
  ~hashtable() { clear(); }
 
  size_type size() const { return _M_num_elements; }
  size_type max_size() const { return size_type(-1); }
  bool empty() const { return size() == 0; }
 
  // begin() 返回第一个有效的节点,不存在则返回end()
  iterator begin()
  {
    for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
      if (_M_buckets[__n])
        return iterator(_M_buckets[__n], this);
    return end();
  }
 
  iterator end() { return iterator(0, this); }
 
public:
 
  size_type bucket_count() const { return _M_buckets.size(); }
 
  // 返回hash数组中指定bucket下标上冲突链表的长度
  size_type elems_in_bucket(size_type __bucket) const
  {
    size_type __result = 0;
    for (_Node* __cur = _M_buckets[__bucket]; __cur; __cur = __cur->_M_next)
      __result += 1;
    return __result;
  }
 
  // 插入操作
  pair<iterator, bool> insert_unique(const value_type& __obj)
  {
    resize(_M_num_elements + 1);
    return insert_unique_noresize(__obj);
  }
 
  iterator insert_equal(const value_type& __obj)
  {
    resize(_M_num_elements + 1);
    return insert_equal_noresize(__obj);
  }
 
  pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
  iterator insert_equal_noresize(const value_type& __obj);
 
  // 查找指定的key
  iterator find(const key_type& __key)
  {
    // 计算key得到的下标
    size_type __n = _M_bkt_num_key(__key);
    // 遍历冲突链表
    _Node* __first;
    for ( __first = _M_buckets[__n];
          __first && !_M_equals(_M_get_key(__first->_M_val), __key);
          __first = __first->_M_next)
      {}
    return iterator(__first, this);
  }
 
  // 计算具有指定key的节点的个数
  size_type count(const key_type& __key) const
  {
    const size_type __n = _M_bkt_num_key(__key);
    size_type __result = 0;
 
    for (const _Node* __cur = _M_buckets[__n]; __cur; __cur = __cur->_M_next)
      if (_M_equals(_M_get_key(__cur->_M_val), __key))
        ++__result;
    return __result;
  }
 
private:
  // 计算hash表格的大小(取素数表中的合适的素数)
  size_type _M_next_size(size_type __n) const
    { return __stl_next_prime(__n); }
 
  // 初始化hash数组
  void _M_initialize_buckets(size_type __n)
  {
    const size_type __n_buckets = _M_next_size(__n);
    _M_buckets.reserve(__n_buckets);
    _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
    _M_num_elements = 0;  // 实际节点个数
  }
 
  // 计算下标的几组函数
  size_type _M_bkt_num_key(const key_type& __key) const
  {
    return _M_bkt_num_key(__key, _M_buckets.size());
  }
 
  size_type _M_bkt_num(const value_type& __obj) const
  {
    return _M_bkt_num_key(_M_get_key(__obj));
  }
 
  size_type _M_bkt_num_key(const key_type& __key, size_t __n) const
  {
    return _M_hash(__key) % __n;
  }
 
  size_type _M_bkt_num(const value_type& __obj, size_t __n) const
  {
    return _M_bkt_num_key(_M_get_key(__obj), __n);
  }
 
  // 内存管理:分配新节点
  _Node* _M_new_node(const value_type& __obj)
  {
    _Node* __n = _M_get_node();
    __n->_M_next = 0;
    __STL_TRY {
      construct(&__n->_M_val, __obj);
      return __n;
    }
    __STL_UNWIND(_M_put_node(__n));
  }
 
  // 内存管理:节点回收
  void _M_delete_node(_Node* __n)
  {
    destroy(&__n->_M_val);
    _M_put_node(__n);
  }
};
 
// 插入操作,不允许重复
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool>
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  ::insert_unique_noresize(const value_type& __obj)
{
  const size_type __n = _M_bkt_num(__obj);
  _Node* __first = _M_buckets[__n];
 
  // 如果已经存在则直接返回
  for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
    if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
      return pair<iterator, bool>(iterator(__cur, this), false);
 
  // 插入新节点
  _Node* __tmp = _M_new_node(__obj);
  __tmp->_M_next = __first;
  _M_buckets[__n] = __tmp;
  ++_M_num_elements;
  return pair<iterator, bool>(iterator(__tmp, this), true);
}
 
// 插入操作,允许重复
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  ::insert_equal_noresize(const value_type& __obj)
{
  const size_type __n = _M_bkt_num(__obj);
  _Node* __first = _M_buckets[__n];
 
  // 如果发现同样的key的节点存在,则插入到这个节点之后
  for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
    if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
      _Node* __tmp = _M_new_node(__obj);
      __tmp->_M_next = __cur->_M_next;
      __cur->_M_next = __tmp;
      ++_M_num_elements;
      return iterator(__tmp, this);
    }
 
  // 否则插入到链表头部
  _Node* __tmp = _M_new_node(__obj);
  __tmp->_M_next = __first;
  _M_buckets[__n] = __tmp;
  ++_M_num_elements;
  return iterator(__tmp, this);
}
 
// 查找或者插入:找到则直接返回,否则进行插入操作
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj)
{
  resize(_M_num_elements + 1);
 
  size_type __n = _M_bkt_num(__obj);
  _Node* __first = _M_buckets[__n];
 
  for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
    if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
      return __cur->_M_val;
 
  _Node* __tmp = _M_new_node(__obj);
  __tmp->_M_next = __first;
  _M_buckets[__n] = __tmp;
  ++_M_num_elements;
  return __tmp->_M_val;
}
 
// 删除指定key的节点
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key)
{
  const size_type __n = _M_bkt_num_key(__key);
  _Node* __first = _M_buckets[__n];
  size_type __erased = 0;
 
  if (__first) {
    _Node* __cur = __first;
    _Node* __next = __cur->_M_next;
    while (__next) {
      if (_M_equals(_M_get_key(__next->_M_val), __key)) {
        __cur->_M_next = __next->_M_next;
        _M_delete_node(__next);
        __next = __cur->_M_next;
        ++__erased;
        --_M_num_elements;
      }
      else {
        __cur = __next;
        __next = __cur->_M_next;
      }
    }
    if (_M_equals(_M_get_key(__first->_M_val), __key)) {
      _M_buckets[__n] = __first->_M_next;
      _M_delete_node(__first);
      ++__erased;
      --_M_num_elements;
    }
  }
  return __erased;
}
 
// 重新调整表格大小
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  ::resize(size_type __num_elements_hint)
{
  const size_type __old_n = _M_buckets.size();
  // 超过原来表格的大小时才进行调整
  if (__num_elements_hint > __old_n) {
    // 新的表格大小
    const size_type __n = _M_next_size(__num_elements_hint);
    // 在边界情况下可能无法调整(没有更大的素数了)
    if (__n > __old_n) {
      vector<_Node*, _All> __tmp(__n, (_Node*)(0),
                                 _M_buckets.get_allocator());
      __STL_TRY {
        // 填充新的表格
        for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
          _Node* __first = _M_buckets[__bucket];
          while (__first) {
            size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
            _M_buckets[__bucket] = __first->_M_next;
            __first->_M_next = __tmp[__new_bucket];
            __tmp[__new_bucket] = __first;
            __first = _M_buckets[__bucket];
          }
        }
        // 通过swap交换
        _M_buckets.swap(__tmp);
      }
#         ifdef __STL_USE_EXCEPTIONS
      // 异常处理
      catch(...) {
        for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
          while (__tmp[__bucket]) {
            _Node* __next = __tmp[__bucket]->_M_next;
            _M_delete_node(__tmp[__bucket]);
            __tmp[__bucket] = __next;
          }
        }
        throw;
      }
#         endif /* __STL_USE_EXCEPTIONS */
    }
  }
}
 
// 清空hash表
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::clear()
{
  for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
    // 删除每个冲突链表上的所有节点
    _Node* __cur = _M_buckets[__i];
    while (__cur != 0) {
      _Node* __next = __cur->_M_next;
      _M_delete_node(__cur);
      __cur = __next;
    }
    _M_buckets[__i] = 0;
  }
  _M_num_elements = 0;
}

4. unordered_map
C++11标准里面纳入了相关的四个容器:(可以把unordered_map和unordered_multimap当做hashtable来使用)
C++11标准unordered_map
unordered_map很多接口和SGI的hashtable非常相似。不过我并没有用过hashtable,倒是后来用unordered_map用的多一点。例子很多,这里就不说了。

5. swap
在《Effective C++》讲解异常的时候有提到通过swap的方式确保操作要么成功,要么失败。比如如果要修改某一个地方,可以先通过copy构造一个副本,然后对副本进行修改,最后通过swap操作来实现对原始对象的修改。
这一点在上面分析的resize函数中也有很好的体现:

// 重新调整表格大小
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  ::resize(size_type __num_elements_hint)
{
  const size_type __old_n = _M_buckets.size();
  if (__num_elements_hint > __old_n) {
    const size_type __n = _M_next_size(__num_elements_hint);
    if (__n > __old_n) {
      vector<_Node*, _All> __tmp(__n, (_Node*)(0),
                                 _M_buckets.get_allocator());
      // =============================================================
      // 构造临时的hash表tmp
      // =============================================================
      __STL_TRY {
        for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
          _Node* __first = _M_buckets[__bucket];
          while (__first) {
            size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
            _M_buckets[__bucket] = __first->_M_next;
            __first->_M_next = __tmp[__new_bucket];
            __tmp[__new_bucket] = __first;
            __first = _M_buckets[__bucket];
          }
        }
      // =============================================================
      // 通过swap交换
      // =============================================================
        _M_buckets.swap(__tmp);
      }
      // =============================================================
      // 如果出错,则析构tmp中的节点
      // =============================================================
      catch(...) {
        for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
          while (__tmp[__bucket]) {
            _Node* __next = __tmp[__bucket]->_M_next;
            _M_delete_node(__tmp[__bucket]);
            __tmp[__bucket] = __next;
          }
        }
        throw;
      }
    }
  }
}

STL源码剖析笔记系列
1. STL笔记之空间配置器
2. STL笔记之迭代器
3. STL笔记之vector
4. STL笔记之list
5. STL笔记之优先队列
6. STL笔记之deque
7. STL笔记之slist
8. STL笔记之hashtable


觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> STL笔记之hashtable
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 2014年9月4日10:25 | #1

    博主你好,我是林科大的,现在也大四了,看了你的博文略感惭愧,我差不多是今年才开始学习Windows内核相关的知识,看过一些基础的书籍和Windows原理与实现,动手写过hook和过滤驱动,接下来我应该从哪方面开始学习,看些什么书籍呢,还有就是找工作的话,公司对应届生有哪些要求?谢谢!

    [回复]

    代码疯子 回复:

    @AloneMonkey, 对Windows内核这一块,抱歉我也只是接触过一段时间,所以没办法告诉你要从哪方面学习,不过既然你都写过过滤驱动,肯定是对驱动有了基本的了解了,建议你从一些小项目入手学习,《寒江独钓》你可以看看。
    至于找工作,看你要找什么样的工作了。看你现在还在学驱动,估计也想从事这方面的工作吧?如果只是内核模块这一块的话,基本都是安全相关的公司了,你可以看看人家的招聘需求啊,不过校园招聘并没有明确对这一块有要求的;另外你可以看看一些做存储之类的公司,他们也会有这方面的需求。
    个人建议你还是多打打基础吧,校招看中的还是个人的基础与潜力,有经验更好,但不是硬性要求吧。
    当然如果你投递的就是内核相关的岗位,那么这就是你的优势了。(其实只要是Windows相关的开发岗位,你的这些经历都算是一个优势)

    [回复]

  2. 2014年9月4日10:53 | #2

    恩恩,大部分基础的书籍都看过了,寒江独钓、天书夜谈、驱动开发详解等等,我最近也是没怎么写代码,在巩固基础的东西,操作系统方面的,数据结构和算法,感觉这方面涉及的比较多,还有感觉python写脚本很快,要不要学习?如果学习逆向的话,有什么好的学习资料。

    [回复]

    代码疯子 回复:

    @AloneMonkey, 要不要学python?你自己觉得喜欢觉得有用,就“学学学”。学习逆向多动动手吧,看别人的东西不如自己动手去分析。

    [回复]

    AloneMonkey 回复:

    @代码疯子, 恩恩,非常感谢!!!向博主学习!

    [回复]