哈希函数、哈希冲突、开闭散列

哈希函数、哈希冲突、开闭散列

在实现哈希表之前需要先了解一些哈希的相关概念，什么是哈希函数？哈希冲突是什么，该怎么解决？开闭散列是啥？

一起往下看吧！

哈希函数

哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。哈希函数实现了将一个元素映射到一个特定的位置，为后面哈希表的实现打好了基础。

常见的哈希函数

下面介绍5中哈希函数，其中最常用的是直接定址法和除留余数法，那么这里也只重点介绍这两种。

1.直接定址法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

• 例如：一组数据{2，6，3，7，5，9} 取A=2，B=3；

2映射的位置为7

6映射的位置为15

…

2.除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

• 例如：一组数据{2，6，3，15，7，5，12，9}

取p为10，那么2映射的位置为2，6映射的位置为6，3映射位置为3，15映射位置为5，7映射位置为7，5映射位置为5，12映射位置为12，9映射位置为9

由此可见：会出现有不同的数映射到同一个位置，这种现象就是下面介绍的哈希冲突问题了。

3.平方取中法

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4.折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这
几部分叠加求和，并按散列表表长，取后几位作为散列地址

• 折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5.随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中
random为随机数函数。
通常应用于关键字长度不等时采用此法

哈希冲突

即使一个元素可以通过哈希函数映射一个位置，但是这个位置不一定就只属于这个元素，也有可能被其他的元素所映射，例如上面的除留余数法中的2 和 12 ，5 和15 都是两个不同的元素映射了同一个位置，这就是哈希冲突。
注意的是哈希冲突不可避免，但是可以优化哈希函数来降低哈希冲突的概率！！！

如何解决哈希冲突

方法一 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

其中冲突后寻找新的额空的位置又有两种常见的方式，线性探测法和二次探测法。

线性探测

• 例如：这里拿除留余数法作为哈希函数来举例

线性探测找空位的公式：hash(key)=key%p+i (i=1,2,3,…) 需要注意的时如果+i处理后hash(key)大于哈希表的长度就会越界所以得模上一个哈希表的长度！！！

• 线性探测优点：实现非常简单
• 线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同
  关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降
  低。如何缓解呢？
• 用下面的二次探测！！！

二次探测

二次探测找空位的公式：hash(key)=key%p+i*i (i=1,2,3,…) 需要注意的时如果 + i * i 处理后hash(key)大于哈希表的长度就会越界所以得模上一个哈希表的长度！！！

• 二次探测往后找空位置时按照+i的平方找的，i就是冲突的元素个数，那么冲突的元素所对应的位置就不会是连续拥挤的，会比较分散,找某个冲突元素的时候就不需要判断很多次才能找到！！！

闭散列的模拟实现

字符串哈希拓展

闭散列模拟实现：

#define  _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;


//散列表形式的哈希表实现
enum state
{
	EXIST,
	EMPTY,
	DELETE,
};
template<class K,class V>
struct table_data
{
	table_data(const pair<K,V>& kv = make_pair(K(),V()))
		:_state(EMPTY)
		,_kv(kv)
	{}

	pair<K,V> _kv;
	state _state;

};


template<class K>
struct DefaultHash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}

};

template<>
struct DefaultHash<int>
{
	size_t operator()(const size_t& key)
	{
		return key;
	}
};

//字符串哈希
template<>
struct DefaultHash<string>
{
	//size_t ret = 0;  这个变量不可以写在函数外面  否则就是成员变量了 对象每次调用一次该函数 该成员变量就会变化了 
	//这样就会使得相同的字符串映射的值不同了  必须写到函数里面做局部变量
	size_t operator()(const string& str)
	{
		size_t ret = 0;
		for (auto& e : str)
		{
			ret = ret * 131 + e;
		}
		return ret;
	}
};



template<class K,class V,class HashFunc=DefaultHash<K>>
class HashTable
{
public:
	typedef table_data<K, V> table_data;
	HashFunc HF;
	bool insert(const pair<K, V>& key)
	{
		if (find(key.first) != nullptr)
		{
			return false;
		}
		//扩容
		if (_table.size() == 0 || _size * 10 / _table.size() >= 7)
		{
			size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
			//HashTable newHT;
			HashTable newHT;
			newHT._table.resize(newsize);
		
			for (auto& e : _table)
			{
				if(e._state==EXIST)//只有当数据对应的映射点存在的话就插入  空和删除不插入
				newHT.insert(e._kv);
			}
			newHT._table.swap(_table);
		}
		size_t starti = HF(key.first);
		starti %= _table.size();

		size_t hashi = starti;
		size_t i = 1;
		while (_table[hashi]._state == EXIST)//该映射位置被占用 往后找空的位置
		{
			hashi = starti+i;
			i++;
			hashi %= _table.size();
		}
		_table[hashi]._kv = key;
		_table[hashi]._state = EXIST;
		++_size;
		return true;

	}
	
	table_data* find(const K& key)
	{
		if (_table.size() == 0)
			return nullptr;

		size_t starti = HF(key);
		starti %= _table.size();
		//用key来建立映射

		size_t hashi = starti;
		size_t i = 1;
		while (_table[hashi]._state != EMPTY)//如果当前映射位置已经被占了就往后占位  线性寻址法  
		{
			if (_table[hashi]._state != DELETE && _table[hashi]._kv.first == key)
			{
				return &_table[hashi];
			}
			//hashi = hashi + i;
			hashi = starti + i;
			i++;
			hashi %= _table.size();//防止越界访问
		}
		return nullptr;

	}

	bool erase(const K& key)
	{
		table_data* ret = find(key);
		if (ret == nullptr)
			return false;

		ret->_state = DELETE;
		return true;
	}


private:
	vector<table_data> _table;
	size_t _size = 0;
};

void test_closedtable()
{
	HashTable<int, int>  hash;
	hash.insert(make_pair(1,1));
	hash.insert(make_pair(10, 10));
	hash.insert(make_pair(3, 3));
	hash.insert(make_pair(6, 6));
	hash.insert(make_pair(7, 7));
	hash.insert(make_pair(15, 15));
	hash.insert(make_pair(20, 20));
	hash.insert(make_pair(30, 30));
	hash.insert(make_pair(40, 40));
	hash.insert(make_pair(50, 50));

	DefaultHash<string> dfh;
	string str[] = { "apple","pear","orange","banana","watermallon","tamato","apple","apple","alppe","eapr","ranoge" };

	vector<string> v(str, str + 11);
	for (auto& e : v)
	{
		cout << dfh(e) << endl;
	}
	HashTable<string, string> HT;
	for(auto& e:v)
	HT.insert(make_pair(e,e));


}


int main()
{
	test_closedtable();
	return 0;
}
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

方法二 开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地
址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

闭散列和开散列的比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：
由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <=
0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

所以哈希表使用的是开散列的方式实现的。

本文结束！ 下篇文章来模拟实现哈希表