哈希结构（图文详解）【哈希表，哈希桶，位图，布隆过滤器】

2024-07-09 10:18| 来源: 网络整理| 查看: 265

哈希结构哈希概念

常见的K-V结构，实现了元素关键码与元素值的映射关系，但没有实现元素关键值与元素存储位置的映射关系，在遍历过程中，一般的顺序表或搜索二叉树要进行关键值的多次比较，其中顺序表的时间复杂度为O(n),二叉搜索树的时间复杂度O(lgn)

对此希望找到一种理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

哈希函数

常见哈希函数1. 直接定制法取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况 2. 除留余数法设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p0.7,此时认为产生冲突的可能性大，需要进行扩容

扩容并非在原表基础上增大size，而是开辟新表，将原表已存在状态位置元素进行逐一存放，代码如下：

void checkcapacity() { //负载因子控制是否增容 //负载因子越小，冲突越小，但空间浪费越大 if (HSTable.size()==0&&_size * 10 / HSTable.size() > 7) { //开新表 int newcap = HSTable.size() == 0 ? 10 : 2 * HSTable.size(); HashTable newHST(newcap); //直接拷贝会导致hash值计算前后不一致 //需要重新计算hash位置 for (int i = 0; i < HSTable.size(); i++) { if (HSTable[i].state == EXIST) { newHST.insert(HSTable[i].kv); } } swap(newHST); } } void swap(HashTable& HT) { swap(HSTable,HT.HSTable); swap(_size, HT._size); }

查找：由于hash冲突，直接通过索引查找难以找到发生hash冲突而通过线性探测法存放的元素，非空位置逐一查找，如果索引超过了表大小，需要循环从头开始

Node* find(const k& key) { //计算hash位置 int idx = key%HSTable.size(); //搜索 while (HSTable[idx].state != EMPTY) { if (HSTable[idx].state == EXIST && key == HSTable[idx].first) return &HSTable[idx]; ++idx; if (idx == HSTable.size() - 1) idx = 0; } return nullptr; }

删除：删除并非真删除，释放元素，而是改变对应元素位置状态信息

bool erase(const k& key) { Node* node = find(key); if (node) { node->state = DELETE; _size--; return true; } return false; } 开散列（哈希桶）

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

bool insert(const V& val) { checkcapacity(); KeyofValue kov; int idx = kov(val) % _hst.size(); //查找 Node* cur = _hst[idx]; while (cur) { if (kov(cur->_val) == kov(val)) { //key重复 return false; } cur = cur->_next; } //插入头插 cur = new Node(val); cur->_next = _hst[idx]; _hst[idx] = cur; _size++; return true; }

哈希桶通过建立新连接进行扩容操作：

void checkcapacity() { if (_size == _hst.size()) { int newcap = _size == 0 ? 10 : 2 * _size; vector newhst(newcap); KeyofValue kov; for (int i = 0; i < _hst.size(); i++) { Node* cur = _hst[i]; while (cur) { Node* next = cur->_next; int idx = kov(cur->_val) % newhst.size(); //新表头插 cur->_next = newhst[idx]; newhst[idx] = cur; cur = next; } //原表断开置空 _hst[i] = nullptr; } swap(_hst,newhst); } } 迭代器操作：

迭代器的++步骤：

#include #include using namespace std; template struct HashNode { V _val; HashNode* _next; HashNode(const V& val) :_val(val) ,_next(nullptr) { } }; //hash表的前置声明 template class HSTable; //hash表迭代器封装单链表节点 template struct HashIterator{ typedef HashNode Node; typedef HSTable ht; typedef HashIterator Self; //成员：节点指针，哈希表指针 Node* _node; ht* _hptr; HashIterator(Node* node,ht* hptr) :_node(node) ,_hptr(hptr) { } Self& operator++() { if (_node->_next) { _node = _node->_next; } //找下一个非空链表头结点 else { //计算当前节点在hash表中位置 KeyofValue kov; int idx = kov(_node->_val) % _hptr->_hst.size(); //从下一位置开始查找 ++idx; for (int; idx < _hptr->_hst.size(); idx++) { if (_hptr->_hst[idx]) { _node = _hptr->_hst[idx];//找到非空链表头结点给node记录 break; } } if (idx = _hptr->_hst.size())//此时走到end位置将node节点置为空 { _node = nullptr; } } return *this; } }; template class HSTable { public: typedef HashNode Node; typedef HashIterator iterator; //由于迭代器需要访问其私有成员_hst 声明为友元类 friend HashIterator; HSTable(int n=10) :_hst(n) ,_size(0) { } iterator begin() { for (int i = 0; i < _hst.size(); i++) { if (_hst[i]) { return iterator(_hst[i], this); } else return iterator(nullptr,this); } } iterator end() { return iterator(nullptr, this); } private: vector _hst; int _size; }; 哈希表的应用位图

位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

比如Tencent的一道面试题：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中

此题解法较多，一般容易想到的就是暴力求解，直接遍历查询，但海量数据导致时间复杂度过大，无法实际中应用；稍微进阶一些的会想到采用二分查找，虽然相比较于直接遍历，把时间复杂度从O(n)提升到O(lgn)，但对于40亿数据还是难以实现

而通过位图可以实现：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

代码实现如下：

#include #include using namespace std; /* 位图应用：（1）存放不重复数据简单信息，不需要存放数据本身优点：节省空间，查找效率高 */ class bitset { public: //位图内存大小与数据范围有关 bitset(size_t range) :_bit(range/32+1) { } //存储信息 void set(size_t num) { //计算整数位置 int idx = num / 32; //计算比特位置 int bitidx = num % 32; //对应比特位置1 按位或运算 _bit[idx] |= (1 > bitidx)&1; } //删除信息 void reset(size_t num) { //计算整数位置 int idx = num / 32; //计算比特位置 int bitidx = num % 32; //对应比特位置10 _bit[idx] &= ~(1

【本文地址】

公司简介

联系我们