python搭建网站,哪些网站可以做引流,鹤岗网站建设,网站logo的颜色与网页的颜色哈希学习 unordered系列关联式容器哈希结构除留余数法哈希冲突闭散列线性探测二次探测 负载因子开散列开散列增容 闭散列 VS 开散列字符串哈希算法 线性探测 二次探测实现拉链法实现 unordered系列关联式容器
unordered系列关联式容器是从C11开始#xff0c;STL提供的。… 哈希学习 unordered系列关联式容器哈希结构除留余数法哈希冲突闭散列线性探测二次探测 负载因子开散列开散列增容 闭散列 VS 开散列字符串哈希算法 线性探测 二次探测实现拉链法实现 unordered系列关联式容器
unordered系列关联式容器是从C11开始STL提供的。它的查询效率要更优于set/map类型关联式容器。 unordered系列容器的名字是从功能角度来取定的。set/map这类容器其遍历是有序的而unordered系列容器的遍历则是无序的。 从底层角度来看set/map类容器底层采用红黑树实现而unordered系列容器则是采用的哈希结构。同时map/set的迭代器是双向的而unordered系列容器是单向的。 unordered系列容器的使用可以参考set/map的使用【C】set map的使用它们的使用方式大多是类似的。
哈希结构
哈希也叫散列是一种值与存储位置之间建立映射关联的结构。 哈希结构通过哈希函数(Hash)使元素的关键码与存储位置之间建立一一映射的关系。当插入元素时由元素的关键码根据哈希函数计算出元素的存储位置进行存放当查找删除元素时也是同样的计算过程。
除留余数法
哈希函数有很多种本文中使用的哈希函数为除留余数法。 设哈希表中允许存放的位置个数为n取一个小于等于n的最大质数p作为除数按照哈希函数Hash(key) key % p通过计算将关键码转换成哈希表中对应的地址。
哈希冲突
当哈希表中存放的数据越来越多必然会出现不同的key通过相同哈希函数的计算出现相同地址的情况即哈希冲突或哈希碰撞。 哈希冲突的解决有两种常见方式闭散列和开散列。
闭散列
闭散列也叫开放定址法。当发生哈希冲突时如果哈希表未被填满也就是还存在空位置那么可以把关键码key的元素存放到冲突位置的“下一个”空位置去。
线性探测
线性探测从发生冲突的位置开始依次向后探测直到找到一个空位置为止。 线性探测的插入分两种情况
通过哈希函数计算待插入元素的位置如果该位置没有元素即直接插入新元素如果该位置有元素发生哈希冲突使用线性探测找到空位置再插入新元素。
线性探测的查找和删除的处理需要额外引入对元素delete的状态标记。
enum State{EMPTY, EXIST, DELETE};假如哈希表中存在发生哈希冲突的两个元素这两个元素位置一前一后状态都为EXIST。如果在前面的元素被删除了该位置状态直接被置为EMPTY此时再去找位于后面的元素就会发生找不到的情况。因为寻找的终止条件就是遇到空EMPTY结束。所以通过DELETE标记的引入使得前面元素的删除不会影响到后面的元素。 线性探测实现起来会比较简单。但是一旦发生哈希冲突可能会相互作用不断扩大冲突的范围使得找一个关键码的位置需要比较很多次从而导致效率的下降。
二次探测
二次探测是对线性探测缺陷的一种改进但本质上还是没有完全解决哈希冲突问题。 如果说线性探测的“下一个”位置可以用 H a s h ( k e y ) i ( i 0 ) Hash(key) i(i0) Hash(key)i(i0)表示那么在二次探测中“下一个”位置的表示就是 H a s h ( k e y ) i 2 Hash(key) i^2 Hash(key)i2 或者 H a s h ( k e y ) − i 2 Hash(key) - i^2 Hash(key)−i2。
负载因子
其实还可以通过扩容来降低哈希冲突发生的概率。 哈希表的负载因子 α 填入表中的元素个数 哈希表的长度 ( 地址个数 ) \alpha \dfrac{填入表中的元素个数}{哈希表的长度(地址个数)} α哈希表的长度(地址个数)填入表中的元素个数。 α \alpha α是哈希表填充程度的衡量因子。因为表长是定值所以 α \alpha α与“填入表中的元素个数”成正比。所以 α \alpha α越大表明填入表中的元素越多冲突概率也越大反之 α \alpha α越小表明填入表中的元素越少冲突概率也越小。对于闭散列(开放定址法)应严格限制 α \alpha α在0.7 - 0.8。 闭散列最大的缺陷就是空间利用率比较低了这同时也是哈希的缺陷。
开散列
开散列也叫拉链法。首先同样是通过哈希函数计算关键码的地址不同的地方是它将具有相同地址的关键码元素归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表连接起来哈希表中存储各链表的头节点指针。 所以开散列中每个桶存放的都是发生哈希冲突的元素。
开散列增容
开散列最好的情况是每个哈希桶中刚好挂一个节点。然后再继续插入元素时每一次都会发生哈希冲突。 因此在元素个数刚好等于桶的个数再插入时可以给哈希表增容。
闭散列 VS 开散列
使用开散列处理哈希冲突需要增设链接指针似乎增加了存储开销。而闭散列需要预留大量的空闲空间来确保效率一般表项所占空间有比指针大的多所以使用开散列反而会比闭散列节省空间。
字符串哈希算法
如果关键码key不为整型比如为字符串类型又该如何映射其地址呢 首先当然是将字符串转为整形再做运算对于如何转换的问题可以参考BYVoid大佬的这篇关于字符串哈希算法的文章各种字符串Hash函数比较里面给出了各种哈希算法的源码实现并对各种算法的性能做了分数排名。
Hash函数数据1数据2数据3数据4数据1得分数据2得分数据3得分数据4得分平均分BKDRHash20477448196.5510090.9582.0592.64APHash23475449396.5588.4610051.2886.28DJBHash22497547496.5592.31010083.43JSHash14476150610084.6296.8317.9581.94RSHash10486150510010051.5820.5175.96SDBMHash32484950493.192.3157.0123.0872.41PJWHash302648785130043.89021.95ELFHash302648785130043.89021.95
线性探测 二次探测实现
templateclass K
class Hash
{
public:// 整形直接返回size_t operator()(const K key){return (size_t)key;}
};template
class Hashstring
{
public:// string类型 -- BKDRHashsize_t operator()(const string key){size_t hash 0;for (char c : key){hash * 131;hash c;}// 装成整形返回return hash;}
};// 闭散列
namespace CloseHash
{// 标记哈希表表项的状态enum State{EMPTY,EXIST,DELETE};// 哈希表表项的类型templateclass K, class Vclass HashNode{public:pairK, V _kv; // 要存储的元素State _state EMPTY;};// 哈希表的实现templateclass K, class V, class Hash HashKclass HashTable{public:// 插入bool Insert(const pairK, V kv){// 找到了返回false插入失败if (Find(kv.first))return false;// 先检查扩容 -- 负载因子到0.7就扩容if (_table.size() 0 || 10 * _size / _table.size() 7){size_t newSize _table.size() 0 ? 10 : _table.size() * 2;HashTableK, V, Hash newHT;newHT._table.resize(newSize);// 旧表数据映射到新表for (auto e : _table){if (e._state EXIST){// 复用Insert()newHT.Insert(e._kv);}}// 交换_table.swap(newHT._table);}// 线性探测Hash hash;// key转整形 - 除留余数法size_t hashi hash(kv.first) % _table.size();while (_table[hashi]._state EXIST){hashi;hashi % _table.size();}_table[hashi]._kv kv;_table[hashi]._state EXIST;_size;return true;}// 删除bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){// 将状态标记成DELETE即可ret-_state DELETE;--_size;return true;}return false;}// 查找HashDataK, V* Find(const K key){if (_table.empty()){return nullptr;}Hash hash;size_t start hash(key) % _table.size();size_t hashi start;while (_table[hashi]._state ! EMPTY){if (_table[hashi]._kv.first key _table[hashi]._state ! DELETE){return _table[hashi];}hashi;hashi % _table.size();if (hashi start){break;}}return nullptr;}private:vectorHashNodeK, V _table;size_t _size 0; // 存储有效数据的个数};
}// 二次探测
// 只需要将Insert()中的线性探测部分替换成下面的二次探测即可
Hash hash;
size_t start hash(kv.first) % _table.size();
size_t i 0;
size_t hashi start;
while (_table[hashi]._state EXIST)
{i;hashi start i * i;hashi % _table.size();
}_table[hashi]._kv kv;
_table[hashi]._state EXIST;
_size;拉链法实现
// 开散列
//namespace OpenHash
namespace HashBucket
{// 哈希节点的类型templateclass K, class Vclass HashNode{public:HashNode(const pairK, V kv): _kv(kv), _next(nullptr){}pairK, V _kv; // 要存储的元素HashNodeK, V* _next;};templateclass K, class V, class Hash HashKclass HashTable{private:typedef HashNodeK, V Node;public:// 析构~HashTable(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}// 引用STL源码略做修改// 使哈希表每次扩容的大小为素数inline size_t __stl_next_prime(size_t n){static const size_t __stl_num_primes 28;static const size_t __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};for (size_t i 0; i __stl_num_primes; i){if (__stl_prime_list[i] n){return __stl_prime_list[i];}}return 0; // 表示出错了}bool Insert(const pairK, V kv){if (Find(kv.first)){return false;}Hash hash;// 检查扩容if (_size _table.size()){vectorNode* newTable;newTable.resize(__stl_next_prime(_table.size()), nullptr);// 旧表中的节点 移动 映射到新表for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;// 链接到新表size_t hashi hash(cur-_kv.first) % newTable.size();cur-_next newTable[hashi];newTable[hashi] cur;cur next;}_table[i] nullptr;}// 交换_table.swap(newTable);}size_t hashi hash(kv.first) % _table.size();// 头插Node* newnode new Node(kv);newnode-_next _table[hashi];_table[hashi] newnode;_size;return true;}bool Erase(const K key){if (_table.empty()){return false;}Hash hash;size_t hashi hash(key) % _table.size();Node* prev nullptr;Node* cur _table[hashi];while (cur){if (key cur-_kv.first){// 头删if (prev nullptr){_table[hashi] cur-_next;}else // 其他位置删除{prev-_next cur-_next;}delete cur;--_size;return true;}prev cur;cur cur-_next;}return false;}Node* Find(const K key){if (_table.empty()){return nullptr;}Hash hash;size_t hashi hash(key) % _table.size();Node* cur _table[hashi];// 去桶里面找while (cur){if (key cur-_kv.first){return cur;}cur cur-_next;}return nullptr;}// 返回有效数据个数size_t Size(){return _size;}// 表的长度(地址个数)size_t TableSize(){return _table.size();}// 桶的个数size_t BucketNum(){size_t num 0;for (size_t i 0; i _table.size(); i){if (_table[i]){num;}}return num;}// 最大桶的节点个数size_t MaxBucket(){size_t maxLen 0;for (size_t i 0; i _table.size(); i){size_t len 0;Node* cur _table[i];while (cur){len;cur cur-_next;}if (len maxLen){maxLen len;}}return maxLen;}private:vectorNode* _table; // 哈希表存哈希节点的指针size_t _size 0; // 存储有效数据的个数};
}
