7.3 哈希表与布隆过滤器（入门）—— C语言实现

本文主要是介绍7.3 哈希表与布隆过滤器（入门）—— C语言实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

前言

本章内容参考海贼宝藏胡船长的数据结构与算法中的第七章——查找算法，侵权删。

哈希表的优点：

1. 高效的操作时间：在最佳情况下，哈希表的查找、插入和删除操作的时间复杂度为 O(1)。这是因为哈希表通过哈希函数直接计算出数据应存储在哪个位置，从而快速定位数据。
2. 直接访问：不需要像在树结构中那样进行多次比较或遍历。

---

一、哈希表

哈希表利用了数组的特性。当我们给出数组下标的时候，就能返回下标所对应的元素值，时间复杂度是O(1)，这个特性也很类似python的字典。说白了就是元素和下标（字典中的键值）完成映射。这个映射关系就叫做哈希函数。

1.1 哈希函数

所谓哈希本质上是高维空间到低维空间的一种映射（不一定是一一映射，可能会出现哈希冲突），映射规则就是哈希函数。

哈希函数（也就是映射规则）是根据具体场景去设计的，不是固定的。但有优化的空间：理想情况下，哈希函数应该均匀分布，这意味着每个可能的索引值都有相等的概率被映射到，以减少冲突。

1.2 哈希冲突

非一一映射

由于哈希表的大小通常远小于可能的键的数量，多个不同的键可能会被哈希到同一个索引值，这就造成了哈希冲突。
怎么处理哈希冲突呢？
1. 开放定址法：在开放地址法中，所有的元素都存储在哈希表数组中。当发生冲突时，使用探测序列（例如线性探测、二次探测或双重哈希等）找到下一个空闲的槽位。
2. 再哈希法（双重哈希）：这是开放地址法的一种特殊情况，使用两个哈希函数来减少冲突。这种情况不常用，因为哈希函数比较难去创造。
3. 建立公共溢出区：额外建立缓冲区，把发生冲突的数据放入到缓冲区。缓冲区可能是其他数据结构，例如堆，二叉排序树，红黑树等。把它理解成为另外的用于查找的数据结构。（该缓存区的查找效率可能没有哈希表的查找效率高）。
4. 链式地址法：在这种方法中，哈希表的每个桶或槽位不仅存储单个元素，而是存储一个链表。当多个元素哈希到同一个桶时，它们会被添加到该桶的链表中。查找、插入和删除操作需要遍历链表以找到目标元素。

补充：每个位置存储链表的效率其实并不高，实际上在实际工程中，每个位置上实现一个红黑树！！！

哈希表没有具体设计规则可言（哈希函数没有标准答案），冲突处理方式也不太同意，他给开发者极大的发挥空间。

---

二、布隆过滤器

举个使用布隆过滤器的应用场景的例子——搜索引擎的爬虫：
搜索引擎在收录网页信息的时候，为了避免重复爬取，它会把爬取过的地址记录下来。所以爬虫在每次爬取的时候，它都会判断一下，当前爬取的网页是否爬取过。记录地址需要一种数据结构，如果用传统哈希表，那么数以千计的网址使得该记录的存储空间会变得巨大。

布隆过滤器的存储空间实际上与它设计时预期要存储的元素数量有关，但这种关系并不是直接存储每个元素的细节，而是通过一组固定大小的位数组来实现，这些位用于代表集合中元素的可能存在。布隆过滤器提供了一种非常空间效率高的方法来测试一个元素是否属于一个集合，但这种方法允许存在一定的错误率（误判率，或者说概率性），即它能判断该元素大概率出现过，但它判断一个元素没有出现过的概率是1（那就真没出现过）。

布隆过滤器的工作原理：

1. 位数组：布隆过滤器背后的数据结构是一个大的位数组，通常初始化时所有位都是0。
2. 多个哈希函数：使用多个独立的哈希函数，每个函数都将元素映射到位数组中的一个位置。
3. 添加元素：将某个元素添加到布隆过滤器时，该元素被每一个哈希函数映射，相应的位数组中的位被设置为1。
4. 元素查询：查询一个元素是否存在于集合中时，使用相同的哈希函数对元素进行映射，然后检查所有对应的位是否为1。如果所有位都是1，那么元素可能存在于集合中；如果任何一位是0，则元素绝对不在集合中。

存储空间与元素数量的关系：

• 设计参数：布隆过滤器的大小（即位数组的长度）和使用的哈希函数数量直接影响其性能，包括误判率和查询速度。这些参数通常在创建过滤器时根据预期要处理的元素数量和可接受的误判率来选择。
• 空间效率：布隆过滤器不存储元素本身，只记录元素可能存在的信息。这使得它比存储实际元素的传统数据结构（如哈希表或集合）更加空间效率。
• 误判率：增加位数组的大小和使用更多的哈希函数可以降低误判率，但这会增加空间使用和计算开销。适当选择这些参数是设计布隆过滤器时的一个关键考虑。

结论：

虽然布隆过滤器的存储空间不直接存储每个元素的详细信息，但其设计和效能确实依赖于预期要处理的元素数量和可接受的误判率。布隆过滤器是一种权衡存储空间和准确性的高效方法，特别适用于那些可以容忍一定误报率的应用场景，如网络数据处理、数据库查询优化等。

---

三、哈希表的代码演示

冲突处理方式选择拉链法
哈希表中存储的数据类型是字符串

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>typedef struct Node{char *s;struct Node *next;
} Node;typedef struct HashTable{Node *data; //哈希表底层有个数组空间 int cnt, size;
} HashTable;//节点Node初始化方法
Node *getNewNode(const char *s){Node *p = (Node *)malloc(sizeof(Node));p->s = strdup(s);p->next = NULL;return p;
}//初始化哈希表
HashTable *getNewHashTable(int n){HashTable *h = (HashTable *)malloc(sizeof(HashTable));h->data = (Node *)malloc(sizeof(Node) * n);h->size = n;h->cnt = 0;return h;
}//哈希函数：经典的字符串哈希算法
int hash_func(const char *s){int seed = 131, h = 0;for (int i = 0; s[i]; i++){h = h * seed + s[i];}return h & 0x7fffffff; //这里去掉最高位（符号位）强制变成正数
}bool find(HashTable *h, const char *s){int hcode = hash_func(s), ind = hcode % h->size;Node *p = h->data[ind].next;while (p){if (strcmp(p->s, s) == 0) return true;p = p->next;}return false;
}bool insert(HashTable *h, const char *s){int hcode = hash_func(s), ind = hcode % h->size; //哈希值转换成为数组下标//放在链表的头部，效率更高：链表头插法,这里采用虚拟头节点！！！Node *p = getNewNode(s);p->next = h->data[ind].next;h->data[ind].next = p;h->cnt += 1;return true;
}void clearNode(Node *p){if (p == NULL) return;if (p->s)  free(p->s);free(p);return;
}void clearHashTable(HashTable *h){if (h == NULL) return;for (int i = 0; i < h->size; i++){Node *p = h->data[i].next, *q;while (p){q = p->next;clearNode(p);p = q;}}free(h->data);free(h);return;
}void output(HashTable *h){printf("\n\nHash Table(%d / %d) : \n", h->cnt, h->size);for (int i = 0; i < h->size; i++){printf("%d : ", i);Node *p = h->data[i].next;while (p){printf("%s -> ", p->s);p = p->next;}printf("\n");}return;
}int main(){srand(time(0));char s[100];#define MAX_N 2HashTable *h = getNewHashTable(MAX_N);while (~scanf("%s", s)){if (strcmp(s, "end") == 0) break;insert(h, s);}output(h);while (~scanf("%s", s)){printf("find(%s) = %d\n", s, find(h, s));}#undef MAX_Nreturn 0;
}

输出结果：

3.1 哈希表扩容

扩容操作：初始化一个大小为原来哈希表大小的两倍，再将原来哈希表的数据通通插入到新的哈希表中来。这样就完成了扩容。

思考：这样的扩容操作，会把原来小的数据全插入到大的中，这会不会太慢了？？？

均摊时间复杂度
最终哈希表大小为n，意味着，之前是$\frac{n}{2}$，之前的之前是$\frac{n}{4}$。一次类推，把这个大的哈希表整个生命周期的时间复杂度加在一起：
$\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+......\approx n$
所以上述算式代表的是一个大小为n的哈希表历史上所有的由于扩容产生的操作加在一起也是n，平摊到每一个元素上也是O(1)的量级
均摊时间复杂度：不要看某一次的操作耗时，其实应该观察该数据结构整个声明周期耗时多少。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>#define swap(a, b){ \__typeof(a) __c = a; \a = b, b = __c;  \
}typedef struct Node{char *s;struct Node *next;
} Node;typedef struct HashTable{Node *data; //哈希表底层有个数组空间 int cnt, size;
} HashTable;//节点Node初始化方法
Node *getNewNode(const char *s){Node *p = (Node *)malloc(sizeof(Node));p->s = strdup(s);p->next = NULL;return p;
}//初始化哈希表
HashTable *getNewHashTable(int n){HashTable *h = (HashTable *)malloc(sizeof(HashTable));h->data = (Node *)malloc(sizeof(Node) * n);h->size = n;h->cnt = 0;return h;
}//哈希函数：经典的字符串哈希算法
int hash_func(const char *s){int seed = 131, h = 0;for (int i = 0; s[i]; i++){h = h * seed + s[i];}return h & 0x7fffffff; //这里去掉最高位（符号位）强制变成正数
}bool find(HashTable *h, const char *s){int hcode = hash_func(s), ind = hcode % h->size;Node *p = h->data[ind].next;while (p){if (strcmp(p->s, s) == 0) return true;p = p->next;}return false;
}void swapHashTable(HashTable *h1, HashTable *h2){swap(h1->data, h2->data);swap(h1->cnt, h2->cnt);swap(h1->size, h2->size);return;
}bool insert(HashTable *, const char *);
void clearHashTable(HashTable *);void expand(HashTable *h){printf("expand Hash Table %d -> %d\n", h->size, h->size * 2);HashTable *new_h = getNewHashTable(h->size * 2); //新哈希表的大小是原哈希表的两倍for (int i = 0; i < h->size; i++){Node *p = h->data[i].next;while (p){insert(new_h, p->s);p = p->next;}} //至此，将原来哈希表中所有的元素插入到了新哈希表中swapHashTable(h, new_h);clearHashTable(new_h);return;
}bool insert(HashTable *h, const char *s){if (h->cnt >= h->size * 2){expand(h);}int hcode = hash_func(s), ind = hcode % h->size; //哈希值转换成为数组下标//放在链表的头部，效率更高：链表头插法,这里采用虚拟头节点！！！Node *p = getNewNode(s);p->next = h->data[ind].next;h->data[ind].next = p;h->cnt += 1;return true;
}//实现见上一段代码
void clearNode(Node *p);
void clearHashTable(HashTable *h);
void output(HashTable *h);// 测试代码用上一个例子的

输出结果：

注意：代码中用swap(h1->data, h2->data)交换两个用malloc函数申请的内存地址，就是将地址交换，而不是将地址里面的数据进行交换！！！

---

四、总结

1. 哈希表，哈希冲突及冲突处理
2. 简单介绍了布隆过滤器

参考文献

1. 数据结构与算法中的第七章——查找算法

这篇关于7.3 哈希表与布隆过滤器（入门）—— C语言实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---