东莞网站建设公司好,网站做电子链接标识申请好吗,nginx wordpress 主题,ui网页设计字体哈希 1. 哈希概念2. 哈希冲突3. 哈希冲突解决3.1 哈希表的闭散列3.2 哈希表的开散列 2. 哈希的应用2.1 位图2.2 布隆过滤器 哈希#xff08;Hash#xff09;是一种将任意长度的二进制明文映射为较短的二进制串的算法。它是一种重要的存储方式#xff0c;也是一种常见的检索方… 哈希 1. 哈希概念2. 哈希冲突3. 哈希冲突解决3.1 哈希表的闭散列3.2 哈希表的开散列 2. 哈希的应用2.1 位图2.2 布隆过滤器 哈希Hash是一种将任意长度的二进制明文映射为较短的二进制串的算法。它是一种重要的存储方式也是一种常见的检索方法。哈希函数通过特定方式hash函数处理输入生成一个值。这个值等同于存放数据的地址这个地址里面再把输入的数据进行存储。 哈希算法是一种以较短的信息来保证文件唯一性的标志这种标志与文件的每一个字节都相关而且难以找到逆向规律。因此当原文件发生改变时其标志的位置也会发生改变此时的对应方式就不再适应需要将数据重新进行标对应的位置。 顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O( l o g 2 N log_2 N log2N)搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。
1. 哈希概念
如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。
当向该结构中
插入元素根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放。搜索元素对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功。
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表。散列方法的主要思想是根据结点的关键码值来确定其存储地址以关键码值K为自变量通过一定的函数关系h (K) (称为散列函数)计算出对应的函数值来把这个值解释为结点的存储地址将结点存入到此存储单元中。 检索时用同样的方法计算地址然后到相应的单元里去取要找的结点。 通过散列方法可以对结点进行快速检索。 用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快。 如上图如果再插入14会出现什么问题会出现哈希冲突。
2. 哈希冲突
哈希冲突是指两个或多个不同的键值被哈希函数映射到了同一个地址中的情况。这种情况下一个地址对应多个键值对而查找时只能找到其中一个键值对因此会导致查找失败。 引起哈希冲突的一个原因可能是哈希函数设计不够合理。 哈希函数设计原则1.哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间2.哈希函数计算出来的地址能均匀分布在整个空间中。 常见哈希函数
直接定址法–(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀缺点需要事先知道关键字的分布情况使用场景适合查找比较小且连续的情况除留余数法–(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址平方取中法–(了解) 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址平方取中法比较适合的情况不知道关键字的分布而位数又不是很大的情况。
3. 哈希冲突解决
哈希冲突是哈希表中常见的问题解决哈希冲突的方法有很多种两种常见的方法是闭散列和开散列。
3.1 哈希表的闭散列
闭散列是一种解决哈希冲突的方法它将所有的关键字都保存在散列表中而不是像开放地址法那样只保存一部分。在闭散列中每个桶都是一个链表当发生哈希冲突时新的元素会被插入到对应桶的链表中。这种方法可以避免开放地址法中的聚集现象并且可以在空间充足的情况下实现快速查找。 线性探索 如上图的场景现在需要插入元素14先通过哈希函数计算哈希地址hashAddr为4因此14理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。
插入通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素。 删除采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素4如果直接删除掉14查找起来可能会受影 响。因此线性探测采用标记的伪删除法来删除一个元素。 哈希表扩容是指在哈希表中插入新元素时如果桶的数量不足以容纳新元素就需要增加桶的数量。哈希表扩容的过程包括以下几个步骤 1.创建一个新的桶数组大小为原来的两倍2.将原来的桶数组中的元素重新哈希到新的桶数组中3.释放原来的桶数组。 在哈希表扩容的过程中需要重新计算每个元素在新桶数组中的位置这个过程需要消耗一定的时间。因此在设计哈希表时需要根据实际情况选择合适的桶数量以避免频繁扩容。 哈希表的负载因子是指哈希表中已经存储的元素个数与容量的数量之比。负载因子越大哈希冲突的概率就越大查找、插入和删除操作的效率也会降低。一般来说当负载因子超过某个阈值时就需要对哈希表进行扩容以保证哈希表的性能。
代码如下
namespace OpenAddress
{enum State{EMPTY,EXIST,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;};templateclass K, class Vclass HashTable{public:bool Insert(const pairK, V kv){if (Find(kv.first))return false;// 负载因子超过0.7就扩容//if ((double)_n / (double)_tables.size() 0.7)if (_tables.size() 0 || _n * 10 / _tables.size() 7){size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;HashTableK, V newht;newht._tables.resize(newsize);// 遍历旧表重新映射到新表for (auto data : _tables){if (data._state EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hashi kv.first % _tables.size();// 线性探测size_t i 1;size_t index hashi;while (_tables[index]._state EXIST){index hashi i;index % _tables.size();i;}_tables[index]._kv kv;_tables[index]._state EXIST;_n;return true;}HashDataK, V* Find(const K key){if (_tables.size() 0){return false;}size_t hashi key % _tables.size();// 线性探测size_t i 1;size_t index hashi;while (_tables[index]._state ! EMPTY){if (_tables[index]._state EXIST _tables[index]._kv.first key){return _tables[index];}index hashi i;index % _tables.size();i;// 如果已经查找一圈那么说明全是存在删除if (index hashi)break;}return nullptr;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;--_n;return true;}else{return false;}}private:vectorHashDataK, V _tables;size_t _n 0; // 存储的数据个数};
}线性探测优点实现非常简单 线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。如何缓解呢可以使用二次探索三次探索等等。当所求出key的位置被占用不去填入key1的位置而是填入key2或key3的位置这种方式叫做二次探索三次探索这样可以让表更加稀松一些就能提高效率。 当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容。
3.2 哈希表的开散列
开散列Open Hashing是另一种解决哈希冲突的方法也称为链地址法Chaining。在开散列中哈希表中的每个桶都是一个链表当发生哈希冲突时新的元素会被插入到对应桶的链表中。这种方法可以避免开放地址法中的聚集现象并且可以在空间充足的情况下实现快速查找 。 开散列增容桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可 能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。 只能存储key为整形的元素其他类型怎么解决key为字符串类型需要将其转化为整形。在将字符串类型转换为整数类型时可以使用以下方法
将字符串中的每个字符转换为其ASCII码值然后将这些值相加得到一个整数。将字符串中的每个字符转换为其ASCII码值然后将这些值相乘得到一个整数。将字符串中的每个字符转换为其ASCII码值然后将这些值按位异或得到一个整数。
代码如下
namespace HashBucket
{templateclass K, class Vstruct HashNode{HashNodeK, V* _next;pairK, V _kv;HashNode(const pairK, V kv):_next(nullptr), _kv(kv){}};templateclass Kstruct HashFunc{size_t operator()(const K key){return key;}};// 特化将字符串的情况进行一些处理templatestruct HashFuncstring{size_t operator()(const string s){size_t hash 0;for (auto ch : s){hash ch;hash * 31;}return hash;}};templateclass K, class V, class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:~HashTable(){for (auto cur : _tables){while (cur){Node* next cur-_next;delete cur;cur next;}cur nullptr;}}Node* Find(const K key){if (_tables.size() 0)return nullptr;Hash hash;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}bool Erase(const K key){Hash hash;size_t hashi hash(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}else{prev cur;cur cur-_next;}}return false;}//扩容扩质数的2倍左右size_t GetNextPrime(size_t prime){static const int __stl_num_primes 28;static const unsigned long __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};size_t i 0;for (; i __stl_num_primes; i){if (__stl_prime_list[i] prime)return __stl_prime_list[i];}return __stl_prime_list[i];}bool Insert(const pairK, V kv){if (Find(kv.first)){return false;}Hash hash;// 负载因因子1时扩容if (_n _tables.size()){size_t newsize GetNextPrime(_tables.size());vectorNode* newtables(newsize, nullptr);for (auto cur : _tables){while (cur){Node* next cur-_next;size_t hashi hash(cur-_kv.first) % newtables.size();// 头插到新表cur-_next newtables[hashi];newtables[hashi] cur;cur next;}}_tables.swap(newtables);}size_t hashi hash(kv.first) % _tables.size();// 头插Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}size_t MaxBucketSize(){size_t max 0;for (size_t i 0; i _tables.size(); i){auto cur _tables[i];size_t size 0;while (cur){size;cur cur-_next;}if (size max){max size;}}return max;}private:vectorNode* _tables; // 指针数组size_t _n 0; // 存储有效数据个数};
}2. 哈希的应用
2.1 位图
位图Bitmap是一种数据结构用于表示一个二进制向量。位图中的每个元素都只有两个可能的取值0和1。位图可以用于压缩数据减少存储空间的使用也可以用于快速查找和访问元素。 在位图中每个元素都只占用一个二进制位因此可以使用一个整数来表示多个元素。例如一个32位的整数可以表示32个元素。这种方法可以大大减少存储空间的使用并且可以在常数时间内访问和修改元素。 位图常用于处理大量数据的问题例如在搜索引擎中用于记录网页的索引信息。它还可以用于计算机网络中的路由表、缓存和防火墙等。 例如求解给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。 数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。 位图代码如下
templatesize_t N
class bitset
{
public:bitset(){_bits.resize(N/8 1, 0);}void set(size_t x){size_t i x / 8;size_t j x % 8;_bits[i] | (1 j);}void reset(size_t x){size_t i x / 8;size_t j x % 8;_bits[i] ~(1 j);}bool test(size_t x){size_t i x / 8;size_t j x % 8;return _bits[i] (1 j);}private:vectorchar _bits;
};2.2 布隆过滤器
当查找大量与字符串有关的数据时过滤掉那些已经存在的记录。 如何快速查找呢
用哈希表存储用户记录缺点浪费空间用位图存储用户记录缺点位图一般只能处理整形如果内容编号是字符串就无法处理了。将哈希与位图结合即布隆过滤器
布隆过滤器Bloom Filter是一种空间效率高、误判率低的概率型数据结构用于判断一个元素是否在一个集合中。它由一个位数组和多个哈希函数组成。位数组的长度为m哈希函数的个数为k。当一个元素被加入集合时它会被k个哈希函数映射成位数组中的k个位置将这些位置设为1。当判断一个元素是否在集合中时将这个元素进行k次哈希得到k个位置。 如果这k个位置都是1则说明这个元素在集合中如果这k个位置中有任意一个位置是0则说明这个元素不在集合中。 布隆过滤器的优点是空间效率高、查询时间短缺点是有一定的误判率和删除困难。它常用于大规模数据处理中例如网络爬虫、垃圾邮件过滤等。 布隆过滤器的查找 布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。 注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判。 比如在布隆过滤器中查找alibaba时假设3个哈希函数计算的哈希值为1、3、7刚好和其他元素的比特位重叠此时布隆过滤器告诉该元素存在但实该元素是不存在的。 布隆过滤器删除 布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。 比如删除上图中tencent元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。 一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。
布隆过滤器优点
增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关哈希函数相互之间没有关系方便硬件并行运算布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势数据量很大时布隆过滤器可以表示全集其他数据结构不能使用同一组散列函数的布隆过滤器可以进行交、并、差运算
布隆过滤器缺陷
有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据)不能获取元素本身一般情况下不能从布隆过滤器中删除元素如果采用计数方式删除可能会存在计数回绕问题
//不同的哈希映射方式
struct BKDRHash
{size_t operator()(const string s){size_t hash 0;for (auto ch : s){hash ch;hash * 31;}return hash;}
};
struct APHash
{size_t operator()(const string s){size_t hash 0;for (long i 0; i s.size(); i){size_t ch s[i];if ((i 1) 0){hash ^ ((hash 7) ^ ch ^ (hash 3));}else{hash ^ (~((hash 11) ^ ch ^ (hash 5)));}}return hash;}
};
struct DJBHash
{size_t operator()(const string s){size_t hash 5381;for (auto ch : s){hash (hash 5) ch;}return hash;}
};// N最多会插入key数据的个数
templatesize_t N,class K string,class Hash1 BKDRHash,class Hash2 APHash,class Hash3 DJBHash
class BloomFilter
{
public:void set(const K key){size_t hash1 Hash1()(key) % N;_bs.set(hash1);size_t hash2 Hash2()(key) % N;_bs.set(hash2);size_t hash3 Hash3()(key) % N;_bs.set(hash3);}bool test(const K key){size_t hash1 Hash1()(key) % N;if (!_bs.test(hash1)){return false;}size_t hash2 Hash2()(key) % N;if (!_bs.test(hash2)){return false;}size_t hash3 Hash3()(key) % N;if (!_bs.test(hash3)){return false;}return true;}
private:bitsetN _bs;
};
