文章目录

• 前言
• • 1、哈希表与哈希函数的引入
  • 2、哈希表
• 一、设计
• • 1、一般、通用哈希函数的设计
  • 2、默认哈希函数
• 二、哈希冲突
• • 1、链地址法。(seperate chaining )
  • • 1.1、实现
    • 1.2、测试
  • 2、哈希表的动态空间优化
• 参考

前言

1、哈希表与哈希函数的引入

就像这道题来说，用一个26个的int 型数组，就可以实现对每个字符进行哈希映射。

其中哈希函数为：f(char) = char -‘a’ ;哈希表就是那个int [26]；

这种简单的哈希函数就处理了从键到索引的转换，同时也是简单的一一对应的。

而更复杂的问题，通常会使得不同的键映射成为同样的索引，这就是哈希冲突。

而我们所需要处理的就是解决哈希冲突。

2、哈希表

哈希表的实现，体现了算法设计领域的经典思想：空间换时间。

哈希表就是在时间和空间之间的平衡

因为哈希表的两个极端就是

无限的空间：对应O(1) 的查找复杂度；

O(1）的空间：对应O(n)的查找复杂度；

所以哈希函数的设计很重要。希望哈希函数能将“键”映射成的“索引”分布的越均匀越好。

一、设计

1、一般、通用哈希函数的设计

常用的哈希函数：转成整形处理

遵循：

• 一致性：一样的键对应一样的哈希映射
• 高效性：计算高效便捷
• 均匀性：哈希值均匀分布(取模）

一般性：

1. 小范围的正整数直接使用
2. 小范围的负整数进行偏移（偏移到正整数）
3. 大整数：取模
4. 浮点数：转换成整数。
5. 字符串：转换成整数。
6. 对于复合类型(如日期)：转换成为字符串处理

其中大整数的取模：

简单的模造成：分布不均、没有利用所有信息。而通常模一个素数，不是合数。且根据数据规模的大小，素数的选取也是有人在研究的。即不同的素数模造成的哈希冲突的概率问题。

其中浮点数：

计算机中都是用32位、64位二进制存储，然后重新解析成为的浮点数。那我们直接用这个二进制当作整数来映射是一样的。同样套用大整数来取模即可。

其中字符串：

字符串如果表示的十进制：就转换成十进制整数来做
字符串表示的是字母，就按照26进制（或者更大进制）转换为整数来做。
如下图：M代表的就是素数模，同时也是哈希表的大小。B代表的就是根据字符串来定的进制数。
其中hash函数向下优化分别：简化了运算、利用多次取模避免溢出(同时结果不会有影响,即，多次取模和最后取模结果一样，但是避免了中间溢出）

2、默认哈希函数

C++中有默认哈希函数对象类。在“functional”中。

我们可以使用其哈希函数，打印出来对应的映射。

#include <functional>
#include <string>
int main() {
    std::hash<int> hash_int;
    std::hash<double> hash_double;
    std::hash<std::string> hash_string;
    int a = 42;
    std::cout << hash_int(a) << std::endl;

    int b = -42;
    std::cout << hash_int(b) << std::endl;

    double c = 3.1415926;
    std::cout << hash_double(c) << std::endl;

    std::string d = "temp";
    std::cout << hash_string(d) << std::endl;
    return 0;
}

二、哈希冲突

1、链地址法。(seperate chaining )

哈希表就是一个M大小的数组(M为取模值）。

对应位置存储链表，将其冲突value 挂在链表上。

当然也有使用tree map 实现的。即每个位置存的都是一个红黑树。(tree map一般都是红黑树实现)

时间复杂度：哈希表M大，数据N个。及，每个地址存的数据为n/m个。得出：

如果用链表存储：O(n/m）//遍历链表
如果用平衡树存储：O(log(n/m)）//遍历tree

但是极端情况（哈希函数设置不恰当）使得所有数据都哈希冲突，所有的n都存在一个位置。那么时间复杂度变成O(n）和O(log(n)）；

信息安全中有种攻击方法就是利用这种机制：哈希碰撞攻击：通过了解哈希值的计算方法，设计一套数据，以实现所有数据产生哈希冲突，使得其哈希表时间复杂度变坏，拖慢系统运行速度。

1.1、实现

重点：

1. 申请的是map的数组
2. 通过位与将hash计算出来的数修改成正数，能作为索引使用
3. 构造函数可以互相调用
4. 得到map用指针操作，以减少多次hash计算的消耗。同样用引用也可以。

template<typename Key, typename Value>
class HashTable {
private:
	int M;
	int size;
	map<Key, Value> *hashTable; //map 的数组

	int hash(Key key) {
		return (hashCode(key) & 0x7fffffff) % M; //负数转正数
	}

	int hashCode(Key key) { //用C++ 的hash函数
		std::hash<Key> key_hash;
		return key_hash(key);
	}

public:

	HashTable(int M) {
		this->M = M;
		size = 0;
		hashTable = new map<Key, Value>[M];
	}

	HashTable() {
		this->M = 97;
		new(this)HashTable(M); //调用构造函数
	}

	int getSize() {
		return size;
	}

	void add(Key key, Value value) {
		map<Key, Value> *my_map = &hashTable[hash(key)]; //指针，使得只hash运算一次。
		if (my_map->count(key)) {
			my_map->find(key)->second= value;
		}
		else {
			my_map->insert(make_pair(key, value));
			size++;
		}
	}

	Value *remove(Key key) {
		Value temp;
		map<Key, Value> *my_map = &hashTable[hash(key)];
		if (my_map->count(key))
		{
			temp = my_map->find(key)->second;
			my_map->erase(key);
			size--;
		}

		return &temp; //注意这里有问题
		//最好改成new出来，使用完了delete掉。尽量不用值传递，和传局部变量指针。
		//或者在调用他的地方创建一个value，然后改造函数成传入value指针，直接把数据复制到那里去即可。就不用返回值了
	}

	bool contains(Key key) {
		return hashTable[hash(key)].count(key);
	}

	Value *get(Key key) {
		return &(hashTable[hash(key)])[key]; //传地址。以防value 是大型数据结构
	}

	void set(Key key, Value value) {
		map<Key, Value> &my_map = hashTable[hash(key)]; //引用， 使得只hash运算一次。
		if (!my_map.count(key)) {
			throw to_string(key) + " doesn't exist";
		}
		//assert(my_map.count(key)!=0);
		my_map.find(key)->second = value;
	}
};

1.2、测试

void main()
{
	HashTable<int, int> temp;

	temp.add(1, 2);
	cout << *(temp.get(1)) << endl;
	temp.add(1, 3);
	cout << *(temp.get(1)) << endl;
	temp.set(1, 5);
	cout << *(temp.get(1)) << endl;

	cout << boolalpha << temp.contains(1) << endl;
	cout << boolalpha << temp.contains(2) << endl;
	try { 
		temp.set(2, 5); }
	catch (const string msg){ 
		cerr << msg << endl; }

	//int *mm = (temp.remove(1));
	//cout<< (void*)mm << endl;
	cout << *(temp.remove(1)) << endl;
	cout << boolalpha << temp.contains(1) << endl;
}

2、哈希表的动态空间优化

上述哈希表实现的时间复杂度强相关于哈希表大小M，那么就可以通过改造哈希表容量，来真正实现哈希表0(1)的时间复杂度。

即设定上下边界，当N/M>= upperTol，即数据量与哈希表大小的比值超过上界，就扩容。
当N/M< lowerTol，即数据量与哈希表大小的比值少于下界，就缩容。

参考

模板类、模板函数设计

bobo老师github