哈希表

缘起

我们之前学过的N多树来进行排序, 但是基于CBA理论（【1】）这种树的排序算法的性能极限就是O(nlogn). 但是哈希算法并不基于比较，所以他的性能可以到达O(n). 但是代价是较大的空间复杂度. 本文给出哈希表的实现.

分析

采用线性探测的方式处理哈希冲突. 这里没有写删除方法, 删除很简单的. 直接置为INF即可

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
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
//#define LOCAL


class HashTable
{
public:
	HashTable(){memset(hashtable, 0x3f, sizeof(hashtable));}  // 伊始初始化为全部都是非法值

	int search(int key) // 在哈希表中搜索key, 返回-1的话表示没找到, 返回>=0的位置表示找到了或者找到了插入的位置
	{
		int addr = hash(key), tmp = addr;
		while(hashtable[addr]!=INF) // 如果不是非法值
		{
			if (hashtable[addr]==key) return addr; // 找到了
			addr = (addr+1)%SZ; // 往后移动一格(本hash表采用的处理冲突的策略是线性探测,当然，还可以使用其他处理冲突的策略，比如二次探测策略)
			if (addr == tmp) // 如果转了一圈转回来了, 说明找了一圈都没找到, 说明哈希表满了
			{
				return -1;
			}
		}
		// 来到这里说明while的过程中没有出现return, 说明找到了可以插入key的空位置
		return addr;
	}

	bool insert(int key) // 往哈希表中插入key, 返回true表示插入成功, false表示插入失败
	{
		int pos = search(key);
		if (!~pos)
		{
			puts("哈希表已满!");
			return false;
		}
		if (hashtable[pos] == key)
		{
			puts("已经存在此值,插入失败!");
			return false;
		}
		hashtable[pos] = key; // 插入
		return true;
	}

	int get(int pos) {return hashtable[pos];} // 获取 pos索引的值
protected:
private:
	const static int SZ = 13, INF = 0x3f3f3f3f; // 哈希表的长度, INF是非法值
	int hashtable[SZ]; // 哈希表

	int hash(int key) {return key%SZ;} // 使用取模函数作为散列（或者叫哈希）函数——找到存放的位置，当然，其实我们可以使用更为复杂的散列函数.

};




int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out","w", stdout);
#endif

	HashTable h;
	int a[19]={19,10,14,23,1,68,10,20,79,84,27,55,23,11,10,79,24,28,30},key;
	for (int i = 0; i < 19; i++)h.insert(a[i]);
	puts("输入你想查找的值");
	while (~scanf_s("%d",&key))
	{
		int pos = h.search(key);
		if (!~pos || h.get(pos)!=key)		
			puts("不存在");
		else
		{
			printf("存在,索引为%d\n", pos);
		}
	}

#ifdef LOCAL
	fclose(stdin);
#endif
	return 0;
}

后继

其实再探测属于hash表的一种冲突处理策略. hash表的冲突处理策略分成两种，另一种是拉链式的. 这里不给出实现（实现也非常简单），看一下下面的图就秒懂了(冲突的元素以头插的形式组成一支链表)

但是哈希表这种数据结构没有问题吗? 一直能保持O(1)的性能吗? 非也! 因为哈希表有一个重要概念——负载因子（load factor），这个概念在java.util.HashMap中有提及.

负载因子 = 总键值对数 / 数组长度

负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是 1，或者 0.75 等)时，哈希表将自动扩容。

哈希表在自动扩容时，一般会创建两倍于原来个数的箱子，因此即使 key 的哈希值不变，对箱子个数取余的结果也会发生改变，因此所有键值对的存放位置都有可能发生改变，这个过程也称为重哈希(rehash)。

哈希表的扩容并不总是能够有效解决负载因子过大的问题。假设所有 key 的哈希值都一样，那么即使扩容以后他们的位置也不会变化。虽然负载因子会降低，但实际存储在每个箱子中的链表长度并不发生改变，因此也就不能提高哈希表的查询性能。

基于以上总结，细心的读者可能会发现哈希表的两个问题:

  1. 如果哈希表中本来箱子就比较多，扩容时需要重新哈希并移动数据，性能影响较大。
  2. 如果哈希函数设计不合理，哈希表在极端情况下会变成线性表，性能极低。

参考

【1】https://yfsyfs.github.io/2019/05/25/CBA%E7%90%86%E8%AE%BA-%E4%B8%BA%E4%BB%80%E4%B9%88%E5%9F%BA%E4%BA%8E%E6%AF%94%E8%BE%83%E7%9A%84%E6%8E%92%E5%BA%8F%E6%96%B9%E6%B3%95%E7%9A%84%E6%80%A7%E8%83%BD%E6%9E%81%E9%99%90%E6%98%AFO-nlogn/