拉一条宽带要多少钱,aso应用优化,百度系app,做全屏的网站 一屛多高文章目录 1. 前言2. unordered 系列关联式容器2.1 unordered_map2.1.1 unordered_map 的概念2.1.2 unordered_map 的使用 2.2 unordered_set2.2.1 unordered_set 的概念2.2.2 unordered_set 的使用 3. 底层结构3.1 哈希的概念3.2 哈希冲突3.3 哈希函数3.4 哈希冲突的解决3.4.1 … 文章目录 1. 前言2. unordered 系列关联式容器2.1 unordered_map2.1.1 unordered_map 的概念2.1.2 unordered_map 的使用 2.2 unordered_set2.2.1 unordered_set 的概念2.2.2 unordered_set 的使用 3. 底层结构3.1 哈希的概念3.2 哈希冲突3.3 哈希函数3.4 哈希冲突的解决3.4.1 闭散列3.4.2 开散列 4. 模拟实现4.1 哈希表的改造4.2 unordered_map 的模拟实现4.3 unordered_set 的模拟实现 5. 哈希的应用5.1 位图5.1.1 位图的概念5.1.2 位图的实现5.1.3 位图的应用 5.2 布隆过滤器5.2.1 布隆过滤器的提出5.2.2 布隆过滤器的概念5.2.3 布隆过滤器的实现5.2.4 布隆过滤器的优点5.2.5 布隆过滤器的缺陷 1. 前言 想象一下你有一个巨大的图书馆里面摆满了成千上万本书。如果你想要找到其中一本特定的书你会怎么做如果你按照书的编号来有序地排列它们找到特定的书本可能会很容易。但是如果书籍是随机地摆放你可能需要逐本地查找这个过程会非常耗时。 而哈希函数就像是给每本书分配一个独特的编号然后将它们放置在合适的位置使得我们能够快速地找到并访问它们。哈希函数能够将输入数据映射到一个固定大小的哈希表中每个元素都有一个唯一的位置。当我们需要查找特定的元素时只需使用哈希函数计算出它的位置然后直接访问该位置的元素无需遍历整个数据集。 这种基于哈希的快速查找技术在现代编程中非常常见。在本篇博客中我们将深入剖析哈希相关的知识点。 本篇文章将着重讲解 unordered 系列关联式容器unordered_map 和 unordered_set、底层结构哈希的概念、哈希函数、哈希冲突、模拟实现unordered_map 和 unordered_set 的模拟实现以及哈希的应用位图和布隆过滤器。 2. unordered 系列关联式容器 在 C98 中STL 提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到 l o g 2 N log_2N log2N即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好的查询是进行很少的比较次数就能够将元素找到因此在 C11 中STL又提供了4个 unordered 系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同本文中只对 unordered_map 和 unordered_set 进行介绍。 2.1 unordered_map
2.1.1 unordered_map 的概念 英文解释 也就是说 unordered_map 是存储 key, value 键值对的关联式容器其允许通过 key 快速的索引到与其对应的 value。 在 unordered_map 中键值通常用于唯一地标识元素而映射值是一个对象其内容与此键关联。键和映射值的类型可能不同。 在内部unordered_map 没有对 key, value 按照任何特定的顺序排序, 为了能在常数范围内找到 key 所对应的 valueunordered_map 将相同哈希值的键值对放在相同的桶中。 unordered_map 容器通过 key 访问单个元素要比 map 快但它通常在遍历元素子集的范围迭代方面效率较低。 unordered_map 实现了直接访问操作符operator[]它允许使用 key 作为参数直接访问 value。 它的迭代器至少是单向迭代器。 2.1.2 unordered_map 的使用 unordered_map 的模板参数列表 说明 key键值对中 key 的类型。T键值对中 value 的类型。Hash哈希函数用于确定元素在内部数据结构中的位置。Pred键相等判断函数用于比较两个键是否相等。Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器。 unordered_map 的构造函数 函数声明功能介绍unordered_map构造不同格式的 unordered_map 对象。 unordered_map 的容量操作 函数名称函数声明功能简介emptybool empty () const;检测 unordered_map 中的元素是否为空是返回 true否则返回 false。sizesize_t size() const;返回 unordered_map 中有效元素的个数。 unordered_map 的元素访问操作 函数名称函数声明功能简介operator[]mapped_type operator[] (const key_type k);返回 k 对应的 value。atmapped_type at (const key_type k);const mapped_type at (const key_type k) const;返回 k 对应的 value。 区分 在元素访问时有一个与 operator[] 类似的操作 at 函数该函数不常用都是通过 key 找到与 key 对应的 value 然后返回其引用不同的是当 key 不存在时operator[] 用默认 value 与 key 构造键值对然后插入返回该默认 valueat 函数直接抛异常。 unordered_map 的查找操作 函数名称函数声明功能介绍finditerator find (const key_type k);const_iterator find (const key_type k) const;在 unordered_map 中查找 key 为 k 的元素找到返回该元素位置的迭代器否则返回 end。在 unordered_map 中查找 key 为 k 的元素找到返回该元素位置的 const 迭代器否则返回 cend。countsize_t count (const key_type k) const;返回 unordered_map 中值为 k 的键值在 map 中的个数这里只会返回0或1。 unordered_map 的修改操作 函数名称函数声明功能介绍insertpairiterator,bool insert (const value_type val);在 unordered_map 中插入键值对 val。如果插入成功返回 val 位置的迭代器true如果插入失败说明 val 在 unordered_map 中已经存在返回 val 位置的迭代器false。eraseiterator erase (const_iterator position);size_t erase (const key_type k);删除 unordered_map 中 position 位置上的元素并返回一个指向被删除元素之后位置的迭代器。删除 unordered_map 中键值为 k 的元素返回删除的元素的个数这里只会返回0或1。swapvoid swap (unordered_map ump);与 ump 交换元素。clearvoid clear();将 map 的元素清空。 unordered_map 的桶操作 函数名称函数声明功能介绍bucket_countsize_t bucket_count() const返回哈希桶中桶的总个数。bucket_sizesize_t bucket_size(size_t n) const返回 n 号桶中有效元素的总个数。bucketsize_t bucket(const key_type k)返回元素 k 所在的桶号。
2.2 unordered_set
2.2.1 unordered_set 的概念 英文解释 也就是说 unordered_set 是一种容器它以无特定顺序存储唯一元素并且允许根据 value 快速检索单个元素。 在 unordered_set 中元素的 value 同时也是唯一标识它的 key。键是不可变的因此在容器中的元素一旦插入就不能修改尽管可以插入和删除。 在内部unordered_set 中的元素没有按照任何特定的顺序排序而是根据它们的哈希值被组织到不同的桶中以便能够通过值快速直接地访问单个元素平均情况下具有常数时间复杂度。 与集合容器相比unordered_set 容器更快地通过 key 访问单个元素尽管对于对子集进行范围迭代它们通常不太高效。 容器中的迭代器至少是单向迭代器。 2.2.2 unordered_set 的使用 unordered_set 的模板参数列表 说明 Tunordered_set 中存放元素的类型。 Hash哈希函数用于确定元素在内部数据结构中的位置。 Pred键相等判断函数用于比较两个键是否相等。 Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器。 unordered_set 的构造函数 函数声明功能介绍unordered_set构造不同格式的 unordered_set 对象。 unordered_set 的容量操作 函数名称函数声明功能介绍emptybool empty() const;检测 unordered_set 是否为空空返回 true否则返回 false。sizesize_t size() const;返回 unordered_set 中有效元素的个数。 unordered_set 的查找操作 函数名称函数声明功能介绍finditerator find (const value_type val) const;在 unordered_set 中查找值为 val 的元素如果找到则返回该元素位置的迭代器未找到则返回 end 迭代器。countsize_t count (const value_type val) const;返回 unordered_set 中值为 val 的元素的个数这里只会返回0或1。 unordered_set 的修改操作 函数名称函数声明功能介绍insertpairiterator,bool insert (const value_type val);在 unordered_set 中插入元素 val。如果插入成功返回 val 位置的迭代器true如果插入失败说明 val 在 unordered_set 中已经存在返回 val 位置的迭代器false。eraseiterator erase (const_iterator position);size_t erase (const value_type val);删除 unordered_set 中 position 位置上的元素并返回一个指向被删除元素之后位置的迭代器。删除 unordered_set 中值为 val 的元素返回删除的元素的个数这里只会返回0或1。swapvoid swap (unordered_set ust);与 ust 交换元素。clearvoid clear();将 unordered_set 的元素清空。 unordered_set 的桶操作 函数名称函数声明功能介绍bucket_countsize_t bucket_count() const返回哈希桶中桶的总个数。bucket_sizesize_t bucket_size(size_t n) const返回 n 号桶中有效元素的总个数。bucketsize_t bucket(const key_type k)返回元素 k 所在的桶号。
3. 底层结构
3.1 哈希的概念 顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O( l o g 2 N log_2 N log2N)搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数hashFunc使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。 当向该结构中 插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放。 搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功。 该方式即为哈希散列方法哈希方法中使用的转换函数称为哈希散列函数构造出来的结构称为哈希表Hash Table或者称散列表。 例如 数据集合{ 1,7,6,4,5,9 }; 哈希函数设置为hash(key) key % capacity;capacity 为存储元素底层空间总的大小 图解 注用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快。 3.2 哈希冲突 对于两个数据元素的关键字 k i k_i ki 和 k j k_j kji ! j有 k i k_i ki ! k j k_j kj但有Hash( k i k_i ki) Hash( k j k_j kj)即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为同义词。 发生哈希冲突该如何处理呢 3.3 哈希函数 引起哈希冲突的一个原因可能是哈希函数设计不够合理。 哈希函数设计原则 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有 m 个地址时其值域必须在 0 到 m-1 之间。哈希函数计算出来的地址能均匀分布在整个空间中。哈希函数应该比较简单。 常见哈希函数 直接定址法常用 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀。 缺点需要事先知道关键字的分布情况。 使用场景适合查找比较小且连续的情况。 除留余数法常用 设散列表中允许的地址数为 m取一个不大于 m但最接近或者等于 m 的质数 p 作为除数按照哈希函数Hash(key) key % p(pm)将关键码转换成哈希地址。 平方取中法了解 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址再比如关键字为4321对它平方就是18671041抽取中间的3位671或710作为哈希地址。 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况。 折叠法了解 折叠法是将关键字从左到右分割成位数相等的几部分最后一部分位数可以短些然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况。 随机数法了解 选择一个随机函数取关键字的随机函数值为它的哈希地址即 H(key) random(key)其中 random 为随机数函数。 随机数法通常应用于关键字长度不等时。 数学分析法了解 设有 n 个 d 位数每一位可能有 r 种不同的符号这 r 种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。例如 假设要存储某家公司员工登记表如果用手机号作为关键字那么极有可能前7位都是相同的那么我们可以选择后面的四位作为散列地址如果这样的抽取工作还容易出现冲突还可以对抽取出来的数字进行反转如1234改成4321、右环位移如1234改成4123、左环移位、前两数与后两数叠加如1234改成123446等方法。 数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。 拓展字符串Hash函数链接。 注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突。 3.4 哈希冲突的解决 解决哈希冲突两种常见的方法是闭散列和开散列。 3.4.1 闭散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有 空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 呢 线性探测 比如3.1中的场景现在需要插入元素44先通过哈希函数计算哈希地址hashAddr 为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 插入 通过哈希函数获取待插入元素在哈希表中的位置。如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素。 删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。 比如删除元素4如果直接删除掉44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。 像这样 // 哈希表每个空间给个标记
// EMPTY此位置空 EXIST此位置已经有元素 DELETE元素已经删除
enum State {EMPTY, EXIST, DELETE};思考哈希表什么情况下进行扩容如何扩容 线性探测的实现 templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 字符串哈希函数特化HashFuncstring
template
struct HashFuncstd::string
{size_t operator()(const string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}return hash;}
};namespace open_address
{enum Status{EMPTY,EXIST,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;Status _s; //状态};templateclass K, class V, class Hash HashFuncKclass HashTable{public:HashTable(){_tables.resize(10);}bool Insert(const pairK, V kv){if (Find(kv.first))return false;// 负载因子0.7就扩容if (_n * 10 / _tables.size() 7){size_t newSize _tables.size() * 2;HashTableK, V, Hash newHT;newHT._tables.resize(newSize);// 遍历旧表for (size_t i 0; i _tables.size(); i){if (_tables[i]._s EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hf;// 线性探测size_t hashi hf(kv.first) % _tables.size();while (_tables[hashi]._s EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._s EXIST;_n;return true;}HashDataK, V* Find(const K key){Hash hf;size_t hashi hf(key) % _tables.size();while (_tables[hashi]._s ! EMPTY){if (_tables[hashi]._s EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();}return nullptr;}// 伪删除法bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_s DELETE;--_n;return true;}else{return false;}}// 打印观察分布void Print(){for (size_t i 0; i _tables.size(); i){if (_tables[i]._s EXIST){cout [ i ]- _tables[i]._kv.first : _tables[i]._kv.second endl;}else if (_tables[i]._s EMPTY){printf([%zd]-\n, i);}else{printf([%zd]-D\n, i);}}cout endl;}private:vectorHashDataK, V _tables;size_t _n 0; // 存储的关键字的个数};
}线性探测优点实现非常简单。 线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据堆积即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。 二次探测 线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 H i H_i Hi ( H 0 H_0 H0 i 2 i^2 i2 )% m或者 H i H_i Hi ( H 0 H_0 H0 - i 2 i^2 i2 )% m。其中i 1,2,3,… H 0 H_0 H0 是通过散列函数 Hash(x) 对元素的关键码 key 进行计算得到的位置m 是表的大小。 对于3.1中如果要插入44产生冲突使用解决后的情况为 研究表明当表的长度为质数且表装载因子 a 不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子 a 不超过0.5如果超出必须考虑增容。 因此闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。
3.4.2 开散列 开散列概念 开散列法又叫链地址法开链法首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。 开散列增容 桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容那该条件怎么确认呢开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。 开散列实现 templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 字符串哈希函数特化HashFuncstring
template
struct HashFuncstd::string
{size_t operator()(const string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}return hash;}
};namespace hash_bucket
{templateclass K, class Vstruct HashNode{HashNode* _next;pairK, V _kv;HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}};templateclass K, class V, class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:HashTable(){_tables.resize(10);}~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}size_t Size() const{return _n;}bool Empty() const{return _n 0;}bool Insert(const pairK, V kv){if (Find(kv.first))return false;Hash hf;// 负载因子最大到1if (_n _tables.size()){vectorNode* newTables;newTables.resize(_tables.size() * 2, nullptr);// 遍历旧表for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;// 挪动到映射的新表size_t hashi hf(cur-_kv.first) % newTables.size();cur-_next newTables[i];newTables[i] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi hf(kv.first) % _tables.size();Node* newnode new Node(kv);// 头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}bool Erase(const K key){Hash hf;size_t hashi hf(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;}prev cur;cur cur-_next;}return false;}Node* Find(const K key){Hash hf;size_t hashi hf(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}size_t Count(const K key){Hash hf;KeyOfT kot;size_t hashi hf(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){return 1;}cur cur-_next;}return 0;}// 桶的总个数size_t BucketCount(){size_t bucketCount 0;for (size_t i 0; i _tables.size(); i){if (_tables[i]){bucketCount;}}return bucketCount;}// key所在桶的大小size_t BucketSize(const K key){Hash hf;size_t bucketSize 0;size_t hashi hf(key) % _tables.size();Node* cur _tables[hashi];while (cur){bucketSize;cur cur-_next;}return bucketSize;}// 打印信息void Some(){size_t bucketSize 0;size_t maxBucketLen 0;size_t sum 0;double averageBucketLen 0;for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];if (cur){bucketSize;}size_t bucketLen 0;while (cur){bucketLen;cur cur-_next;}sum bucketLen;if (bucketLen maxBucketLen){maxBucketLen bucketLen;}}averageBucketLen (double)sum / (double)bucketSize;printf(all bucketSize:%d\n, _tables.size());printf(bucketSize:%d\n, bucketSize);printf(maxBucketLen:%d\n, maxBucketLen);printf(averageBucketLen:%lf\n\n, averageBucketLen);}private:vectorNode* _tables;size_t _n 0;};
}开散列与闭散列比较 应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 0.5而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间。 4. 模拟实现
4.1 哈希表的改造 模板参数列表的改造 // K关键码类型
// T不同容器T的类型不同如果是unordered_mapT代表一个键值对如果是unordered_set,T为K。
// KeyOfT因为T的类型不同通过value取key的方式就不同详细见unordered_map/set的实现。
// Hash哈希函数仿函数对象类型哈希函数使用除留余数法需要将Key转换为整型数字才能取模。
templateclass T
struct HashNode
{HashNodeT* _next;T _data;HashNode(const T data):_data(data), _next(nullptr){}
};
templateclass K, class T, class KeyOfT, class Hash
class HashTable;增加迭代器操作 templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash
struct __HTIterator
{typedef HashNodeT Node;typedef __HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self;Node* _node;const HashTableK, T, KeyOfT, Hash* _pht;size_t _hashi;__HTIterator(Node* node, HashTableK, T, KeyOfT, Hash* pht, size_t hashi):_node(node), _pht(pht), _hashi(hashi){}__HTIterator(Node* node, const HashTableK, T, KeyOfT, Hash* pht, size_t hashi):_node(node), _pht(pht), _hashi(hashi){}Self operator(){if (_node-_next){// 当前桶还有节点走到下一个节点_node _node-_next;}else{// 当前桶已经走完了找下一个桶开始_hashi;while (_hashi _pht-_tables.size()){if (_pht-_tables[_hashi]){_node _pht-_tables[_hashi];break;}_hashi;}if (_hashi _pht-_tables.size()){_node nullptr;}}return *this;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}
};改造后代码实现 templateclass K, class T, class KeyOfT, class Hash
class HashTable
{typedef HashNodeT Node;templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashfriend struct __HTIterator;public:typedef __HTIteratorK, T, T, T*, KeyOfT, Hash iterator;typedef __HTIteratorK, T, const T, const T*, KeyOfT, Hash const_iterator;iterator begin(){for (size_t i 0; i _tables.size(); i){if (_tables[i]){return iterator(_tables[i], this, i);}}return end();}iterator end(){return iterator(nullptr, this, -1);}const_iterator begin() const{for (size_t i 0; i _tables.size(); i){if (_tables[i]){return const_iterator(_tables[i], this, i);}}return end();}const_iterator end() const{return const_iterator(nullptr, this, -1);}HashTable(){_tables.resize(10);}~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}size_t Size() const{return _n;}bool Empty() const{return _n 0;}pairiterator, bool Insert(const T data){Hash hf;KeyOfT kot;iterator it Find(kot(data));if (it ! end())return make_pair(it, false);// 负载因子最大到1if (_n _tables.size()){vectorNode* newTables;newTables.resize(_tables.size() * 2, nullptr);// 遍历旧表for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;// 挪动到映射的新表size_t hashi hf(kot(cur-_data)) % newTables.size();cur-_next newTables[i];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi hf(kot(data)) % _tables.size();Node* newnode new Node(data);// 头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return make_pair(iterator(newnode, this, hashi), true);}bool Erase(const K key){Hash hf;KeyOfT kot;size_t hashi hf(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}prev cur;cur cur-_next;}return false;}iterator Find(const K key){Hash hf;KeyOfT kot;size_t hashi hf(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur, this, hashi);}cur cur-_next;}return end();}size_t Count(const K key){Hash hf;KeyOfT kot;size_t hashi hf(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){return 1;}cur cur-_next;}return 0;}// 桶的总个数size_t BucketCount(){size_t bucketCount 0;for (size_t i 0; i _tables.size(); i){if (_tables[i]){bucketCount;}}return bucketCount;}// key所在桶的大小size_t BucketSize(const K key){Hash hf;size_t bucketSize 0;size_t hashi hf(key) % _tables.size();Node* cur _tables[hashi];while (cur){bucketSize;cur cur-_next;}return bucketSize;}// 打印信息void Some(){size_t bucketSize 0;size_t maxBucketLen 0;size_t sum 0;double averageBucketLen 0;for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];if (cur){bucketSize;}size_t bucketLen 0;while (cur){bucketLen;cur cur-_next;}sum bucketLen;if (bucketLen maxBucketLen){maxBucketLen bucketLen;}}averageBucketLen (double)sum / (double)bucketSize;printf(all bucketSize:%zd\n, _tables.size());printf(bucketSize:%zd\n, bucketSize);printf(maxBucketLen:%zd\n, maxBucketLen);printf(averageBucketLen:%lf\n\n, averageBucketLen);}private:vectorNode* _tables;size_t _n 0;
};4.2 unordered_map 的模拟实现 unordered_map 的底层结构就是哈希表因此在 unordered_map 中直接封装一个哈希表然后将其接口包装下即可。 代码实现如下 #pragma once
#includeHashTable.hnamespace my_unordered_map
{templateclass K, class V, class Hash HashFuncKclass unordered_map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}size_t size() const{return _ht.Size();}bool empty() const{return _ht.Empty();}pairiterator, bool insert(const pairK, V kv){return _ht.Insert(kv);}bool erase(const K key){return _ht.Erase(key);}V operator[](const K key){pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}const V operator[](const K key) const{pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}iterator find(const K key){return _ht.Find(key);}size_t count(const K key){return _ht.Count(key);}size_t bucket_count(){return _ht.BucketCount();}size_t bucket_size(const K key){return _ht.BucketSize(key);}private:hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;};
}4.3 unordered_set 的模拟实现 unordered_set 的底层结构就是哈希表因此在 unordered_set 中直接封装一个哈希表然后将其接口包装下即可。 代码实现如下 #pragma once
#includeHashTable.hnamespace my_unordered_set
{templateclass K, class Hash HashFuncKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename hash_bucket::HashTableK, K, SetKeyOfT, Hash::const_iterator iterator;typedef typename hash_bucket::HashTableK, K, SetKeyOfT, Hash::const_iterator const_iterator;iterator begin() const{return _ht.begin();}iterator end() const{return _ht.end();}size_t size() const{return _ht.Size();}bool empty() const{return _ht.Empty();}pairconst_iterator, bool insert(const K key){auto ret _ht.Insert(key);return pairconst_iterator, bool(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);}bool erase(const K key){return _ht.Erase(key);}iterator find(const K key){auto ret _ht.Find(key);return const_iterator(ret._node, ret._pht, ret._hashi);}size_t count(const K key){return _ht.Count(key);}size_t bucket_count(){return _ht.BucketCount();}size_t bucket_size(const K key){return _ht.BucketSize(key);}private:hash_bucket::HashTableK, K, SetKeyOfT, Hash _ht;};
}5. 哈希的应用
5.1 位图
5.1.1 位图的概念 所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。 来看一个问题 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中 遍历 O ( N ) O(N) O(N) 排序 O ( N l o g 2 N ) O(Nlog_2N) O(Nlog2N) 二分查找 O ( l o g 2 N ) O(log_2N) O(log2N) 位图解决 数据是否在给定的整型数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息。如果二进制比特位为1则代表存在二进制比特位为0则代表不存在。 比如 5.1.2 位图的实现
namespace my_bitset
{// N是需要多少比特位templatesize_t Nclass bitset{public:bitset(){_bits.resize((N 5) 1, 0);}void set(size_t x){size_t i x / 32;size_t j x % 32;_bits[i] | (1 j);}void reset(size_t x){size_t i x / 32;size_t j x % 32;_bits[i] ~(1 j);}bool test(size_t x){size_t i x / 32;size_t j x % 32;return _bits[i] (1 j);}private:vectorint _bits;};
}5.1.3 位图的应用 快速查找某个数据是否在一个集合中。 排序 去重。 求两个集合的交集、并集等。 操作系统中磁盘块标记。 以下面三个题为例 给定100亿个整数设计算法找到只出现一次的整数 给两个文件分别有100亿个整数我们只有 1G 内存如何找到两个文件交集 位图应用变形1个文件有100亿个 int1G 内存设计算法找到出现次数不超过2次的所有整数。 思路解答 创建两个位图遍历给定的100亿个整数。对于每个整数如果出现一次则将两个位图中对应位置分别置成01如果出现零次、二次及以上则将两个位图中对应位置分别置成00、10或11最后再次遍历位图找到位图位置对应的值为01的整数。将两个文件中的整数分别映射到两个位图中。然后遍历其中一个位图对于每个整数查询另一个位图如果对应位置的值为1则表示该整数存在于两个文件中即为所求交集。创建两个位图初始化所有位为0。然后遍历给定的100亿个整数对于每个整数将其对应的位图位置的值加1这里加1指的是调整两个位图对应位置组合成的数加1。最后再次遍历位图找到位图位置对应的值不超过2的整数。 5.2 布隆过滤器
5.2.1 布隆过滤器的提出 我们在使用新闻客户端看新闻时它会给我们不停地推荐新的内容它每次推荐时要去重去掉那些已经看过的内容。问题来了新闻客户端推荐系统如何实现推送去重的 用服务器记录了用户看过的所有历史记录当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选过滤掉那些已经存在的记录。 如何快速查找呢 用哈希表存储用户记录缺点浪费空间。 用位图存储用户记录缺点位图一般只能处理整型如果内容编号是字符串就无法处理了。 将哈希与位图结合即布隆过滤器。 5.2.2 布隆过滤器的概念 布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你某样东西一定不存在或者可能存在它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。 5.2.3 布隆过滤器的实现 布隆过滤器的插入 往布隆过滤器增加元素添加的 key 需要根据 k 个无偏 hash 函数计算得到多个 hash 值然后对数组长度进行取模得到数组下标的位置然后将对应数组下标的位置的值置为1。 布隆过滤器的查找 布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找 分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。 注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判。 比如在布隆过滤器中查找alibaba时假设3个哈希函数计算的哈希值为1、3、7刚好和其他元素的比特位重叠此时布隆过滤器告诉该元素存在但实该元素是不存在的。 布隆过滤器的删除 布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。 比如删除上图中tencent元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。 一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器。插入元素时给 k 个计数器k 个哈希函数计算出的哈希地址加一删除元素时给 k 个计数器减一。这样通过多占用几倍存储空间的代价来增加删除操作。 具体实现代码 #pragma once
#includebitset.hstruct BKDRHash
{size_t operator()(const string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}return hash;}
};struct APHash
{size_t operator()(const string key){size_t hash 0;for (size_t i 0; i key.size(); i){char ch key[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 key){size_t hash 5381;for (auto ch : key){hash (hash 5) ch;}return hash;}
};templatesize_t N,class K string,class HashFunc1 BKDRHash,class HashFunc2 APHash,class HashFunc3 DJBHash
class BloomFilter
{
public:void Set(const K key){size_t hash1 HashFunc1()(key) % N;size_t hash2 HashFunc2()(key) % N;size_t hash3 HashFunc3()(key) % N;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool Test(const K key){// 判断不存在是准确的size_t hash1 HashFunc1()(key) % N;if (_bs.test(hash1) false)return false;size_t hash2 HashFunc2()(key) % N;if (_bs.test(hash2) false)return false;size_t hash3 HashFunc3()(key) % N;if (_bs.test(hash3) false)return false;// 存在误判的return true;}private:my_bitset::bitsetN _bs;
};5.2.4 布隆过滤器的优点 增加和查询元素的时间复杂度为: O ( K ) O(K) O(K), K K K为哈希函数的个数一般比较小与数据量大小无关。 哈希函数相互之间没有关系方便硬件并行运算。 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势。 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势。 数据量很大时布隆过滤器可以表示全集其他数据结构不能。 使用同一组散列函数的布隆过滤器可以进行交、并、差运算。 5.2.5 布隆过滤器的缺陷 有误判率即存在假阳性False Position即不能准确判断元素是否在集合中。补救方法再建立一个白名单存储可能会误判的数据 不能获取元素本身。 一般情况下不能从布隆过滤器中删除元素。 如果采用计数方式删除可能会存在计数回绕问题。
文章转载自： http://www.morning.bzkgn.cn.gov.cn.bzkgn.cn http://www.morning.juju8.cn.gov.cn.juju8.cn http://www.morning.mwhqd.cn.gov.cn.mwhqd.cn http://www.morning.xhjjs.cn.gov.cn.xhjjs.cn http://www.morning.hnhgb.cn.gov.cn.hnhgb.cn http://www.morning.zzgkk.cn.gov.cn.zzgkk.cn http://www.morning.bmgdl.cn.gov.cn.bmgdl.cn http://www.morning.rdlxh.cn.gov.cn.rdlxh.cn http://www.morning.hmbtb.cn.gov.cn.hmbtb.cn http://www.morning.qfdyt.cn.gov.cn.qfdyt.cn http://www.morning.vattx.cn.gov.cn.vattx.cn http://www.morning.plkrl.cn.gov.cn.plkrl.cn http://www.morning.mjzcp.cn.gov.cn.mjzcp.cn http://www.morning.tfrmx.cn.gov.cn.tfrmx.cn http://www.morning.beiyishengxin.cn.gov.cn.beiyishengxin.cn http://www.morning.hpxxq.cn.gov.cn.hpxxq.cn http://www.morning.dkqyg.cn.gov.cn.dkqyg.cn http://www.morning.snktp.cn.gov.cn.snktp.cn http://www.morning.lwwnq.cn.gov.cn.lwwnq.cn http://www.morning.ygflz.cn.gov.cn.ygflz.cn http://www.morning.fdxhk.cn.gov.cn.fdxhk.cn http://www.morning.nqdkx.cn.gov.cn.nqdkx.cn http://www.morning.cnyqj.cn.gov.cn.cnyqj.cn http://www.morning.rrcrs.cn.gov.cn.rrcrs.cn http://www.morning.qwqzk.cn.gov.cn.qwqzk.cn http://www.morning.pmghz.cn.gov.cn.pmghz.cn http://www.morning.cklld.cn.gov.cn.cklld.cn http://www.morning.qxmpp.cn.gov.cn.qxmpp.cn http://www.morning.mhbcy.cn.gov.cn.mhbcy.cn http://www.morning.xrqkm.cn.gov.cn.xrqkm.cn http://www.morning.gsjw.cn.gov.cn.gsjw.cn http://www.morning.thbnt.cn.gov.cn.thbnt.cn http://www.morning.lhqw.cn.gov.cn.lhqw.cn http://www.morning.kkzwn.cn.gov.cn.kkzwn.cn http://www.morning.rgnq.cn.gov.cn.rgnq.cn http://www.morning.pbgnx.cn.gov.cn.pbgnx.cn http://www.morning.tssmk.cn.gov.cn.tssmk.cn http://www.morning.cwgfq.cn.gov.cn.cwgfq.cn http://www.morning.rrxnz.cn.gov.cn.rrxnz.cn http://www.morning.kpcjl.cn.gov.cn.kpcjl.cn http://www.morning.rsxw.cn.gov.cn.rsxw.cn http://www.morning.gcrlb.cn.gov.cn.gcrlb.cn http://www.morning.rxrw.cn.gov.cn.rxrw.cn http://www.morning.qbksx.cn.gov.cn.qbksx.cn http://www.morning.btmwd.cn.gov.cn.btmwd.cn http://www.morning.mflhr.cn.gov.cn.mflhr.cn http://www.morning.wynnb.cn.gov.cn.wynnb.cn http://www.morning.nkwgy.cn.gov.cn.nkwgy.cn http://www.morning.ctqlq.cn.gov.cn.ctqlq.cn http://www.morning.qmzhy.cn.gov.cn.qmzhy.cn http://www.morning.nfmlt.cn.gov.cn.nfmlt.cn http://www.morning.hyjpl.cn.gov.cn.hyjpl.cn http://www.morning.hwpcm.cn.gov.cn.hwpcm.cn http://www.morning.lyjwb.cn.gov.cn.lyjwb.cn http://www.morning.tgyqq.cn.gov.cn.tgyqq.cn http://www.morning.qpnb.cn.gov.cn.qpnb.cn http://www.morning.nbhft.cn.gov.cn.nbhft.cn http://www.morning.gmplp.cn.gov.cn.gmplp.cn http://www.morning.xbhpm.cn.gov.cn.xbhpm.cn http://www.morning.yqgbw.cn.gov.cn.yqgbw.cn http://www.morning.hqllx.cn.gov.cn.hqllx.cn http://www.morning.jbxmb.cn.gov.cn.jbxmb.cn http://www.morning.rnht.cn.gov.cn.rnht.cn http://www.morning.pwghp.cn.gov.cn.pwghp.cn http://www.morning.xnkh.cn.gov.cn.xnkh.cn http://www.morning.ctwwq.cn.gov.cn.ctwwq.cn http://www.morning.blqsr.cn.gov.cn.blqsr.cn http://www.morning.wfjyn.cn.gov.cn.wfjyn.cn http://www.morning.brzlp.cn.gov.cn.brzlp.cn http://www.morning.yqkmd.cn.gov.cn.yqkmd.cn http://www.morning.ltspm.cn.gov.cn.ltspm.cn http://www.morning.nxrgl.cn.gov.cn.nxrgl.cn http://www.morning.tyrlk.cn.gov.cn.tyrlk.cn http://www.morning.cdrzw.cn.gov.cn.cdrzw.cn http://www.morning.rdng.cn.gov.cn.rdng.cn http://www.morning.mgwpy.cn.gov.cn.mgwpy.cn http://www.morning.mjqms.cn.gov.cn.mjqms.cn http://www.morning.kldtf.cn.gov.cn.kldtf.cn http://www.morning.sjgsh.cn.gov.cn.sjgsh.cn http://www.morning.gjxr.cn.gov.cn.gjxr.cn
