精密导航,济南优化联系电话,国内做航模比较好的网站,房地产设计师工作内容文章目录哈希哈希#xff08;散列#xff09;函数常见的哈希函数字符串哈希函数哈希冲突闭散列#xff08;开放地址法#xff09;开散列#xff08;链地址法/拉链法#xff09;负载因子以及增容对于闭散列对于开散列结构具体实现哈希表#xff08;闭散列#xff09;创建…
文章目录哈希哈希散列函数常见的哈希函数字符串哈希函数哈希冲突闭散列开放地址法开散列链地址法/拉链法负载因子以及增容对于闭散列对于开散列结构具体实现哈希表闭散列创建插入查找删除完整代码哈希桶开散列插入查找删除完整代码哈希
哈希散列是一种数据结构通过散列算法将元素值转换为散列值进行存储。使得元素存储的位置与元素本身建立起了映射关系如果要查、改数据就可以直接到对应的位置去使得时间复杂度达到了 O(1) 原因如下
若结构中存在和 关键字K 相等的记录则必定在 f(K) 的存储位置上。由此不需比较便可直接取得所查记录。
称上面的对应关系 f 为 散列函数Hash function按这个映射关系事先建立的表为散列表这一映象过程称为 散列造表 或 散列 最终所得的存储位置称 散列地址 。 哈希散列函数
哈希函数用来建立元素与其存储位置的映射关系。
对于哈希函数来说必须具有以下特点
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有 m 个地址时其值域必须在 0 到 m-1 之间。哈希函数计算出来的地址能均匀分布在整个空间中防止产生密集的哈希冲突
哈希冲突大量出现往往都是因为哈希函数设计的不够合理但是即使再优秀的哈希函数也只能尽量减少哈希冲突的次数无法避免哈希冲突。 常见的哈希函数 直接定址法常见 哈希函数Hash(Key) A * Key B 这是最简单的哈希函数直接取关键字本身或者他的线性函数来作为散列地址。 除留余数法常见 哈希函数 Hash(key) key % capacity 几乎是最常用的哈希函数用一个数来对 key 取模一般来说这个数都是容量。 平方取中法 对关键字进行平方然后取中间的几位来作为地址。 折叠法 折叠法是将关键字从左到右分割成位数相等的几部分最后一部分位数可以短些然后将这几部分叠加求和去除进位并按散列表表长取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况. 随机数法 选择一个随机函数取关键字的随机函数值为它的哈希地址即 H(key) random(key)其中 random 为随机数函数。通常应用于关键字长度不等时。 数学分析法 分析一组数据比如一组员工的出生年月日这时我们发现出生年月日的前几位数字大体相同这样的话出现冲突的几率就会很大但是我们发现年月日的后几位表示月份和具体日期的数字差别很大如果用后面的数字来构成散列地址则冲突的几率会明显降低。因此数字分析法就是找出数字的规律尽可能利用这些数据来构造冲突几率较低的散列地址。 字符串哈希函数
因为哈希函数的常用方法如直接定址、除留余数、平方取中等方法需要用的 key值 为整型而大部分时候我们的 key 都是 string由于无法对 string 进行算数运算所以需要考虑新的方法。
常见的字符串哈希算法有 BKD、SDB、RS 等这些算法大多通过一些公式来对字符串每一个 字符的 ascii值 或者 字符串的大小 进行计算来推导出一个不容易产生冲突的 key值 。
例如 BKDHash
struct _Hashstd::string
{const size_t operator()(const std::string key){// BKDR字符串哈希函数size_t hash 0;for (size_t i 0; i key.size(); i){hash * 131;hash key[i];}return hash;}
};这里推荐两篇文章一篇具体对比各类字符串哈希函数的效率一篇是实现
字符串Hash函数对比各种字符串Hash函数 哈希冲突
对不同的关键字可能得到同一散列地址即 key1≠key2 而 f(key1)f(key2) 这种现象称碰撞哈希冲突。
哈希冲突使得多个数据映射的位置相同但是每个位置又只能存储一个数据所以就需要通过某种方法来解决哈希冲突。
查找过程中关键码的比较次数取决于产生冲突的多少产生的冲突少查找效率就高产生的冲突多查找效率就低。因此影响产生冲突多少的因素也就是影响查找效率的因素。影响产生冲突多少有以下三个因素
散列函数是否均匀处理冲突的方法散列表的负载因子装填因子。
第一点取决于上面讲过的哈希函数不再赘述下面详细讲一下2、3点。
处理冲突的方法可分为两类开散列方法( open hashing也称为拉链法separate chaining ) 和 闭散列方法( closed hashing也称为开地址方法open addressing )。这两种方法的不同之处在于开散列法把发生冲突的关键码存储在散列表主表之外而闭散列法把发生冲突的关键码存储在表中另一个槽内。 闭散列开放地址法
因为闭散列是顺序的结构所以可以通过遍历哈希表来将冲突的数据放到空的位置上。 线性探测 线性探测即为从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 这种方法实现起来极为简单但是效率也不高因为如果同一位置产生了大量的哈希冲突就会导致每次都在同一个位置进行探测例如我在10这里连续冲突100次此时所有探测的次数加起来就会高达100 二次探测 二次探测即为从发生冲突的位置开始每次往后探测 ±k2(km/2m为散列表长) 个位置如12-(12)22-(22) 等。 这样的话就将每次探测的效率从 O(N) 提升到了 O(logN) 即使有着大量的冲突堆积也不会导致效率过低。 伪随机数探测 这种方法并不常见实现方法是创建一个伪随机数序列根据序列内容决定每次往后探测的长度。 开散列链地址法/拉链法
先用哈希函数计算每个数据的散列地址把具有相同地址的元素归于同一个集合之中把该集合处理为一个链表链表的头节点存储于哈希表之中。 链地址法在每一个映射位置都建立起一个链表数据过多时可能会转为建立红黑树将每次插入的数据都直接连接上这个链表这样就不会像闭散列一样进行大量的探测但是如果链表过长也会导致效率低下。 负载因子以及增容
哈希冲突出现的较为密集往往代表着此时数据过多而能够映射的地址过少而要想解决这个问题就需要通过 负载因子装填因子 的判断来进行增容。 负载因子的大小 表中数据个数 / 表的容量长度 对于闭散列
对于闭散列来说因为其是一种线性的结构所以一旦负载因子过高就很容易出现哈希冲突的堆积所以当负载因子达到一定程度时就需要进行增容并且增容后为了保证映射关系还需要将数据重新映射到新位置。
经过算法科学家的计算 负载因子应当严格的控制在 0.7-0.8 以下所以一旦负载因子到达这个范围就需要进行增容。
因为除留余数法等方法通常是按照表的容量来计算所以科学家的计算当对一个质数取模时冲突的几率会大大的降低并且因为增容的区间一般是 1.5-2 倍所以算法科学家列出了一个增容质数表按照这样的规律增容冲突的几率会大大的降低。
这也是 STL 中 unordered_map/unordered_set 使用的增容方法。
//算法科学家总结出的一个增容质数表按照这样增容的效率更高const int PRIMECOUNT 28;const size_t primeList[PRIMECOUNT] {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul}; hashmap 的负载因子为什么默认是 0.75 比如说当前的容器容量是 16负载因子是 0.75,16*0.7512也就是说当容量达到了 12 的时候就会进行扩容操作。而负载因子定义为 0.75 的原因是
当负载因子是 1.0 的时候也就意味着只有当散列地址全部填充了才会发生扩容。意味着随着数据增长最后势必会出现大量的冲突底层的红黑树变得异常复杂。虽然空间利用率上去了但是查询时间效率降低了。负载因子是 0.5 的时候这也就意味着当数组中的元素达到了一半就开始扩容。虽然时间效率提升了但是空间利用率降低了。 诚然填充的元素少了Hash冲突也会减少那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。但是这时候空间利用率就会大大的降低原本存储 1M 的数据现在就意味着需要 2M 的空间。
对于开散列结构
因为哈希桶是开散列的链式结构发生了哈希冲突是直接在对应位置位置进行头插而桶的个数是固定的而插入的数据会不断增多随着数据的增多就可能会导致某一个桶过重使得效率过低。
所以最理想的情况就是每个桶都有一个数据。这种情况下如果往任何一个地方插入都会产生哈希冲突所以当数据个数与桶的个数相同时也就是负载因子为 1 时就需要进行扩容。 具体实现
哈希表闭散列
创建
对于闭散列我们需要通过状态来记录一个数据是否在表中所以这里会使用枚举来实现。
enum State
{EMPTY,//空EXITS,//存在DELETE,//已经删除
};templateclass T
struct HashData
{HashData(const T data T(), const State state EMPTY): _data(data), _state(state){}T _data;State _state;
};插入
插入的思路很简单计算出映射的地址后开始遍历判断下面几种状态
如果映射位置已存在数据并且值与当前数据不同则说明产生冲突继续往后查找如果映射位置的数据与插入的数据相同则说明此时数据已经插入过此时就不需要再次插入如果映射位置的状态为删除或者空则代表着此时表中没有这个数据在这个位置插入即可
bool Insert(const T data)
{KeyOfT koft;//判断此时是否需要增容//当装填因子大于0.7时增容if (_size * 10 / _table.size() 7){//增容的大小按照别人算好的近似两倍的素数来增这样效率更高也可以直接2倍或者1.5倍。std::vectorHashData newTable(getNextPrime(_size));for (size_t i 0; i _table.size(); i){//将旧表中的数据全部重新映射到新表中if (_table[i]._state EXITS){//如果产生冲突则找到一个合适的位置size_t index HashFunc(koft(_table[i]._data));while (newTable[i]._state EXITS){i;if (i _table.size()){i 0;}}newTable[i] _table[i];}}//最后直接将数据进行交换即可原来的数据会随着函数栈帧一起销毁_table.swap(newTable);}//用哈希函数计算出映射的位置size_t index HashFunc(koft(data));//从那个位置开始探测, 如果该位置已经存在时有两种情况一种是已经存在一种是冲突这里使用的是线性探测while (_table[index]._state EXITS){//如果已经存在了则说明不用插入if (koft(_table[index]._data) koft(data)){return false;}else{index;index HashFunc(index);}}//如果走到这里说明这个位置是空的或者已经被删除的位置可以在这里插入_table[index]._data data;_table[index]._state EXITS;_size;return true;
}查找
查找也分几种情况
如果映射的位置为空则说明查找失败。如果映射的位置的数据不同则说明产生冲突继续向后查找如果映射的位置的数据相同如果状态为删除则说明数据已经删除查找失败而如果数据为存在则说明查找成功。
HashData* Find(const K key)
{KeyOfT koft;size_t index HashFunc(key);//遍历如果查找的位置为空则说明查找失败while (_table[index]._state ! EMPTY){//此时判断这个位置的数据是否相同如果不同则说明出现哈希冲突继续往后查找if (koft(_table[index]._data) key){//此时有两个状态一种是数据已经被删除一种是数据存在。if (_table[index]._state EXITS){return _table[index];}else if (_table[index]._state DELETE){return nullptr;}}index;//如果index越界则归零if (index _table.size()){index 0;}}return nullptr;
}删除
直接遍历查找数据如果找不到则说明已经被删除如果找到了则直接将状态改为删除即可。
bool Erase(const K key)
{HashData* del Find(key);//如果找不到则说明已经被删除if (del nullptr){return false;}else{//找到了则直接更改状态即可del-_state DELETE;_size--;return true;}
}完整代码
#pragma once
#includevectornamespace lee
{//算法科学家总结出的一个增容质数表按照这样增容的效率更高const int PRIMECOUNT 28;const size_t primeList[PRIMECOUNT] {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul};enum State{EMPTY,EXITS,DELETE,};templateclass Tstruct HashData{HashData(const T data T(), const State state EMPTY): _data(data), _state(state){}T _data;State _state;};templateclass K, class T, class KeyOfTclass HashTable{public:typedef HashDataT HashData;HashTable(size_t capacity 10): _table(capacity), _size(0){}size_t getNextPrime(size_t num){size_t i 0;for (i 0; i PRIMECOUNT; i){//返回比那个数大的下一个质数 if (primeList[i] num){return primeList[i];}}//如果比所有都大还是返回最后一个因为最后一个已经是32位最大容量return primeList[PRIMECOUNT - 1];}//除留余数法size_t HashFunc(const K key){return key % _table.size();}bool Insert(const T data){KeyOfT koft;//判断此时是否需要增容//当装填因子大于0.7时增容if (_size * 10 / _table.size() 7){//增容的大小按照别人算好的近似两倍的素数来增这样效率更高也可以直接2倍或者1.5倍。std::vectorHashData newTable(getNextPrime(_size));for (size_t i 0; i _table.size(); i){//将旧表中的数据全部重新映射到新表中if (_table[i]._state EXITS){//如果产生冲突则找到一个合适的位置size_t index HashFunc(koft(_table[i]._data));while (newTable[i]._state EXITS){i;if (i _table.size()){i 0;}}newTable[i] _table[i];}}//最后直接将数据进行交换即可原来的数据会随着函数栈帧一起销毁_table.swap(newTable);}//用哈希函数计算出映射的位置size_t index HashFunc(koft(data));//从那个位置开始探测, 如果该位置已经存在时有两种情况一种是已经存在一种是冲突这里使用的是线性探测while (_table[index]._state EXITS){//如果已经存在了则说明不用插入if (koft(_table[index]._data) koft(data)){return false;}else{index;index HashFunc(index);}}//如果走到这里说明这个位置是空的或者已经被删除的位置可以在这里插入_table[index]._data data;_table[index]._state EXITS;_size;return true;}HashData* Find(const K key){KeyOfT koft;size_t index HashFunc(key);//遍历如果查找的位置为空则说明查找失败while (_table[index]._state ! EMPTY){//此时判断这个位置的数据是否相同如果不同则说明出现哈希冲突继续往后查找if (koft(_table[index]._data) key){//此时有两个状态一种是数据已经被删除一种是数据存在。if (_table[index]._state EXITS){return _table[index];}else if (_table[index]._state DELETE){return nullptr;}}index;//如果index越界则归零if (index _table.size()){index 0;}}return nullptr;}bool Erase(const K key){HashData* del Find(key);//如果找不到则说明已经被删除if (del nullptr){return false;}else{//找到了则直接更改状态即可del-_state DELETE;_size--;return true;}}private:std::vectorHashData _table;size_t _size;};
};哈希桶开散列
开散列也叫哈希桶桶为每一个映射的位置桶一般用链表或者红黑树实现这里我用的是链表。当我们通过映射的地址找到存放数据的桶再对桶进行插入或者删除操作即可。
插入
通过计算映射位置找到对应的桶再判断数据是否存在后将数据头插进去即可也可以尾插
bool Insert(const T data)
{KeyofT koft;/*因为哈希桶是开散列的链式结构发生了哈希冲突是直接在对应位置位置进行头插而桶的个数是固定的而插入的数据会不断增多随着数据的增多就可能会导致某一个桶过重使得效率过低。所以最理想的情况就是每个桶都有一个数据。这种情况下如果往任何一个地方插入都会产生哈希冲突所以当数据个数与桶的个数相同时也就是负载因子为1时就需要进行扩容。*/if (_size _table.size()){//按照素数表来增容size_t newSize getNextPrime(_table.size());size_t oldSize _table.size();std::vectorNode* newTable(newSize);_table.resize(newSize);//接着将数据重新映射过去for (size_t i 0; i oldSize; i){Node* cur _table[i];while (cur){//重新计算映射的位置size_t pos HashFunc(koft(cur-_data));//找到位置后头插进对应位置Node* next cur-_next;cur-_next newTable[pos];newTable[pos] cur;cur next;}//原数据置空_table[i] nullptr;}//直接和新表交换交换过去的旧表会和函数栈帧一块销毁。_table.swap(newTable);}size_t pos HashFunc(koft(data));Node* cur _table[pos];//因为哈希桶key值唯一如果已经在桶中则返回falsewhile (cur){if (koft(cur-_data) koft(data)){return false;}else{cur cur-_next;}}//检查完成此时开始插入这里选择的是头插这样就可以减少数据遍历的次数。Node* newNode new Node(data);newNode-_next _table[pos];_table[pos] newNode;_size;return true;
}查找
直接根据映射的位置到桶中查找数据即可
Node* Find(const K key)
{KeyofT koft;size_t pos HashFunc(key);Node* cur _table[pos];while (cur){if (koft(cur-_data) key){return cur;}else{cur cur-_next;}}return nullptr;
}删除
bool Erase(const K key)
{KeyofT koft;size_t pos HashFunc(key);Node* cur _table[pos];Node* prev nullptr;while (cur){if (koft(cur-_data) key){//如果要删除的是第一个节点就让下一个节点成为新的头节点否则直接删除。if (prev nullptr){_table[pos] cur-_next;}else{prev-_next cur-_next;}delete cur;--_size;return true;}else{prev cur;cur cur-_next;}}return false;
}完整代码
#pragma once
#includevector
#includestringnamespace lee
{//算法科学家总结出的一个增容质数表按照这样增容的效率更高const int PRIMECOUNT 28;const size_t primeList[PRIMECOUNT] {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul};/*因为哈希函数的常用方法如直接定地、除留余数、平方取中等方法需要用的key值为整型而大部分时候我们的key都是string或者某些自定义类型这个时候就可以提供一个仿函数的接口给外部让他自己处理如何将key转换成我们需要的整型*/templateclass Kstruct Hash{const K operator()(const K key){return key;}};templatestruct Hashstd::string{const size_t operator()(const std::string key){//BKDR字符串哈希函数size_t hash 0;for (size_t i 0; i key.size(); i){hash * 131;hash key[i];}return hash;}};templateclass Tstruct HashNode{HashNode(const T data T()): _data(data), _next(nullptr){}T _data;HashNodeT* _next;};templateclass K, class T, class KeyofT, class Hash HashKclass HashBucket{public:typedef HashNodeT Node;HashBucket(size_t capacity 10): _table(capacity), _size(0){}~HashBucket(){Clear();}size_t getNextPrime(size_t num){size_t i 0;for (i 0; i PRIMECOUNT; i){//返回比那个数大的下一个质数 if (primeList[i] num){return primeList[i];}}//如果比所有都大还是返回最后一个因为最后一个已经是32位最大容量return primeList[PRIMECOUNT - 1];}size_t HashFunc(const K key){Hash hash;return hash(key) % _table.size();}bool Insert(const T data){KeyofT koft;/*因为哈希桶是开散列的链式结构发生了哈希冲突是直接在对应位置位置进行头插而桶的个数是固定的而插入的数据会不断增多随着数据的增多就可能会导致某一个桶过重使得效率过低。所以最理想的情况就是每个桶都有一个数据。这种情况下如果往任何一个地方插入都会产生哈希冲突所以当数据个数与桶的个数相同时也就是负载因子为1时就需要进行扩容。*/if (_size _table.size()){//按照素数表来增容size_t newSize getNextPrime(_table.size());size_t oldSize _table.size();std::vectorNode* newTable(newSize);_table.resize(newSize);//接着将数据重新映射过去for (size_t i 0; i oldSize; i){Node* cur _table[i];while (cur){//重新计算映射的位置size_t pos HashFunc(koft(cur-_data));//找到位置后头插进对应位置Node* next cur-_next;cur-_next newTable[pos];newTable[pos] cur;cur next;}//原数据置空_table[i] nullptr;}//直接和新表交换交换过去的旧表会和函数栈帧一块销毁。_table.swap(newTable);}size_t pos HashFunc(koft(data));Node* cur _table[pos];//因为哈希桶key值唯一如果已经在桶中则返回falsewhile (cur){if (koft(cur-_data) koft(data)){return false;}else{cur cur-_next;}}//检查完成此时开始插入这里选择的是头插这样就可以减少数据遍历的次数。Node* newNode new Node(data);newNode-_next _table[pos];_table[pos] newNode;_size;return true;}bool Erase(const K key){KeyofT koft;size_t pos HashFunc(key);Node* cur _table[pos];Node* prev nullptr;while (cur){if (koft(cur-_data) key){//如果要删除的是第一个节点就让下一个节点成为新的头节点否则直接删除。if (prev nullptr){_table[pos] cur-_next;}else{prev-_next cur-_next;}delete cur;--_size;return true;}else{prev cur;cur cur-_next;}}return false;}Node* Find(const K key){KeyofT koft;size_t pos HashFunc(key);Node* cur _table[pos];while (cur){if (koft(cur-_data) key){return cur;}else{cur cur-_next;}}return nullptr;}void Clear(){//删除所有节点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;}}private:std::vectorNode* _table;size_t _size;};
};
相关文章：
