1
#ifndef HASH_MAP_H
2#define HASH_MAP_H
3
4#include "list"
5#include "algorithm"
6#include "iostream"
7
8using namespace std;
9
10template<typename Key, typename T>
11class value_type
12
{
13
public:
14
15 value_type(const Key& key, const T& t):first(key)
16
{
17 second = t;
18
}
19
20 value_type(const value_type& val):first(val.first)
21 {
22 second = val.second;
23 }
24
25 bool operator==(const value_type& other_value_type) //考虑第一个组件，比较 键值 项的比较的依据
26 {
27 return first == other_value_type.first;
28 }
29
30 Key first;
31 T second;
32
};
33
34template<typename Key, typename T, typename Hash_Func>
35class hash_map
36{
37 friend ostream& operator<<(ostream& os, hash_map<Key, T, Hash_Func>& map)
38 {
39 hash_map<Key,T,Hash_Func>::iterator temp_itr;
40
41 for (temp_itr = map.begin(); temp_itr!=map.end(); temp_itr++)
42 {
43 os<<(*temp_itr).first<<" "<<(*temp_itr).second<<endl;
44 }
45 os<<endl<<endl;
46 return os;
47 }
48private:
49
50 typedef Key key_type;
51 typedef Hash_Func hash_func;
52
53 list<value_type<const key_type, T> >* buckets; //列表桶
54 unsigned count; //当前项的数量
55 unsigned lenght; //桶长度
56 hash_func hash; //函数对象
57
58 const static int DEFAULT_SIZE;
59 const static float MAX_RATIO;
60
61 void check_for_expansion()
62 {
63 list<value_type<const key_type,T> >* temp_buckets;
64
65 list<value_type<const key_type, T> >::iterator list_itr;
66
67 if (count < lenght*MAX_RATIO)
68 {
69 return;
70 }
71
72 lenght = lenght*2+1;
73
74 temp_buckets = buckets;
75
76 buckets = new list<value_type<const key_type, T> >[lenght];
77
78 unsigned i=0;
79
80 unsigned address;
81
82 while (i < lenght/2)
83 {
84 if (!temp_buckets[i].empty())
85 {
86 for (list_itr = temp_buckets[i].begin(); list_itr!=temp_buckets[i].end(); list_itr++)
87 {
88 address = hash((*list_itr).first)%lenght;
89 buckets[address].push_back(*list_itr);
90 }
91 }
92 i++;
93 }
94
95 for (i=0; i<lenght/2; i++)
96 {
97 if (!temp_buckets[i].empty())
98 {
99 temp_buckets[i].erase(temp_buckets[i].begin(),temp_buckets[i].end());
100 }
101 }
102 delete []temp_buckets;
103 }
104public:
105 hash_map()
106 {
107 buckets = new list<value_type<const key_type, T> >[DEFAULT_SIZE];
108 count = 0;
109 lenght = DEFAULT_SIZE;
110 }
111
112 ~hash_map()
113 {
114 delete []buckets;
115 }
116
117 unsigned size()
118 {
119 return count;
120 }
121
122 //class iterator;
123 //friend class iterator;
124
125 class iterator //前向迭代器
126 {
127 friend class hash_map<key_type,T,hash_func>;
128 private:
129 list<value_type<const key_type,T> >* buckets_ptr; //桶列表
130 typename list<value_type<const key_type,T> >::iterator list_itr; //指向桶当前位置的 列表 元素
131 unsigned index; //指向桶当前下标
132 unsigned lenght; //当前桶长度
133
134 public:
135
136 iterator operator++(int)
137 {
138 iterator old_itr = *this;
139
140 unsigned ind = index;
141
142 if (++list_itr != buckets_ptr[ind].end()) //返回元素 不是当前列表最后一个元素
143 {
144 return old_itr;
145 }
146
147 while(ind < lenght-1) //查找下一个不为空的列表
148 {
149 ind++;
150 if (!buckets_ptr[ind].empty())
151 {
152 index = ind;
153 list_itr = buckets_ptr[ind].begin();
154 return old_itr;
155 }
156 }
157
158 index = ind; //返回元素 已经是最后一个元素，返回end()
159 list_itr = buckets_ptr[ind].end();
160 return old_itr;
161 }
162
163 bool operator==(const iterator& other_iterator)
164 {
165 return (buckets_ptr == other_iterator.buckets_ptr)&&
166 (list_itr == other_iterator.list_itr)&&
167 (index == other_iterator.index)&&
168 (lenght == other_iterator.lenght);
169 }
170
171 bool operator!=(const iterator& other_iterator)
172 {
173 return !(*this == other_iterator);
174 }
175
176 value_type<const key_type,T> operator*() //返回list元素
177 {
178 return *list_itr;
179 }
180
181 };
182
183 iterator begin() //寻找第一个元素
184 {
185 iterator temp_itr;
186
187 temp_itr.buckets_ptr = buckets;
188
189 int index = 0;
190
191 while (index < lenght) //
192 {
193 if (!buckets[index].empty())
194 {
195 temp_itr.index = index;
196 temp_itr.list_itr = buckets[index].begin();
197 temp_itr.lenght = lenght;
198 return temp_itr;
199 }
200 index++;
201 }
202
203 index--; //
204
205 temp_itr.index = index;
206 temp_itr.list_itr = buckets[index].end();
207 temp_itr.lenght = lenght;
208 return temp_itr;
209 }
210
211 iterator end()
212 {
213 iterator temp_itr;
214
215 temp_itr.buckets_ptr = buckets;
216
217 int index = lenght-1;
218
219 temp_itr.index = index;
220 temp_itr.list_itr = buckets[index].end();
221 temp_itr.lenght = lenght;
222 return temp_itr;
223 }
224
225 pair<iterator , bool> insert(const value_type<const key_type, T>& x)
226 {
227 iterator temp_itr;
228
229 temp_itr = find(x.first);
230
231 if (!(temp_itr == end())) //已经存在该键值
232 {
233 return pair<iterator,bool>(temp_itr,false);
234 }
235
236 unsigned index = hash(x.first)%lenght;
237 //temp_itr.list_itr = buckets[index].push_back(x);
238 buckets[index].push_back(x);
239 count++;
240 check_for_expansion();
241 return pair<iterator,bool>(find(x.first),true);
242
243 }
244
245 iterator find(const key_type& key)
246 {
247 iterator temp_itr;
248 unsigned index;
249 index = hash(key)%lenght;
250
251 temp_itr.list_itr = std::find(buckets[index].begin(),buckets[index].end(),
252 value_type<const key_type, T>(key,T()));
253
254 if (temp_itr.list_itr == buckets[index].end())
255 {
256 return end();
257 }
258
259 temp_itr.buckets_ptr = buckets;
260 temp_itr.index = index;
261 temp_itr.lenght = lenght;
262 return temp_itr;
263 }
264
265 void erase(const iterator& itr)
266 {
267 buckets[itr.index].erase(itr.list_itr);
268 count--;
269 }
270
271 T& operator[](const key_type& key)
272 {
273 return (*(insert(value_type<const key_type,T>(key,T())).first)).second;
274 }
275
276 bool operator==(const hash_map<const key_type,T,hash_func>& other_hash_map)
277 {
278 return (buckets == other_hash_map.buckets)&&
279 (count == other_hash_map.count)&&
280 (lenght == other_hash_map.lenght);
281 }
282};
283#endif
284
285template<typename Key, typename T, typename Hash_Func>
286const int hash_map<Key,T,Hash_Func>::DEFAULT_SIZE = 203;
287template<typename Key, typename T, typename Hash_Func>
288const float hash_map<Key,T,Hash_Func>::MAX_RATIO = 0.75;
289
290
291
posted on 2009-12-16 23:36
HenDanTou 阅读(239)
评论(0) 编辑 收藏 引用 所属分类:
数据结构