KJHの博客

记录&回忆

0%

STL哈希表

发表于 更新于 分类于
本文字数： 16k 阅读时长 ≈ 15 分钟

哈希表是一个很重要的数据结构，在各大场合均有应用，比如在内核网络栈中的 sock_array 的结构。

之前也学习过哈希表 ，建议看此文之前，先看前面用C++实现的简洁的哈希表。这里通过剖析SGI STL 中的hashtable 来进一步探索hashtable。

SGI STL 中哈希表采用链接法解决冲突。结构中维护了一个 vector，vector 中每一个元素称为一个桶（bucket），它包含的是一个链表的第一个节点。

哈希表的思想这里就不赘述了，直接通过STL 的源码来剖心其内部实现。

一、 hash table 的节点定义：

1
2
3
4
5
template <class Value>
struct __hashtable_node
  __hashtable_node* next; //下一个节点
  Value val; //键值
};

bucket 所维护的正是上述的 hash table node。

​ img

从上图可知，buckets vector 中存放的是bucket，然后每个bucket 存放链表（如果有的话）。通俗的说bucket 就是动态array 中的一个元素。

二、hashtable 的迭代器：

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
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
	//typedef 定义
	typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
	hashtable;
	typedef __hashtable_iterator<Value, Key, HashFcn,
		ExtractKey, EqualKey, Alloc>
		iterator;
	typedef __hashtable_const_iterator<Value, Key, HashFcn,
		ExtractKey, EqualKey, Alloc>
		const_iterator;
	typedef __hashtable_node<Value> node;
	typedef forward_iterator_tag iterator_category;  //迭代器类型
	typedef Value value_type;  //迭代器所指对象的型别
	typedef ptrdiff_t difference_type;  //两个迭代器之间的距离
	typedef size_t size_type;
	typedef Value& reference;
	typedef Value* pointer;
	node* cur;  //迭代器目前所指节点
	hashtable* ht;  //保持对容器的连结关系（因为可能需要从bucket跳到bucket）
	/*构造函数*/
	__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
	__hashtable_iterator() {}
	/*运算符重载*/
	reference operator*() const { return cur->val; }
	pointer operator->() const { return &(operator*()); }
	iterator& operator++();  //前缀++
	iterator operator++(int); //后缀++
	bool operator==(const iterator& it) const { return cur == it.cur; }
	bool operator!=(const iterator& it) const { return cur != it.cur; }
};

hashtable 迭代器必须永远维系着与整个“bucket vector” 的关系，并记录目前所指的节点。其前进操作是首先尝试从目前所指的节点出发，前进一个位置（节点），由于节点被安置于 list 内，所以利用节点的 next 指针即可轻易达成前进操作。如果目前节点正巧是list 的尾端，就跳至下一个bucket 身上，那正是指向下一个list 的头部节点。上面的 hashtable* ht; 就是为这点添加的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*前缀++*/
template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>&
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{
	const node* old = cur;//保存当前位置
	cur = cur->next;//更新为当前bucket链表中的下一个节点
	if (!cur) {//如果该节点恰好为list 的尾端
		size_type bucket = ht->bkt_num(old->val);//通过散列函数查找键值对应的bucket
		while (!cur && ++bucket < ht->buckets.size())//根据元素值定位下一个bucket的起头处
			cur = ht->buckets[bucket];
	}
	return *this;
}
/*后缀++，返回的是++之前的数值*/
template <class V, class K, class HF, class ExK, class EqK, class A>
inline __hashtable_iterator<V, K, HF, ExK, EqK, A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++(int)
{
	iterator tmp = *this;
	++*this;//调用operator++
	return tmp;//返回自增前的值
}

三、hashtable 的数据结构

由于在STL源码中 hashtable 的操作函数都定义在结构体类，这里我们只摘取一部分，具体函数实现在后面介绍

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
/*hashtable节点结构，处于篇幅考虑，这里省去对应const类型code*/
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey,
class Alloc>
class hashtable {
public:
	typedef Key key_type;//节点的键值型别
	typedef Value value_type;//节点的实值型别
	typedef HashFcn hasher;//散列函数的函数型别
	typedef EqualKey key_equal;//判断键值相同与否的方法
	/*
    ExtractKey：从节点中取出键值的方法
	Alloc：空间配置器，缺省使用std::alloc
	*/
	typedef size_t            size_type;
	typedef ptrdiff_t         difference_type;
	typedef value_type*       pointer;
	typedef const value_type* const_pointer;
	typedef value_type&       reference;
	typedef const value_type& const_reference;
	hasher hash_funct() const { return hash; }
	key_equal key_eq() const { return equals; }
private:
	hasher hash;
	key_equal equals;
    ExtractKey get_key;
	typedef __hashtable_node<Value> node;
	typedef simple_alloc<node, Alloc> node_allocator;
	vector<node*, Alloc> buckets;//桶（动态array）
	size_type num_elements;//散列表中所有元素的个数
public:
	/*typedef 定义*/
	typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,
		Alloc>
		iterator;
	typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,
		Alloc>
		const_iterator;
	friend struct
		__hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
	friend struct
		__hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
public:
	/*构造函数*/
	hashtable(size_type n,
		const HashFcn&    hf,
		const EqualKey&   eql,
		const ExtractKey& ext)
		: hash(hf), equals(eql), get_key(ext), num_elements(0)
	{
		initialize_buckets(n);//初始化

	}

	hashtable(size_type n,
		const HashFcn&    hf,
		const EqualKey&   eql)
		: hash(hf), equals(eql), get_key(ExtractKey()), num_elements(0)
	{
		initialize_buckets(n);
	}
	/*拷贝构造函数*/
	hashtable(const hashtable& ht)
		: hash(ht.hash), equals(ht.equals), get_key(ht.get_key), num_elements(0)
	{
		copy_from(ht);
	}
	/*赋值构造函数*/
	hashtable& operator= (const hashtable& ht)
	{
		if (&ht != this) {
			clear();//清除原有数据
			hash = ht.hash;
			equals = ht.equals;
			get_key = ht.get_key;
		copy_from(ht);
		}
		return *this;
	}
	/*析构函数*/
	~hashtable() { clear(); }
	size_type size() const { return num_elements; }//实际元素
	size_type max_size() const { return size_type(-1); }
	bool empty() const { return size() == 0; }//判断是否为空
	/*类里面，this* 与ht交换，浅交换*/
	void swap(hashtable& ht)
	{
		::swap(hash, ht.hash);
		::swap(equals, ht.equals);
		::swap(get_key, ht.get_key);
		buckets.swap(ht.buckets);
		::swap(num_elements, ht.num_elements);
	}
	/*迭代器有效首位置*/
	iterator begin()
	{
	for (size_type n = 0; n < buckets.size(); ++n)
	if (buckets[n])
			/*下面实质就是__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab){}*/
		return iterator(buckets[n], this);
		return end();
	}
	/*迭代器尾端位置的下一位置，其实是空位置*/
	iterator end() { return iterator(0, this); }
	/*==运算符重载*/
	friend bool operator== (const hashtable<Value, Key,
	HashFcn, ExtractKey, EqualKey,
		Alloc>&,
		const hashtable<Value, Key,
		HashFcn, ExtractKey, EqualKey,
		Alloc>&);
public:
	/*返回桶子的个数(vector的大小)*/
	size_type bucket_count() const { return buckets.size(); }
	/*可能的最大值（质数表里的最大值）*/
	size_type max_bucket_count() const
	{
		return __stl_prime_list[__stl_num_primes - 1];
	}
	/*指定第bucket个桶中节点的个数*/
	size_type elems_in_bucket(size_type bucket) const
	{
	size_type result = 0;
		for (node* cur = buckets[bucket]; cur; cur = cur->next)//某bucket中链表节点的个数
			result += 1;
		return result;
	}
	/*插入单个元素，不允许重复*/
	pair<iterator, bool> insert_unique(const value_type& obj)
	{
	resize(num_elements + 1);//判断是否需要重建表格，如需要就扩充
		return insert_unique_noresize(obj);
	}
	/*插入单个元素，允许重复*/
	iterator insert_equal(const value_type& obj)
	{
		resize(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);
	/*下面都是批量元素插入*/
	……
	/*两个连续存储区之间的元素插入*/
	void insert_unique(const value_type* f, const value_type* l)
	{
		size_type n = l - f;
		resize(num_elements + n);
		for (; n > 0; --n, ++f)
			insert_unique_noresize(*f);
	}
	void insert_equal(const value_type* f, const value_type* l)
	{
		size_type n = l - f;
		resize(num_elements + n);
		for (; n > 0; --n, ++f)
			insert_equal_noresize(*f);
	}
	/*插入两个迭代器之间的元素，不允许重复*/
	void insert_unique(const_iterator f, const_iterator l)
	{
		size_type n = 0;
		distance(f, l, n);//迭代器距离
		resize(num_elements + n);
		for (; n > 0; --n, ++f)
			insert_unique_noresize(*f);//两个迭代器之间的元素逐步插入
	}
	/*插入两个迭代器之间的元素，允许重复*/
	void insert_equal(const_iterator f, const_iterator l)
	{
		size_type n = 0;
		distance(f, l, n);//迭代器距离
		resize(num_elements + n);
		for (; n > 0; --n, ++f)
			insert_equal_noresize(*f);//两个迭代器之间的元素逐步插入(这里的两个迭代器之间不是线性的)
	}
	reference find_or_insert(const value_type& obj);
	/*查找*/
	iterator find(const key_type& key)
	{
	size_type n = bkt_num_key(key);//定位
		node* first;
		/*直接在下面循环中完成搜索*/
		for (first = buckets[n];
			first && !equals(get_key(first->val), key);
			first = first->next)
		{
		}
		return iterator(first, this);
	}
	/*统计与键值key相等的元素的个数*/
	size_type count(const key_type& key) const
	{
		const size_type n = bkt_num_key(key);//定位
		size_type result = 0;
		for (const node* cur = buckets[n]; cur; cur = cur->next)
		if (equals(get_key(cur->val), key))
			++result;
	return result;
	}
	pair<iterator, iterator> equal_range(const key_type& key);
	pair<const_iterator, const_iterator> equal_range(const key_type& key) const;
	size_type erase(const key_type& key);
	void erase(const iterator& it);
	void erase(iterator first, iterator last);
	void erase(const const_iterator& it);
	void erase(const_iterator first, const_iterator last);
	void resize(size_type num_elements_hint);
	void clear();
private:
	size_type next_size(size_type n) const { return __stl_next_prime(n); }
	/*buckes初始化*/
	void initialize_buckets(size_type n)
	{
		const size_type n_buckets = next_size(n);//质数表里大于等于该数的最小质数
		buckets.reserve(n_buckets);//调整buckets大小（buckets其实就是一个vector）
		buckets.insert(buckets.end(), n_buckets, (node*)0);
		num_elements = 0;
	}
	/*下面近似是散列函数，判知元素的落脚处*/
	/*只接受键值*/
	size_type bkt_num_key(const key_type& key) const
	{
		return bkt_num_key(key, buckets.size());
	}
	/*只接受实值（value）*/
	size_type bkt_num(const value_type& obj) const
	{
		return bkt_num_key(get_key(obj));
	}
	/*接受键值和 buckets个数*/
	size_type bkt_num_key(const key_type& key, size_t n) const
	{
		return hash(key) % n;
	}

	/*接受实值（value）和 buckets个数*/
	size_type bkt_num(const value_type& obj, size_t n) const
	{
		return bkt_num_key(get_key(obj), n);
	}
	/*创建新节点*/
	node* new_node(const value_type& obj)
	{
		node* n = node_allocator::allocate();
		n->next = 0;
		try {
		construct(&n->val, obj);
		return n;
		}
		catch (...) {
			node_allocator::deallocate(n);
			throw;
		}
	}
	/*销毁*/
	void delete_node(node* n)
	{
		destroy(&n->val);
		node_allocator::deallocate(n);
	}
	void erase_bucket(const size_type n, node* first, node* last);
	void erase_bucket(const size_type n, node* last);
	void copy_from(const hashtable& ht);
};

补充：

质数表：SGI STL 中的hashtable 是采用质数来设定表格大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*质数表*/
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __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
};

/*以下找出上述28个质数之中，最接近并大于 n的那个质数（有的话），没有取最大*/
inline unsigned long __stl_next_prime(unsigned long n)
{
	const unsigned long* first = __stl_prime_list;//首
	const unsigned long* last = __stl_prime_list + __stl_num_primes;//尾的下一位置
	/*泛型算法，返回一个迭代器，指向第一个不小于 n的元素*/
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;//如果没有比它大的就取最大的
}

这里考虑到元素的各种型别，将散列函数封装起来

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
template <class Key> struct hash { };
/*字符串类型*/
inline size_t __stl_hash_string(const char* s)
{
	/*处理方法*/
	unsigned long h = 0;
	for (; *s; ++s)
		h = 5 * h + *s;
	return size_t(h);
}
/*字符串类型，则调用上面处理方法*/

struct hash<char*>
{
	size_t operator()(const char* s) const { return __stl_hash_string(s); }
};
struct hash<const char*>
{
	size_t operator()(const char* s) const { return __stl_hash_string(s); }
};
/*下面各种类型直接返回，无需额外处理*/
struct hash<char> {
	size_t operator()(char x) const { return x; }
};

struct hash<unsigned char> {
	size_t operator()(unsigned char x) const { return x; }
};

struct hash<signed char> {

	size_t operator()(unsigned char x) const { return x; }
};
struct hash<short> {
	size_t operator()(short x) const { return x; }
};
struct hash<unsigned short> {
	size_t operator()(unsigned short x) const { return x; }
};

struct hash<int> {
	size_t operator()(int x) const { return x; }

};

struct hash<unsigned int> {

	size_t operator()(unsigned int x) const { return x; }

};

struct hash<long> {

	size_t operator()(long x) const { return x; }

};

struct hash<unsigned long> {

	size_t operator()(unsigned long x) const { return x; }

};

插入操作与表格重整

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
/*以下函数判断是否需要重建表格。如果不需要，立即返回。如果需要，就重建*/

template <class V, class K, class HF, class Ex, class Eq, class A>

void hashtable<V, K, HF, Ex, Eq, A>::resize(size_type num_elements_hint)
{

	const size_type old_n = buckets.size();//bucket vector 的大小
	/*如果元素个数(把新增元素计入后)比bucket vector 大，则需要重建表格*/
	if (num_elements_hint > old_n) {
		const size_type n = next_size(num_elements_hint);//找出下一个质数
		if (n > old_n) { //old_n不是质数表里面的最大值时，才可扩展
			vector<node*, A> tmp(n, (node*)0);//设立新的bucket vector，大小为n
			try {
				//以下处理每一个旧的bucket
				for (size_type bucket = 0; bucket < old_n; ++bucket) {
					node* first = buckets[bucket];//指向节点所对应之串行(链表)的起始节点
					while (first) {//处理单个bucket中的链表
						size_type new_bucket = bkt_num(first->val, n);//找出节点落在哪一个新的bucket内
						buckets[bucket] = first->next;//令旧bucket指向其所对应的链表的下一个节点，以便迭代处理

						/*下面将当前节点插入到新的bucket内，成为其对应链表的第一个节点，这里的实现比较巧妙

						相当于插入新节点到新bucket vector中，新插入的元素插入到链表的首位置，这里不同于一般的插入的是，
						由于之前已有元素占据空间，这里只是修改节点指针指向*/
						first->next = tmp[new_bucket];
						tmp[new_bucket] = first;

						first = buckets[bucket];//回到旧bucket所指的待处理链表，准备处理下一个节点
				                        //first = old_first->next;

					}
				}
			buckets.swap(tmp);//vector::swap 新旧两个buckets 对调（浅修改）
				/*对调两方如果大小不同，大的会变小，小的会变大，离开时释放local tmp 的内存*/

			}
			catch (...) {
				for (size_type bucket = 0; bucket < tmp.size(); ++bucket) {
					while (tmp[bucket]) {
						node* next = tmp[bucket]->next;
						delete_node(tmp[bucket]);
						tmp[bucket] = next;
					}
				}
				throw;
			}
		}
	}
}

/*插入元素，不允许重复*/
template <class V, class K, class HF, class Ex, class Eq, class A>
pair<hashtable<V, K, HF, Ex, Eq, A>::iterator, bool>
hashtable<V, K, HF, Ex, Eq, A>::insert_unique_noresize(const value_type& obj)
{
	const size_type n = bkt_num(obj);//定位bucket
	node* first = buckets[n];
	/*判断插入元素是否有重复*/
	for (node* cur = first; cur; cur = cur->next)
	if (equals(get_key(cur->val), get_key(obj)))
		return pair<iterator, bool>(iterator(cur, this), false);
	node* tmp = new_node(obj);//产生新节点 node_allocator::allocate()
	/*先插入节点放在链表最前面*/
	tmp->next = first;
	buckets[n] = tmp;
	++num_elements;//元素个数增加
	return pair<iterator, bool>(iterator(tmp, this), true);
}

/*插入元素，允许重复*/
template <class V, class K, class HF, class Ex, class Eq, class A>
hashtable<V, K, HF, Ex, Eq, A>::iterator
hashtable<V, K, HF, Ex, Eq, A>::insert_equal_noresize(const value_type& obj)
{
	const size_type n = bkt_num(obj);//定位bucket
	node* first = buckets[n];//链表头节点
	for (node* cur = first; cur; cur = cur->next)
	if (equals(get_key(cur->val), get_key(obj))) {//如果插入元素是重复的(与cur->val重复)
		node* tmp = new_node(obj);
		tmp->next = cur->next;//新增元素插入重复元素的后面
		cur->next = tmp;
		++num_elements;
		return iterator(tmp, this);
	}
	//没有重复，等同于insert_unique_noresize()
	node* tmp = new_node(obj);
	tmp->next = first;
	buckets[n] = tmp;
	++num_elements;
	return iterator(tmp, this);
}

​ img

​ img

插入过程，可以用上面两张图（来源wikipedia）来说明。

复制与整体删除

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
/*复制*/
template <class V, class K, class HF, class Ex, class Eq, class A>
void hashtable<V, K, HF, Ex, Eq, A>::copy_from(const hashtable& ht)
{
	buckets.clear();//清除所有原有元素
	buckets.reserve(ht.buckets.size());//bucket vector 空间调整为 ht对应的大小
	buckets.insert(buckets.end(), ht.buckets.size(), (node*)0);//从尾端开始插入n个元素，其值为NULL指针
	//此时buckets vector 为空，所以所谓尾端，就是起头处
	try {
		for (size_type i = 0; i < ht.buckets.size(); ++i) {
		//这里是复制vector 中的每一个元素
			if (const node* cur = ht.buckets[i]) {//如果该位置不为空，表明有元素需要复制
				node* copy = new_node(cur->val);
				buckets[i] = copy;//先是bucket vector 中的元素
				//然后是针对同一个bucket list，复制每一个节点
				for (node* next = cur->next; next; cur = next, next = cur->next) {
					copy->next = new_node(next->val);
					copy = copy->next;
				}
			}
		}
		num_elements = ht.num_elements;
	}
	catch (...) {
		clear();
		throw;
	}
}
/*删除第 n 个bucket中的所有元素（链表也要逐个删除）*/
template <class V, class K, class HF, class Ex, class Eq, class A>
void hashtable<V, K, HF, Ex, Eq, A>::erase_bucket(const size_type n, node* last)
{
	node* cur = buckets[n];
	while (cur != last) {
		node* next = cur->next;
		delete_node(cur);
		cur = next;
		buckets[n] = cur;
		--num_elements;
	}
}
/*整体删除，考虑链表的存在，需要逐个删除释放内存*/
template <class V, class K, class HF, class Ex, class Eq, class A>
void hashtable<V, K, HF, Ex, Eq, A>::clear()
{
	//针对每一个bucket
	for (size_type i = 0; i < buckets.size(); ++i) {
		node* cur = buckets[i];
		//删除释放该桶中的链表中的所有节点
		while (cur != 0) {
			node* next = cur->next;
			delete_node(cur);
			cur = next;
		}
		buckets[i] = 0;
	}
	num_elements = 0;
	//此时bucket vector 空间并未释放