欢迎您来到芯片的主页!

Welcome to Chipset's homepage!

拉链哈希表unordered_xxx

写过单数组和双数组哈希表的设计,再来个拉链哈希凑数。

拉链哈希是最常用的一种哈希表,也是多数C++标准库实现unordered_xxx时最常用的数据结构。
由于每个节点都是动态创建的,因此除了分配内存的时间开销,每块内存还有metadata,对于存储小对象来说,很不划算,但是比较适合存储大的数据结构,例如字符窜。存储整数的示意图如下。


实现哈希表最简单的做法就是用std::vector和std::forward_list做组合。为了看清楚原理,这里单独来做,为了实现简单,没有迭代器。
下面有代码了,懒得多解释了。
  1 // hash_function.hpp
  2 
  3 #pragma once
  4 
  5 #include <string>
  6 #include <cstring>
  7 
  8 namespace Sample
  9 {
 10 
 11 template <typename K> struct hash {};
 12 
 13 // please change this hash function prior to usage
 14 inline unsigned long hash_string(const char* s)
 15 {
 16   unsigned long h = 0;
 17   for(; *s; ++s)
 18     h = (h << 5U+ h + *s; // h = h * 33 + *s;
 19 
 20   return h;
 21 }
 22 
 23 template <>
 24 struct hash<char*>
 25 {
 26   unsigned long operator()(const char* s) const { return hash_string(s); }
 27 };
 28 
 29 template <>
 30 struct hash<const char*>
 31 {
 32   unsigned long operator()(const char* s) const { return hash_string(s); }
 33 };
 34 
 35 // this hash algorithm comes from glib, GPL V3 license
 36 template <>
 37 struct hash<std::string>
 38 {
 39   unsigned long operator()(const std::string& s) const
 40   {
 41     unsigned long seed = 0xc70f6907UL;
 42     unsigned long len = s.size();
 43     const unsigned long m = 0x5bd1e995UL;
 44     unsigned long h = seed ^ len;
 45     const char* buf = s.c_str();
 46 
 47     // Mix 4 bytes at a time into the hash.
 48     while(len >= 4U)
 49     {
 50       unsigned long k;
 51       std::memcpy(&k, buf, sizeof(k));
 52       k *= m;
 53       k ^= k >> 24U;
 54       k *= m;
 55       h *= m;
 56       h ^= k;
 57       buf += 4U;
 58       len -= 4U;
 59     }
 60 
 61     // Handle the last few bytes of the input array.
 62     switch(len)
 63     {
 64       case 3U: h ^= static_cast<unsigned char>(buf[2U]) << 16U;
 65       case 2U: h ^= static_cast<unsigned char>(buf[1U]) << 8U;
 66       case 1U: h ^= static_cast<unsigned char>(buf[0]);
 67       h *= m;
 68     };
 69 
 70     // Do a few final mixes of the hash.
 71     h ^= h >> 13U;
 72     h *= m;
 73     h ^= h >> 15U;
 74     return h;
 75   }
 76 };
 77 
 78 template <>
 79 struct hash<const std::string>
 80 {
 81   unsigned long operator()(const std::string& s) const { return hash_string(s.c_str()); }
 82 };
 83 
 84 template <>
 85 struct hash<void*>
 86 {
 87   unsigned long operator()(void* p) const
 88   {
 89     union
 90     {
 91       unsigned long ul;
 92       void* ptr;
 93     };
 94     ptr = p;
 95     return ul;
 96   }
 97 };
 98 
 99 template <>
100 struct hash<const void*>
101 {
102   unsigned long operator()(const void* p) const
103   {
104     union
105     {
106       unsigned long ul;
107       const void* ptr;
108     };
109     ptr = p;
110     return ul;
111   }
112 };
113 
114 #ifndef MANY_COLLISIONS
115 
116 template <>
117 struct hash<char>
118 {
119   unsigned char operator()(char x) const { return static_cast<unsigned char>(x); }
120 };
121 
122 template <>
123 struct hash<unsigned char>
124 {
125   unsigned char operator()(unsigned char x) const { return x; }
126 };
127 
128 template <>
129 struct hash<signed char>
130 {
131   unsigned char operator()(signed char x) const { return static_cast<unsigned char>(x); }
132 };
133 
134 template <>
135 struct hash<short>
136 {
137   unsigned short operator()(short x) const { return static_cast<unsigned short>(x); }
138 };
139 
140 template <>
141 struct hash<unsigned short>
142 {
143   unsigned short operator()(unsigned short x) const { return x; }
144 };
145 
146 template <>
147 struct hash<int>
148 {
149   unsigned int operator()(int x) const { return static_cast<unsigned int>(x); }
150 };
151 
152 template <>
153 struct hash<unsigned int>
154 {
155   unsigned int operator()(unsigned int x) const { return x; }
156 };
157 
158 template <>
159 struct hash<long>
160 {
161   unsigned long operator()(long x) const { return static_cast<unsigned long>(x); }
162 };
163 
164 template <>
165 struct hash<unsigned long>
166 {
167   unsigned long operator()(unsigned long x) const { return x; }
168 };
169 
170 template <>
171 struct hash<unsigned long long>
172 {
173   unsigned long long operator()(unsigned long long x) const { return x; }
174 };
175 
176 template <>
177 struct hash<long long>
178 {
179   unsigned long long operator()(long long x) const { return static_cast<unsigned long long>(x); }
180 };
181 
182 #else
183 
184 // many collisions? Use these hash objects instead the above
185 template <>
186 struct hash<unsigned long long>
187 {
188   unsigned long long operator()(unsigned long long x) const
189   {
190     x = (~x) + (x << 21U);
191     x = x ^ (x >> 24U);
192     x = (x + (x << 3U)) + (x << 8U);
193     x = x ^ (x >> 14U);
194     x = (x + (x << 2U)) + (x << 4U);
195     x = x ^ (x >> 28U);
196     x = x + (x << 31U);
197     return x;
198   }
199 };
200 
201 template <>
202 struct hash<long long>
203 {
204   unsigned long long operator()(long long x) const
205   {
206     unsigned long long y = static_cast<unsigned long long>(x);
207     y = (~y) + (y << 21U);
208     y = y ^ (y >> 24U);
209     y = (y + (y << 3U)) + (y << 8U);
210     y = y ^ (y >> 14U);
211     y = (y + (y << 2U)) + (y << 4U);
212     y = y ^ (y >> 28U);
213     y = y + (y << 31U);
214     return y;
215   }
216 };
217 
218 // hash 32 bit integer
219 template <>
220 struct hash<unsigned long>
221 {
222   unsigned long operator()(unsigned long x) const
223   {
224     x ^= (x >> 20U^ (x >> 12U);
225     x ^= (x >> 7U^ (x >> 4U);
226     return x;
227   }
228 };
229 
230 template <>
231 struct hash<long>
232 {
233   unsigned long operator()(long x) const
234   {
235     unsigned long y = static_cast<unsigned long>(x);
236     y ^= (y >> 20U^ (y >> 12U);
237     y ^= (y >> 7U^ (y >> 4U);
238     return y;
239   }
240 };
241 
242 // hash 16 bit integer
243 template <>
244 struct hash<unsigned short>
245 {
246   unsigned short operator()(unsigned short x) const
247   {
248     x ^= (x >> 12U^ (x >> 7U);
249     x ^= (x >> 4U^ (x >> 1U);
250     return x;
251   }
252 };
253 
254 template <>
255 struct hash<short>
256 {
257   unsigned short operator()(short x) const
258   {
259     unsigned short y = static_cast<unsigned short>(x);
260     y ^= (y >> 12U^ (y >> 7U);
261     y ^= (y >> 4U^ (y >> 1U);
262     return y;
263   }
264 };
265 
266 // hash char and unsigned char
267 template <>
268 struct hash<unsigned char>
269 {
270   unsigned char operator()(unsigned char x) const
271   {
272     x ^= (x >> 7U^ (x >> 4U);
273     x ^= (x >> 2U^ (x >> 1U);
274     return x;
275   }
276 };
277 
278 template <>
279 struct hash<signed char>
280 {
281   unsigned char operator()(signed char x) const
282   {
283     unsigned char y = static_cast<unsigned char>(x);
284     y ^= (y >> 7U^ (y >> 4U);
285     y ^= (y >> 2U^ (y >> 1U);
286     return y;
287   }
288 };
289 
290 template <>
291 struct hash<char>
292 {
293   unsigned char operator()(char x) const
294   {
295     unsigned char y = static_cast<unsigned char>(x);
296     y ^= (y >> 7U^ (y >> 4U);
297     y ^= (y >> 2U^ (y >> 1U);
298     return y;
299   }
300 };
301 
302 #endif
303 
304 // Copied from boost library by Chipset with minor changes
305 
306 // Copyright 2005-2009 Daniel James.
307 // Distributed under the Boost Software License, Version 1.0. (See accompanying
308 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
309 
310 // The code blow is not portable even on x86 system
311 
312 inline void hash_float_combine(unsigned long& seed, unsigned long value)
313 {
314   seed ^= value + (seed << 6U+ (seed >> 2U);
315 }
316 
317 template <>
318 struct hash<float>
319 {
320   unsigned long operator ()(float v) const
321   {
322     unsigned long* ptr = (unsigned long*)&v;
323     unsigned long seed = *ptr;
324     return seed;
325   }
326 };
327 
328 template <>
329 struct hash<double>
330 {
331   unsigned long operator ()(double v) const
332   {
333     unsigned long* ptr = (unsigned long*)&v;
334     unsigned long seed = *ptr++;
335     hash_float_combine(seed, *ptr);
336     return seed;
337   }
338 };
339 
340 template <>
341 struct hash<long double>
342 {
343   unsigned long operator ()(long double v) const
344   {
345     unsigned long* ptr = (unsigned long*)&v;
346     unsigned long seed = *ptr++;
347     hash_float_combine(seed, *ptr++);
348     hash_float_combine(seed, *(unsigned short*)ptr);
349     return seed;
350   }
351 };
352 
353 /* namespace Sample */
354 

 1 // hash_functors.hpp
 2 
 3 #pragma once
 4 
 5 #include <cstring>
 6 
 7 namespace Sample
 8 {
 9 
10 template <typename T>
11 struct equal_to
12 {
13   bool operator ()(const T& x, const T& y) const { return x == y; }
14 };
15 
16 template <>
17 struct equal_to<const char*>
18 {
19   bool operator()(const char* x, const char* y) const { return 0 == std::strcmp(x, y); }
20 };
21 
22 template <>
23 struct equal_to<char*>
24 {
25   bool operator()(const char* x, const char* y) const { return 0 == std::strcmp(x, y); }
26 };
27 
28 // select the first item [a pair must be used]
29 template <typename P>
30 struct select1st
31 {
32   const typename P::first_type& operator()(const P& x) const { return x.first; }
33 };
34 
35 // find an argument's original value
36 template <typename T>
37 struct identity
38 {
39   const T& operator () (const T& x) const { return x; }
40 };
41 
42 // namespace Sample
43 

  1 // unordered_impl.hpp
  2 #pragma once
  3 
  4 #include <algorithm>
  5 #include "hash_function.hpp"
  6 #include "hash_functors.hpp"
  7 
  8 namespace Sample
  9 {
 10 
 11 template <typename U>
 12 struct snode
 13 {
 14   // cached and this will avoid recalculating the hash value repeatedly
 15   unsigned long m_value;
 16   // payload, for hash map, a pair of two, for hash set, only one
 17   U m_data;
 18   snode* m_next;
 19   snode(unsigned long = 0const U& = U(), snode* = 0);
 20   bool operator == (const snode&);
 21   bool operator < (const snode&);
 22 };  // struct snode
 23 
 24 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
 25 class unordered_impl
 26 {
 27 public:
 28   typedef K key_type;
 29   typedef V value_type;
 30   typedef value_type* pointer;
 31   typedef const value_type* const_pointer;
 32   typedef value_type& reference;
 33   typedef const value_type& const_reference;
 34   typedef unsigned long size_type;
 35   typedef HF hash_functor;
 36   typedef Compare compare;
 37   typedef KeyOfValue key_of_value;
 38 
 39 protected:
 40   // hash functor
 41   hash_functor m_hf;
 42 
 43   compare cmp;
 44   // to get key
 45   key_of_value kv;
 46 
 47   // buffer size of bucket, always power of 2
 48   size_type cap;
 49 
 50   // how many entries in the hash table?
 51   size_type sz;
 52 
 53   // list headers for real entries
 54   snode<value_type>** bucket;
 55 
 56   // If you need these two funtions, add implementation by yourselft
 57   // and move them into public area
 58   unordered_impl(const unordered_impl&);               // no implementation
 59   unordered_impl& operator = (const unordered_impl&);  // no implementation
 60 
 61   // rounding up to upper power of 2, needs about 12 basic RISC instructions
 62   // somthing like this:
 63   // 1 => 1
 64   // 2, 3, 4 => 4
 65   // 5, 6, 7, 8 => 8
 66   // 9, 10, , 15, 16 => 16
 67   // 17, 18, , 31, 32 => 32
 68   // 
 69   // argument: size_type, a unsigned long typedef, value 'x'
 70   // returned: the nearest number less or equal_to to 'x' but power of 2
 71   // required: 32 bit integers
 72   // it is designed to calculate address easier
 73   size_type power2ceil(size_type);
 74 
 75   // to get key from a data type argument 'x'
 76   const key_type& key(const_reference) const;
 77 
 78   unsigned long key2int(const key_type&const;
 79 
 80   // to get subscript of the buffer
 81   size_type hasher(unsigned longconst;
 82 
 83 public:
 84   // constructor, allocate memory and initialize
 85   // n elements will be stored
 86   // default value val at bucket
 87   // default functor
 88   // default functor to get key
 89   // returned: none
 90   unordered_impl(size_type n,
 91                  const hash_functor& hash_func = hash_functor(),
 92                  const compare& pred = compare(),
 93                  const key_of_value& key_val = key_of_value());
 94 
 95   // argument: none
 96   // returned: none
 97   virtual ~unordered_impl();
 98 
 99   // clear all, not really remove elements, but refill with default items to
100   // override the old one
101   // argument: none
102   // returned: void
103   void clear();
104 
105   // to get the maximum amount of elements a fixed hash table can hold
106   // argument: none
107   // returned: size_type, a unsigned long typedef
108   size_type capacity() const;
109 
110   // Insert an element into hash table, generally very fast, worst case
111   // very slow, fortunately worst case seldom happened
112   // argument: const_reference, a const V& typedef, value 'x'
113   // returned: boolean 'true' means insertion seccess, 'false' failure
114   pointer insert(const_reference);
115 
116   // Erase an element, not really remove that element, only replace it with
117   // the default value. This method accepts a key value as its argument.
118   // argument: const key_type& 'x'
119   // returned: boolean 'true' means erasure success, 'false' means failure
120   bool erase(const key_type&);
121 
122   // generally, find an element will be very fast, but at worst case, the
123   // search will become linear, fortunately, worst case seldom happened
124   // if found the mentioned item, return a pointer pointed to that item,
125   // otherwise return a null pointer 0
126   // argument: const key_type&,  value 'x'
127   // returned: pointer point to the node's ndata if found, otherwise '0'
128   const_pointer find(const key_type&const;
129 
130   // Is the hash table empty?
131   // argument: none
132   // returned: boolean, 'true' means hash table empty, 'false' otherwise
133   bool empty () const;
134 
135   // Is the hash table overpacked?
136   // argument: node
137   // returend: boolean 'true' means hash table full, 'false' otherwise,
138   //           almost always false, unless buffer is overcrowded
139   bool full() const;
140 
141   // How many nodes are filled in the hash table?
142   // argument: none
143   // returned: size_type, a unsigned long typedef
144   size_type size() const;
145 
146   // swap two hash tables
147   // argument: unordered_impl&, value 'fhi' (fhi = fixed hash implementation)
148   // returned: void
149   void swap(unordered_impl&);
150 
151   // the hash table should be allowed to reset its size. If the new_sz is larger
152   // than size(), its size will be reset to new_sz, otherwise, nothing will happen
153   // argument: size_type new_sz
154   // returned: void
155   void resize(size_type);
156 
157   double load_factor() const;
158 }; // unordered_impl
159 
160 ///////////////////////////////////////////////////////////////////////////////////////////////////
161 
162 template <typename U>
163 snode<U>::snode(unsigned long v, const U& d, snode* next) : m_value(v), m_data(d), m_next(next) {}
164 
165 template <typename U>
166 inline bool snode<U>::operator == (const snode& sn)
167 {
168   return m_value == sn.m_value && m_data == sn.m_data;
169 }
170 
171 template <typename U>
172 inline bool snode<U>::operator < (const snode& sn)
173 {
174   return m_data < sn.m_data;
175 }
176 
177 ////////////////////////////////////////////////////////////////////////////////////////////////
178 
179 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
180 inline typename unordered_impl<K, V, HF, Compare, KeyOfValue>::size_type
181 unordered_impl<K, V, HF, Compare, KeyOfValue>::power2ceil(size_type x)
182 {
183   if(0 == (x & (x - 1U)))
184     return x;
185   --x;
186   x = x | (x >> 1U);
187   x = x | (x >> 2U);
188   x = x | (x >> 4U);
189   x = x | (x >> 8U);
190   x = x | (x >> 16U);
191   return ++x;
192 }
193 
194 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
195 inline typename unordered_impl<K, V, HF, Compare, KeyOfValue>::size_type
196 unordered_impl<K, V, HF, Compare, KeyOfValue>::hasher(size_type val) const
197 {
198   return val & (cap - 1U);
199 }
200 
201 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
202 inline typename unordered_impl<K, V, HF, Compare, KeyOfValue>::size_type
203 unordered_impl<K, V, HF, Compare, KeyOfValue>::key2int(const key_type& k) const
204 {
205   return static_cast<size_type>(m_hf(k));
206 }
207 
208 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
209 inline const typename unordered_impl<K, V, HF, Compare, KeyOfValue>::key_type&
210 unordered_impl<K, V, HF, Compare, KeyOfValue>::key(const_reference x) const
211 {
212   return kv(x);
213 }
214 
215 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
216 unordered_impl<K, V, HF, Compare, KeyOfValue>::unordered_impl(
217   size_type n,
218   const hash_functor& hash_func,
219   const compare& pred,
220   const key_of_value& key_val) :
221   m_hf(hash_func),
222   cmp(pred),
223   kv(key_val),
224   cap(power2ceil(n < 2U ? 2U : n)),
225   sz(0),
226   bucket(0)
227 {
228   bucket = new snode<value_type>*[cap]; // new a chunk as buffer
229   std::fill_n(bucket, cap, static_cast<snode<value_type>*>(0));
230 }
231 
232 
233 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
234 unordered_impl<K, V, HF, Compare, KeyOfValue>::~unordered_impl()
235 {
236   clear();
237   delete [] bucket;  // delete newed buffer
238 }
239 
240 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
241 void unordered_impl<K, V, HF, Compare, KeyOfValue>::clear()
242 {
243   for(size_type i = 0; i < cap; ++i)
244     while(0 != bucket[i])
245     {
246       snode<value_type>* p = bucket[i];
247       bucket[i] = bucket[i]->m_next;
248       delete p;
249     }
250   sz = 0;
251 }
252 
253 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
254 typename unordered_impl<K, V, HF, Compare, KeyOfValue>::pointer
255 unordered_impl<K, V, HF, Compare, KeyOfValue>::insert(const_reference x)
256 {
257   const key_type k = key(x);
258 
259   if(sz == cap)
260     resize(sz << 1U);
261 
262   size_type val = key2int(k);
263   // found the entry point
264   size_type idx = hasher(val);
265   snode<value_type>* ptr = bucket[idx];
266 
267   if(0 != ptr)
268   {
269    // try to find if x is in the hash table
270     while((0 != ptr->m_next) && (val != ptr->m_value || !cmp(k, key(ptr->m_data))))
271       ptr = ptr->m_next;
272     // an identical key exists
273     if(val == ptr->m_value && cmp(k, key(ptr->m_data)))
274       return &ptr->m_data;
275   }
276 
277   // construct object at arranged address only
278   snode<value_type>* pn = new snode<value_type>(val, x);
279   // linked the new node
280   ((0 == ptr) ? bucket[idx] : ptr->m_next) = pn;
281   ++sz;
282   return &pn->m_data;
283 }
284 
285 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
286 bool unordered_impl<K, V, HF, Compare, KeyOfValue>::erase(const key_type& x)
287 {
288   size_type val = key2int(x);
289   // found the entry point
290   size_type idx = hasher(val);
291   snode<value_type>* ptr = bucket[idx];
292   if(0 == ptr)
293     return false;
294 
295   // search while moving forward
296   snode<value_type>* prev = ptr;
297   while(0 != ptr->m_next && (val != ptr->m_value || !cmp(x, key(ptr->m_data))))
298   {
299     prev = ptr;
300     ptr = prev->m_next;
301   }
302 
303   // if found x, then delete the corresponding node.
304   if(val == ptr->m_value && cmp(x, key(ptr->m_data)))
305   {
306     // not list head (bucket[idx])?
307     if(prev != ptr)
308       prev->m_next = ptr->m_next;
309     else
310       bucket[idx] = ptr->m_next;
311 
312     delete ptr;
313     --sz;
314 
315     // frequently resize will degrade performance severely! since the bucket
316     // only hold pointers, it should not use too much memory, we'd better avoid
317     // purging it frequently as possible as we can
318     if((sz << 1U+ 1U < cap)
319       resize(sz);
320 
321     return true;
322   }
323   return false;
324 }
325 
326 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
327 typename unordered_impl<K, V, HF, Compare, KeyOfValue>::const_pointer
328 unordered_impl<K, V, HF, Compare, KeyOfValue>::find(const key_type& x) const
329 {
330   size_type val = key2int(x);
331   snode<value_type>* ptr = bucket[hasher(val)];
332   if(0 == ptr)
333     return 0;
334 
335   // linear search, generally it is fast enough, because the path is
336   // extremely short. At worst case, it is very slow.
337   while(0 != ptr->m_next && (val != ptr->m_value || !cmp(x, key(ptr->m_data))))
338     ptr = ptr->m_next;
339 
340   if(val == ptr->m_value && cmp(x, key(ptr->m_data)))
341     return &ptr->m_data;
342   else
343     return 0;
344 }
345 
346 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
347 inline bool unordered_impl<K, V, HF, Compare, KeyOfValue>::empty () const
348 {
349   return 0 == sz;
350 }
351 
352 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
353 inline typename unordered_impl<K, V, HF, Compare, KeyOfValue>::size_type
354 unordered_impl<K, V, HF, Compare, KeyOfValue>::capacity() const
355 {
356   return cap;
357 }
358 
359 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
360 inline typename unordered_impl<K, V, HF, Compare, KeyOfValue>::size_type
361 unordered_impl<K, V, HF, Compare, KeyOfValue>::size() const
362 {
363   return sz;
364 }
365 
366 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
367 inline void unordered_impl<K, V, HF, Compare, KeyOfValue>::swap(unordered_impl& fhi)
368 {
369   std::swap(m_hf, fhi.m_hf);
370   std::swap(cmp, fhi.cmp);
371   std::swap(kv, fhi.kv);
372   std::swap(cap, fhi.cap);
373   std::swap(sz, fhi.sz);
374   std::swap(bucket, fhi.bucket);
375 }
376 
377 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
378 void unordered_impl<K, V, HF, Compare, KeyOfValue>::resize(size_type new_sz)
379 {
380   if(new_sz < sz)  // try to abandon some elements? Never!!
381     return;
382   unordered_impl tmp(new_sz);
383   for(size_type i = 0; i < cap; ++i)
384   {
385     snode<value_type>* ptr = bucket[i];
386     while(0 != ptr) // only rearrange pointers, no objects copied.
387     {
388       bucket[i] = ptr->m_next;
389       size_type idx = tmp.hasher(ptr->m_value);
390       ptr->m_next = tmp.bucket[idx];
391       tmp.bucket[idx] = ptr;
392       ++tmp.sz;
393       --sz;
394       ptr = bucket[i];
395     }
396   }
397   tmp.swap(*this);
398 }
399 
400 template <typename K, typename V, typename HF, typename Compare, typename KeyOfValue>
401 double unordered_impl<K, V, HF, Compare, KeyOfValue>::load_factor() const
402 {
403   size_type n = 0;
404   for(size_type i = 0; i < cap; ++i)
405     if(0 != bucket[i])
406       ++n;
407   return static_cast<double>(n) / cap;
408 }
409 
410 }  // namespace Sample
411 

 1 // unordered_set.hpp
 2 
 3 #pragma once
 4 
 5 #include "unordered_impl.hpp"
 6 
 7 namespace Sample
 8 {
 9 
10 template <typename K,
11           typename HF = hash<K>,
12           typename Compare = equal_to<K> >
13 class unordered_set : public unordered_impl<K, K, HF, Compare, identity<K> >
14 {
15 public:
16   // some typedefs just look like good names to understand
17   typedef unordered_impl<K, K, HF, Compare, identity<K> > hash_table;
18   typedef typename hash_table::value_type value_type;
19   typedef typename hash_table::const_reference const_reference;
20   typedef typename hash_table::hash_functor hash_functor;
21   typedef typename hash_table::compare compare;
22   typedef typename hash_table::key_of_value key_of_value;
23   typedef typename hash_table::size_type size_type;
24 public:
25   // constructor
26   unordered_set(size_type n = 0,
27                 const hash_functor& hash_func = hash_functor(),
28                 const compare& pred = compare());
29 
30   // destructor
31   ~unordered_set();
32 
33 }; // calss unordered_set
34 
35 template <typename K, typename HF, typename Compare>
36 unordered_set<K, HF, Compare>::unordered_set(
37   size_type n,
38   const hash_functor& hash_func,
39   const compare& pred)
40   : hash_table(n, hash_func, pred, key_of_value()) {}
41 
42 // destructor
43 template <typename K, typename HF, typename Compare>
44 unordered_set<K, HF, Compare>::~unordered_set() {}
45 
46 // namespace Sample
47 


 1 // unordered_map.hpp
 2 
 3 #pragma once
 4 
 5 #include <utility>
 6 #include "unordered_impl.hpp"
 7 
 8 namespace Sample
 9 {
10 
11 template <typename K,
12           typename V,
13           typename HF = hash<K>,
14           typename Compare = equal_to<K> >
15 class unordered_map : public unordered_impl<K, std::pair<K, V>, HF, Compare, select1st<std::pair<K, V> > >
16 {
17 public:
18   typedef K key_type;
19   typedef V data_type;
20   typedef unordered_impl<K, std::pair<K, V>, HF, Compare, select1st<std::pair<K, V> > > hash_table;
21   typedef typename hash_table::size_type size_type;
22   typedef typename hash_table::hash_functor hash_functor;
23   typedef typename hash_table::compare compare;
24   typedef typename hash_table::key_of_value key_of_value;
25   typedef typename hash_table::value_type value_type;
26   typedef typename hash_table::const_pointer const_pointer;
27   typedef typename hash_table::pointer pointer;
28   typedef typename hash_table::const_reference const_reference;
29   typedef typename hash_table::reference reference;
30 
31 private:
32   unordered_map(const unordered_map&);                // no implementation
33   unordered_map& operator = (const unordered_map&);   // no implementation
34 
35 public:
36   // constructor
37   unordered_map(size_type n = 0,
38                 const hash_functor& hash_func = hash_functor(),
39                 const compare& pred = compare());
40 
41   // destructor
42   ~unordered_map();
43 
44   // a convenient way to insert an item into fixed hash table
45   //        key         value
46   // fht[456789000u] = 12345678u;
47   // 'fht' is a unordered_map object, 456789000u is key, 12345678u is value
48   // to insert into the 'fht'.
49   // The operation will cause the result to happen.
50   // If there is an identical key, the operation will change the associated
51   // value, otherwise a new item pair<UInt32, UInt32>(456789000u, 12345678u)
52   // will be inserted into 'fht', and its size will increase 1.
53   // It can be used something like this below.
54   // const UInt32 FSZ = 1025u;
55   // unordered_map<UInt32, UInt32> fht(FSZ);
56   // 
57   // fht[987654321u] = 76543210u;
58   // 
59   // CAUTION: If the hash table has even been full, a futher operation can
60   // cause problems. Its your responsibilty to make sure there are enough
61   // vacancies to hold a new item. Well, we can do something like this below.
62   // while(!fht.full())
63   //   fht[rand32()] = rand32(); // all random integers in [0, 4294967295)
64   data_type& operator [] (const key_type& k);
65 
66   // If insertion failed, return false, otherwise return true
67   // k is a reference value of key_type, d is a refrence value of data_type
68   bool insert(const key_type& k, const data_type& d);
69 
70   using hash_table::insert;
71 }; // class unordered_map
72 
73 // constructor
74 template <typename K, typename V, typename HF, typename Compare>
75 unordered_map<K, V, HF, Compare>::unordered_map(size_type n,
76   const hash_functor& hash_func, const compare& pred)
77   : hash_table(n, hash_func, pred, key_of_value()) {}
78 
79 // destructor
80 template <typename K, typename V, typename HF, typename Compare>
81 unordered_map<K, V, HF, Compare>::~unordered_map() {}
82 
83 template <typename K, typename V, typename HF, typename Compare>
84 typename unordered_map<K, V, HF, Compare>::data_type&
85 unordered_map<K, V, HF, Compare>::operator [] (const key_type& k)
86 {
87   return insert(value_type(k, data_type()))->second;
88 }
89 
90 template <typename K, typename V, typename HF, typename Compare>
91 inline bool unordered_map<K, V, HF, Compare>::insert(const key_type& k, const data_type& d)
92 {
93   return 0 != insert(make_pair(k, d));
94 }
95 
96 // namespace Sample
97 

posted on 2014-06-15 17:26 Chipset 阅读(291) 评论(0)  编辑 收藏 引用 所属分类: 算法和数据结构消遣


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理