哈希与 unordered 系列关联式容器

1.unordered 系列关联式容器STL 提供了底层为红黑树结构的一系列关联式容器查询效率可达log2n最差也是比较红黑树高度次当树中结点较多时查询效率也不理想。因此又提供了4个 unordered 系列的关联式容器。1.1 unordered_mapunordered_map 是存储key value键值对的关联式容器其允许通过 key 快速索引到与其对应的 value。unordered_map 没对键值按照特定的顺序排序将相同哈希值的键值对放在相同的桶中。1.2 unordered_set使用与 unordered_map相似不做展示。2.底层结构——哈希:2.1顺序结构以及平衡树中元素关键码与其存储位置之间没有对应关系查找元素时需要经过关键码的多次比较顺序查找时间复杂度为O(n)树结构为O(log2N)搜索效率取决于搜索过程中元素的比较次数。哈希可以不经过任何比较一次直接从表中得到要搜索的元素。构造一种存储结构通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射关系那么便可以很快找到要搜索的元素。当向该结构中插入元素根据待插入元素的关键码以此函数计算出元素的存储位置并按此位置进行存放搜索元素对关键码进行同样计算把求得的函数值当作元素的存储位置在结构中按此位置取元素比较若value值相同则搜索成功。该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(或散列表)。例如数据集合{1、7、6、4、5、9}哈希函数设置为hash(key) key % capacitycapacity 为存储元素底层空间总的的大小。2.2哈希冲突不同关键字通过相同哈希函数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。2.3哈希函数直接定址法取关键字的某个线性函数为散列地址hash(key) A*key B。除留余数法设散列表中允许地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数hash(key) key % p(pm)将关键码转为哈希地址。平方取中法、折叠法、随机数法、数学分析法(了解)。哈希函数设计原则哈希函数的定义域需包含存储到全部关键码如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单。哈希函数只能减少产生冲突都可能性无法避免。2.4哈希冲突解决两种常见的方法闭散列和开散列2.4.1闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置的“下一个”空位置中去。线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。插入通过哈希函数获取待插入元素在哈希表中的位置如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素。删除采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有元素若直接删除会影响其他元素搜索。比如删除元素444查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。enum State { EMPTY, EXIST, DELETE };//哈希表每个空间给个标记线性探测优点一旦发生哈希冲突所有冲突连在一起容易产生数据堆积即不同关键码占据了可利用的空位置使得寻找没关键码的位置需要许多次比较导致搜索效率降低。二次探测线性探测的缺陷是产生冲突的数据堆积在一块这与其下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找找下一个空位置的方法为h_i (h_0 i ^2) % m或者h_i (h_0 - i^2) % m。其中i 1、2、3...h_0是通过散列函数hash(x)对元素的关键码key进行计算得到的位置m是表的大小。当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满问题在插入时需确保装载因子a不超过0.5超过需考虑增容闭散列空间利用率低。2.4.2开散列又叫拉链法首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集和每个子集和称为一个桶各个桶的元素通过一个单链表链接起来各个链表头结点存储在哈希表中。开散列中每个桶中都是发生哈希冲突的元素。开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。3.模拟实现3.1开放定址法#pragma once #includevector #includestring using namespace std; templateclass K struct DefaultHashFunc { size_t operator()(const K key) { return (size_t)key; } }; //struct stringhsahfunc //{ // size_t operator()(const string str) // { // return str[0]; // } //}; //模板特化 template struct DefaultHashFuncstring { size_t operator()(const string str) { return str[0]; } }; namespace open_address { enum STATE { EXIST, EMPTY, DELETE }; templateclass K, class V struct HashData { pairK, V _kv; STATE _state EMPTY; }; templateclass K, class V, class HashFunc DefaultHashFuncK class HashTable { public: HashTable() { _table.resize(10); } bool Insert(const pairK, V kv) { if (Find(kv.first)) { return false; } //扩容 if (_n * 10 / _table.size() 7) { size_t newSize _table.size() * 2; HashTableK, V newHT; newHT._table.resize(newSize); //遍历旧表插入新表 for (size_t i 0; i _table.size(); i) { if (_table[i]._state EXIST) { newHT.Insert(_table[i]._kv); } } _table.swap(newHT._table); } //线性探测 HashFunc hf; size_t hashi hf(kv.first) % _table.size(); while (_table[hashi]._state EXIST) { hashi; hashi % _table.size(); } _table[hashi]._kv kv; _table[hashi]._state EXIST; _n; return true; } HashDataconst K, V* Find(const K key) { HashFunc hf; size_t hashi hf(key) % _table.size(); while (_table[hashi]._state ! EMPTY) { if (_table[hashi]._state EXIST _table[hashi]._kv.first key) { return (HashDataconst K, V*) _table[hashi]; } hashi; hashi % _table.size(); } return nullptr; } bool Erase(const K key) { HashDataconst K, V* ret Find(key); if (ret) { ret-_state DELETE; --_n; return true; } return false; } private: vectorHashDataK, V _table; size_t _n;//存储有效数据的个数 }; }3.2拉链法namespace hash_bucket { templateclass K, class V struct HashNode { pairK, V _kv; HashNodeK, V* _next; HsahNode(const pairK, V kv) :_kv(kv) ,_next(nullptr) {} }; templateclass K, class V, class HashFunc DefaultHashFuncK class HashTable { typedef HashNodeK, V Node; public: HashTable() { _table.resize(10, nullptr); } ~HashTable() { for (size_t i 0; i _table.size(); i) { Node* cur _table[i]; while (cur) { Node* cur cur-_next; delete cur; cur next; } _table[i] nullptr; } } bool Insert(const pairK, V kv) { if (Find(kv.first)) { return false; } HashFunc hf; if (_n _table.size()) { size_t newSize _table.size() * 2; vectorNode* newTable; newTable.resize(newSize, nullptr); //遍历旧表把结点挂在新表 for (size_t i 0; i _table.size(); i) { Node* cur _table[i]; while (cur) { Node* next cur-_next; //头插到新表 size_t hashi hf(cur-_kv.first) % newSize; cur-_next newTable[hashi]; newTable[hashi] cur; cur next; } _table[i] nullptr; } _table.swap(newTable); } size_t hashi hf(kv.first) % _table.size(); //头插 Node* newnode new Node(kv); newnode-_next _table[hashi]; _table[hashi] newnode; _n; return true; } Node* Find(const K key) { HashFunc hf; size_t hashi hf(key) % _table.size(); Node* cur _table[hashi]; while (cur) { if (cur-_kv.first key) { return cur; } cur cur-_next; } return nullptr; } bool Erase(const K key) { HashFunc hf; size_t hashi hf(key) % _table.size(); Node* prev nullptr; Node* cur _table[hashi]; while (cur) { if (cur-_kv.first key) { if (prev nullptr) { _table[hashi] cur-_next; } else { prev-_next cur-_next; } delete cur; return true; } prev cur; cur cur-_next; } return false; } private: vectorNode* _table; size_t _n 0; }; }3.3封装暂略4.哈希的应用4.1位图所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常用来判断某个数据在不在。4.1.1位图的应用1.快速查找某个数据是否在一个集合中2.排序去重3.求两个集合交集、并集等4.操作系统磁盘标记4.1.2位图实现暂略4.2布隆过滤器布隆过滤器是由布隆Burton Howard Bloom在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。4.2.1插入往布隆过滤器增加元素添加的key需要根据k个无hash函数计算得到多个hash值然后对数组长度进行取模得到数组下标的位置然后将对应数组下标的位置的值置为1。4.2.2查找布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判。比如在布隆过滤器中查找alibaba时假设3个哈希函数计算的哈希值为1、3、7刚好和其他元素的比特位重叠此时布隆过滤器告诉该元素存在但实该元素是不存在的。主要是因为hash函数无论如何好都会出现冲突可能会存在多个元素计算的hash值一样的情况此时删除可能并不会将该位置一所以出现误判。4.2.3删除布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。比如删除上图中tencent元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。(缺陷无法确认元素是否真正存在存在计数回绕)