C++：哈希表的模拟实现

哈希

在顺序结构和平衡树中，元素的Key和存储位置之间没有必然的联系，在进行查找的时候，要不断的进行比较，时间复杂度是O(N)或O(logN)

而有没有这样一种方案，可以直接不经过比较，从表中得到所需要的元素呢？直接进行获取就可以，如果存在这样的结构，那么对它而言的查找效率是很高的

插入元素

根据上面的原理，在插入元素的时候，根据插入元素的Key，找到一个可以映射到一个表中的具体位置，并进行存放

搜索元素

在对元素的Key进行计算后，就可以直接找到它被映射到了表中的哪一个位置，从而可以直接找到它在表中的位置，如果找到了就返回true

上面的这个原理，就叫做哈希，也叫做散列，而在哈希中使用的这个转换函数就叫做哈希函数，也叫做散列函数，构造出来的结构就叫做哈希表，也叫做散列表

下面用一个例子来举例：

例如数据集合有{1, 7, 6, 4, 5, 9}

那么就可以把根据一个哈希转换函数：hash(key) = key % capacity，得到一个专属于它的下标，把这个值存到下标的位置：

通过这样的方法就可以对元素和下标建立一种关系，在寻找的时候可以直接寻找到，在进行数据的存储和查找的过程拥有相当高的效率

但依旧有问题，如果存储的元素正好已经被存储过了呢？

哈希冲突

所谓哈希冲突，简单来说就是不同的Key值经过计算，得到了一个相同的hash值，此时再向表中填写数据就会有问题，这个过程就叫哈希冲突，也叫做哈希碰撞，那为什么会引起哈希碰撞？如何解决？

哈希函数

通常来说，引起哈希碰撞的一个原因是哈希函数有问题

常见的哈希函数定义：

1. 直接定址法：取Key值的某个线性函数作为散列地址，例如Hash（Key）= A*Key + B
2. 除留余数法：设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
3. 平方取中法
4. 折叠法
5. 数学分析法

哈希函数设计的越好，出现哈希冲突的可能性就越低，但无法避免哈希冲突，也就是说，哈希冲突是一定会发生的

解决哈希冲突

解决的方法通常有两种，闭散列和开散列

闭散列：

当发生哈希冲突的时候，如果哈希表没有被装满，那么就说明哈希表中肯定还有空余位置，那么就放到冲突位置的下一个位置当中去

1. 线性探测

从发生哈希冲突的位置开始，依次向后进行探测，直到探测到了一个空位置为止

那么下面模拟实现一下线性探测的实现过程

	bool insert(const pair<K, V>& kv)
	{
		// 考虑扩容问题
		if (_n * 10 / _t.size() == 7)
		{
			size_t newsize = _t.size() * 2;
			vector<HashData<K, V>> newV;
			newV.resize(newsize);
			size_t _newn = 0;

			// 把原来的数据放到新表中 遍历一次旧表
			for (int i = 0; i < _t.size(); i++)
			{
				// 如果旧表中这个位置的值存在 就准备放到新表中
				if (_t[i]._s == EXIST)
				{
					size_t newhashi = _t[i]._kv.first % newsize;
					while (newV[newhashi]._s == EXIST)
					{
						newhashi++;
						newhashi %= newsize;
					}
					newV[newhashi]._kv = _t[i]._kv;
					newV[newhashi]._s = EXIST;
					_newn++;
				}
			}
			_t.swap(newV);
			_n = newsize;
		}
		// 正常插入逻辑
		size_t hashi = kv.first % _t.size();
		while (_t[hashi]._s == EXIST)
		{
			// 如果插入元素的位置有内容，就插入到下一个位置
			hashi++;
			hashi %= _t.size();
		}

		_t[hashi]._kv = kv;
		_t[hashi]._s = EXIST;
		_n++;

		return true;
	}
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

但是闭散列的缺陷是很明显的，比如当插入数据是12,22,32,42…这样的数据的时候，就会导致不停地触发哈希冲突，这样会产生堆积的效应，为了避免出现这样的问题，又提出了开散列的方案

开散列

开散列也叫做哈希桶，也叫做拉链法，原理就是把具有相同地址的Key值放到一起，每一个子集就叫做一个桶，每个桶的元素通过单链表来进行链接，每个链表的头结点在哈希表中

开散列中每个桶中放的都是哈希冲突的元素

namespace opened_hashing
{
	// 定义节点信息
	template<class K, class V>
	struct Node
	{
		Node(const pair<K, V>& kv)
			:_next(nullptr)
			, _kv(kv)
		{}
		Node* _next;
		pair<K, V> _kv;
	};

	template<class K, class V>
	class HashTable
	{
		typedef Node<K, V> Node;
	public:
		// 构造函数
		HashTable()
			:_n(0)
		{
			_table.resize(10);
		}

		// 析构函数
		~HashTable()
		{
			//cout << endl << "*******************" << endl;
			//cout << "destructor" << endl;
			for (int i = 0; i < _table.size(); i++)
			{
				//cout << "[" << i << "]->";
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					//cout << cur->_kv.first << " ";
					delete cur;
					cur = next;
				}
				//cout << endl;
				_table[i] = nullptr;
			}
		}

		// 插入元素
		bool insert(const pair<K, V>& kv)
		{
			// 如果哈希表中有这个元素，就不插入了
			if (find(kv.first))
			{
				return false;
			}

			// 扩容问题
			if (_n == _table.size())
			{
				HashTable newtable;
				int newsize = _table.size() * 2;
				newtable._table.resize(newsize, nullptr);
				for (int i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;
						// 把哈希桶中的元素插入到新表中
						int newhashi = cur->_kv.first % newsize;
						// 头插
						cur->_next = newtable._table[newhashi];
						newtable._table[newhashi] = cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newtable._table);
			}

			// 先找到在哈希表中的位置
			size_t hashi = kv.first % _table.size();

			// 把节点插进去
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			_n++;

			return true;
		}

		Node* find(const K& Key)
		{
			// 先找到它所在的桶
			int hashi = Key % _table.size();

			// 在它所在桶里面找数据
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == Key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}

		void print()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				cout << i << "->";
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->_kv.first << " ";
					cur = cur->_next;
				}
				cout << endl;
			}
			cout << endl;
		}
	private:
		vector<Node*> _table;
		size_t _n;
	};
}
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

上面的实现看似没有问题，实际上依旧有问题，如果要传入的数据是string类，那么在比较的过程中会出现错误，因此要写一个仿函数用以处理这些情况

这里利用版本模板中的特化进行处理即可，处理细节比较巧妙

	template<class T>
	struct _Convert
	{
		T& operator()(const T& key)
		{
			return key;
		}
	};
	
	template<>
	struct _Convert<string>
	{
		size_t& operator()(const string& key)
		{
			size_t sum = 0;
			for (auto e : key)
			{
				sum += e * 31;
			}
			return sum;
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

那么下一步就要进行对于哈希表的封装了，详情见模拟实现篇章