目录
1、Hash表的概念
2、为什么使用Hash函数
3、Hash冲突（不可避免）
4、解决哈希冲突的方法
4.1闭散列
4.2 开散列
5、Hash函数
6、Hash函数的实战
出于刷LeetCode的需要，对字符串查找几乎是必须要使用到的技巧。普通的遍历自然是可行之举，但其时间复杂度也会根据你选择的算法而有那么些超出范围。于是，在笔者查找资料与题型比对后，本篇文章横空出世，涵盖着笔者对Hash函数些许拙见。新人发文章，如有错误，还望轻批、指正。
1、Hash表的概念
那么在了解一项新事物之前，我们总逃不开对事物了解的逻辑思维三段论：是什么？为什么？怎么用？而在本段，就由笔者来向你们粗浅地讲述一番什么是Hash表。
正如笔者开篇所提，查找一段数据，由你选择的算法决定你程序的时间复杂度，那么自然地，为了效率，我们会不会想要有那么一个足够迅速的算法，可以直接得出我想要的数据，理想的搜索方法就是搜索一次就能直接从容器中找到数据。那么这种想法可以实现吗？笔者告诉你是可以的。
以上为百科对Hash表的介绍，我们通过对上面几行的描述大致可以理解到：Hash表可以根据一个key值来直接访问数据，因此它的查找速度是很快的。同时，我们也可以认识到我们还需要一个能够帮我们转换key值的函数，将这个 key 所对应的存储位置 index 得出，即Hash函数。
总结一下，我们要构造一种存储结构（Hash表），存放数据时，给数据定义一个 key 值，每个数据的key值按照简单的Hash函数计算出一个存储该数据元素信息的位置坐标 index ，使元素的存储位置index与它的关键码之间能够建立一种一一对应的关系，也就是 映射，那么在查找时通过该函数可以很快找到该元素。
通俗点说，我们可以将想要的数据的关键码 key，输入进一个我们自身编写的转换器Hash函数，让转换器直接将笔者存储结构（Hash表）内的相应位置 index 输出，然后在 Hash表 内部通过 index 直接获取对应的值 value。这就是键值对（key ——value）的意思。
2、为什么使用Hash函数
谈完了是什么，自然也要说说为什么？其实开篇笔者已经提过一点，那就是效率！一个好的Hash表在查找方面拥有无与伦比的优势：不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间，即0(1）的时间级。（所对应的自然是空间占用过大了，可以说是用空间换时间吧）
对哈希表的使用者一一人来说，这是一瞬间的事。哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。
哈希表也有一些缺点，它是基于数组的，数组创建后难以扩展。某些哈希表被基本填满时，性能下降得非常严重，所以程序虽必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程。又或是建立一个动态数组，不够再插入堆空间，也是极为便利的。）
如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。
3、Hash冲突（不可避免）
那么谈完使用的原因，自然要说到怎么使用了。理所当然地，我们是希望我们每一个不同的 key 都能只对应不同的一个 value，就像我们希望对应的锁只有对应的那把钥匙才能打开，不然那还叫锁吗？
而这有可能实现吗？答案是否定的。因为我们的空间是有限的，而数据是无限的，根本不可能通过有限的空间来存储繁杂多样的数据，因此不同的 key 对应了同一个位置 index 的 value 是不可避免存在的。这就是 Hash表 中存在的大难题，Hash冲突。
通过选定的哈希函数计算key值，有时不同的key值通过相同的哈希函数会计算出相同的位置，这种现象就是 哈希冲突 或称为 哈希碰撞 ，要通过特定的方法解决哈希冲突的问题。
造成Hash冲突的原因：可能有其存储结构（Hash表）内存空间分配太少，再优秀的Hash函数也挽救不了的可能性存在。不过最大的可能还是Hash函数设计的不合理。
4、解决哈希冲突的方法
我们有两种方式来解决Hash冲突的问题，分别为闭散列和开散列。
4.1闭散列
闭散列方法也叫开放定址法，是当计算的位置已经有元素存在即发生冲突时，如果哈希表还没满就找到冲突位置的下一个位置去存放元素。有两种常用的寻找下一个位置的方法。
线性探测 当计算的初始位置发生冲突时，下标+1，判断是否位置上为空，是就把元素放入该位置，否则继续向后探测。 二次探测 计算的初始位置记为start，设置一个步长i初始为0，用start+i^2作为放入元素的位置，就是从初始位置开始计算，冲突了就探测后面的位置，不过是每次i+1后的平方，这样跳跃式探测。
闭散列哈希表的插入元素就按上面两种方式之一进行，删除元素不能通过随便的物理删除哈希表的元素，因为这样做可能在查找元素时造成误判，比如我们插入两个元素，两个元素是发生冲突的，插入第一个元素到计算的哈希地址上去，第二个元素就要按线性探测或二次探测存放到哈希地址的后面，当我们删除第一个元素后，该位置为空了，再来查找第二个元素，我们计算出了这个哈希地址就是原先的哈希地址，该地址为空我们就认为第二个元素不在表中，其实它在该位置的后面位置。合适的做法是把数据元素加上一个状态值。
4.2 开散列
闭散列插入数据，有冲突就把元素从哈希地址开始往后找空位放入，开散列则是把冲突的元素用链表连起来，挂在计算的哈希地址的位置上。我们结合6中的实战来看。
5、Hash函数
一个好的Hash函数必须有着以下特性：
1. 确定性：对于相同的输入数据，哈希算法会生成相同的哈希值。
2. 不可逆性：无法从哈希值中推导出原始的输入数据。
3. 唯一性：不同的输入数据生成的哈希值应尽可能不同。
4. 散列性：即使输入数据仅有微小的变化，生成的哈希值应该有很大的差异。
除此之外，依笔者拙见，Hash函数 应该简单点比较好，不要过多的使用乘法，宁可多用位移<<。因为在计算机中是以二进制存储数据，+ 或是 位操作 均比乘除法效率高出一截。
下面我们来见一下常见的 Hash函数
直接定址法 就是线性函数 y=kx+b 这类的函数。优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况。 除留余数法 是用 key 值取模存储结构的容量得到的计算值，即 Hash(key)=key%capacity ,也可以是取模一个不大于容量的值。 平方取中法 假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。 折叠法 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。 随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法。
6、Hash函数的实战
基于笔者在LeetCode上的题库所见，直接定址法是足够用于平常的刷题所用，故还是较为推荐学习使用的。至于其它方法，等以后遇到的时候会再进行补充。
下图为Leetcode简单题的一解，使用的就是直接定址法，并且在使用Hash表后可以较为容易地解出结果。
int firstUniqChar(char* s)
{
//此处hash表为数组形式
//小写字母个数为26，故hash表设26个存储地址
//全部置0，方便计数
int hash[26] = {0};
for(int i = 0; i < strlen(s); i++)
{
//此处 x 即为 字母对应的value位置所在，
int x = s[i] - 'a';
//遍历后对hash表内26个元素计数
hash[x]++;
}
//从前向后遍历，得出的必为第一个
for(int i = 0; i < strlen(s); i++)
{
int x = s[i] - 'a';
if(hash[x] == 1)
//hash函数巧妙使用了原字符串的下标，故可直接返回下标
return i;
}
return -1;
}
一般来说，实现哈希表我们可以采用两种方法：
1、数组+链表
2、数组+二叉树
上题为简单的数组 Hash表，而下图则是用到了数组+链表的结合，并且使用了开散列的方式来解决冲突问题：
#include
#include
#include
#define TABLE_SIZE 100
// 哈希节点:链表形式
typedef struct Node {
char* key;
int value;
struct Node* next;
} Node;
// 哈希表
typedef struct HashTable {
Node* buckets[TABLE_SIZE];
} HashTable;
// 哈希函数
unsigned int hash(const char* key) {
unsigned int hash_value = 0;
while (*key != '\0') {
hash_value = hash_value *31 + *key;
key++;
}
return hash_value % TABLE_SIZE;
}
这段代码定义了哈希表中的节点结构，它包含一个键(key)和相应的值(value)，以及指向下一个节点的指针(next)。同时还定义了哈希表的结构。哈希表由多个节点指针组成，是一个指针数组，每个指针都代表着一条链表。并且定义了一个简单的哈希函数。它遍历键中的每个字符，通过乘以31并加上字符的ASCII值来计算哈希值，然后对TABLE_SIZE进行取余操作，以确保哈希值在合适的范围内。
不过此处可以修改成如下图所示，减少计算机运算压力。
hash_value = hash_value <<5 + *key;
我们继续看后面的代码：
// 创建哈希表
HashTable* createHashTable() {
HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));
if (hashTable == NULL) {
fprintf(stderr, "Memory allocation failed.\n");
exit(EXIT_FAILURE);
}
for (int i = 0; i < TABLE_SIZE; i++) {
hashTable->buckets[i] = NULL;
}
return hashTable;
}
这段代码实现了创建Hash表。它分配给新建的Hash表内存，并将每个bucket的指针初始化为NULL，此时Hash表内每个元素都相当于一个链表的头节点指针。
// 插入键值对
void insert(HashTable* hashTable, const char* key, int value) {
unsigned int index = hash(key);
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
fprintf(stderr, "Memory allocation failed.\n");
exit(EXIT_FAILURE);
}
//为需要插入的key创建一片空间，并将此空间地址赋予新节点的key（strdup需要与free搭配）
newNode->key = strdup(key);
newNode->value = value;
newNode->next = NULL;
// 插入到链表头部
newNode->next = hashTable->buckets[index];
hashTable->buckets[index] = newNode;
}
这段代码实现了插入键值对。它首先使用hash()函数计算键的哈希值，然后创建一个新的节点，并设置节点的键、值和next指针。如果对应的bucket为空，则将新节点直接放入bucket中，成为链表的头节点；如果不为空，则将新节点添加到该index处链表头部，并让 新节点成为该index处的新头节点，方便后续相同index节点的头插入。（这就是使用开散列来对冲突进行处理）
// 查找键对应的值
int search(HashTable* hashTable, const char* key) {
unsigned int index = hash(key);
Node* current = hashTable->buckets[index];
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
return current->value;
}
current = current->next;
}
return -1; // 未找到
}
这段代码实现了查找值。它首先使用hash()函数计算键的哈希值，然后在对应的bucket中遍历链表，逐个比较节点的键和给定的键，如果相等则返回节点的值，否则继续向下搜索。如果没有找到对应的键值对，则返回-1。
// 销毁哈希表
void destroyHashTable(HashTable* hashTable) {
for (int i = 0; i < TABLE_SIZE; i++) {
Node* current = hashTable->buckets[i];
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp->key);
free(temp);
}
}
free(hashTable);
}
这段代码实现了销毁哈希表。它逐个遍历哈希表的每个bucket，并释放每个节点的键和节点本身的内存，直到链表为空。最后释放哈希表的内存。
以下是示例：
int main() {
HashTable* hashTable = createHashTable();
// 插入键值对
insert(hashTable, "apple", 5);
insert(hashTable, "banana", 8);
insert(hashTable, "orange", 12);
// 查找键对应的值
printf("Value for key 'apple': %d\n", search(hashTable, "apple"));
printf("Value for key 'banana': %d\n", search(hashTable, "banana"));
printf("Value for key 'orange': %d\n", search(hashTable, "orange"));
printf("Value for key 'grape': %d\n", search(hashTable, "grape"));
// 销毁哈希表
destroyHashTable(hashTable);
return 0;
}
结果如下：
总之，结合代码来看，hash表还是可以理解的，而具体的使用也得看代码的需求。毕竟再好用的算法也离不开使用它的环境。那么笔者今天就先写到这里，我们下次在见。
ps：小白萌新一个，求轻喷！！！
推荐阅读
发表评论