婚纱摄影网站模板下载,有没有做婚车的网站,移动网站开发实例,seo搜索优化工程师招聘快乐的流畅#xff1a;个人主页 个人专栏#xff1a;《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火#xff0c;在为久候之人燃烧#xff01; 文章目录 引言一、哈希1.1 哈希概念1.2 哈希函数1.3 哈希冲突 二、闭散列2.1 数据类型2.2 成员变量2.3 默认成员函数2.… 快乐的流畅个人主页 个人专栏《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火在为久候之人燃烧 文章目录 引言一、哈希1.1 哈希概念1.2 哈希函数1.3 哈希冲突 二、闭散列2.1 数据类型2.2 成员变量2.3 默认成员函数2.3.1 constructor 2.4 查找2.5 插入2.6 删除 三、开散列3.1 结点3.2 成员变量3.3 默认成员函数3.3.1 constructor3.3.2 destructor 3.4 查找3.5 插入3.6 删除3.7 哈希化 总结 引言
之前学习的红黑树增删查改都为O(logN)但是今天学习的哈希表理论上可以达到增删查改都为O(1)让我们来看看是什么结构这么神奇吧~
一、哈希
1.1 哈希概念
在线性结构和树形结构中元素键值key与其存储位置之间没有对应关系因此在查找指定元素时要经过key的多次对比。
时间复杂度顺序查找为O(N)二叉搜索平衡树查找为O(logN)。 理想的查找方式不经过任何比较直接通过key获取其存储位置。
这就是哈希的本质通过某种函数称之为哈希函数构建key与其存储位置的一一映射关系从而达到查找为O(1)。而这种结构也称为哈希表Hash Table又称散列表。
1.2 哈希函数
哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部key而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单 那么下面介绍两种常见的哈希函数
直接定址法 Hash(key) A*key B
优点简单、均匀 缺点需要事先知道key的分布情况
除留余数法 Hash(key) key % p (pm)其中m为地址数p为最接近m的素数
优点不需要事先知道key的分布情况 缺点会产生哈希冲突 选择除数为素数的原因减少哈希冲突 如果选择的除数包含多个正因数那么哈希地址可能会集中在某些特定的值上从而导致冲突概率增加。 1.3 哈希冲突
哈希冲突又称哈希碰撞即为不同key通过相同哈希函数计算出相同的哈希地址。
数学表达对于两个数据元素的关键字 k i k_i ki和 k j k_j kj(i ! j)有 k i k_i ki ! k j k_j kj有Hash( k i k_i ki) Hash( k j k_j kj) 面对陌生数据我们一般比较常用的除留余数法会产生哈希冲突而哈希冲突则是影响哈希表效率的关键因素。
那么如何解决哈希冲突呢这里有两种方法闭散列和开散列
二、闭散列
闭散列又称开放定址法。
当哈希冲突发生时开放定址法尝试在哈希表内部找到一个空闲的单元来存放冲突的元素。这个空闲的单元被称为开放单元或空白单元。
2.1 数据类型
enum State
{EMPTY,EXIST,DELETE
};templateclass K, class V
struct HashData
{pairK, V _kv;State _state EMPTY;
};细节
每个哈希数据都要设置状态变量以便区分状态分为空存在和删除数据状态初始化为空
2.2 成员变量
templateclass K, class V
class HashTable
{
public:
protected:vectorHashDataK, V _tables;size_t _n 0;//有效数据个数
};细节
哈希表底层一般使用数组vector哈希表的有效数据个数_n与vector的size不同
2.3 默认成员函数
2.3.1 constructor
HashTable()
{_tables.resize(10);
}细节这里vector提前开空间可以避免后续为空的讨论
2.4 查找
HashDataK, V* Find(const K key)
{size_t hashi key % _tables.size();size_t pos hashi;size_t i 1;while (_tables[pos]._state ! EMPTY){if (_tables[pos]._state EXIST _tables[pos]._kv.first key){return _tables[pos];}pos hashi i;if (pos _tables.size()){return nullptr;}i;}return nullptr;
}细节
先用key取模数组size得到哈希地址hashi然后沿当前位置向后找直到该位置状态为空或超出数组边界才算找不到如果该位置状态为存在且key相等则找到了
2.5 插入
bool Insert(const pairK, V kv)
{if (Find(kv.first))//保持key唯一{return false;}//...size_t hashi kv.first % _tables.size();size_t pos hashi;size_t i 1;while (_tables[pos]._state EXIST){pos hashi i;//线性探测if (pos _tables.size()){return false;}i;}_tables[pos]._kv kv;_tables[pos]._state EXIST;_n;return true;
}细节
先查找当前是否存在该值如果存在则不插入用key取模数组size得到哈希地址hashi然后沿当前位置向后找直到状态为空或删除才插入 但是上述情况是哈希表未满时如果满了如何扩容还有一定要满了才扩容吗
这里我们引入负载因子的概念α 有效数据个数 / 哈希表长度
当负载因子越大哈希冲突的概率就越大同时发生哈希踩踏的概率也越大对于开放定址法应该控制负载因子小于0.7超过将扩容。
if (_n * 10 / _tables.size() 7)//负载因子大于等于0.7 扩容
{size_t newsize _tables.size() * 2;vectorHashDataK, V newtables(newsize);for (auto cur : _tables){size_t hashi cur._kv.first % newsize;size_t pos hashi;size_t i 1;while (newtables[pos]._state EXIST){pos hashi i;//线性探测i;}newtables[pos]._kv kv;_tables[pos]._state EXIST;}_tables.swap(newtables);
}细节
判断时左右同乘以10避免比较浮点数而带来误差newsize为原本的2倍本来应该是接近2倍的素数这里简单起见没实现将原哈希表中的元素一一映射到新表中最后交换旧表和新表类似于拷贝构造的现代写法
2.6 删除
bool Erase(const K key)
{HashDataK, V* ret Find(key);if (ret){ret._state DELETE;--_n;return true;}return false;
}细节
先查找当前是否存在该值如果存在则删除这里的删除只用将状态变量改为删除即可 以上讲解的查找和插入它们所用的探测方法是线性探测一个一个往后找这种探测方法可能会造成大量的哈希冲突。
那么有没有什么探测方法能缓解哈希冲突呢有那就是二次探测
改法也很简单以一小段代码举例
while (newtables[pos]._state EXIST)
{pos hashi i*i;//二次探测i;
}这样就是每次跨越 i 的二次方向后探测中间间隔大哈希冲突就可以得到缓解。
三、开散列
但是闭散列开放定址法有一个致命的缺陷那就是空间利用率低它必须保留相当一部分的开放空间才能不断插入。
所以实际上我们更常用另一种方式来实现哈希表——闭散列又称为开链法。
在开链法中哈希表的每个槽位bucket又称为哈希桶通过一个单链表来存储所有散列到该槽位的元素。这意味着即使不同的key经过哈希函数映射到同一个槽位它们也可以被存储在同一个单链表上从而避免了冲突。 3.1 结点
templateclass K, class V
struct HashNode
{HashNodeK, V* _next;pairK, V _kv;HashNode(const pairK, V kv): _next(nullptr), _kv(kv){}
};细节
这里没有使用STL的list或者forward_list而是自己设计结点为了更方便操纵内部细节
3.2 成员变量
templateclass K, class V, class Hash HashFuncK
class HashTable
{
protected:typedef HashNodeK, V Node;
public:
protected:vectorNode* _tables;size_t _n 0;//有效数据个数
};细节
数组vector中存储单链表的头结点指针模板参数的Hash是为了任意类型都能转换为整型来取模
3.3 默认成员函数
3.3.1 constructor
HashTable()
{_tables.resize(10);
}细节这里vector提前开空间可以避免后续为空的讨论
3.3.2 destructor
~HashTable()
{for (auto cur : _tables){while (cur){Node* del cur;cur cur-_next;delete del;}}
}细节因为涉及链表结点空间的动态开辟所以要手动释放
3.4 查找
Node* Find(const K key)
{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;
}细节
先取模计算出哈希地址再沿当前单链表向下查找
3.5 插入
bool Insert(const pairK, V kv)
{if (Find(kv.first))//保持key唯一{return false;}Hash hash;//...size_t hashi hash(kv.first) % _tables.size();Node* newnode new Node(kv);//头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;
}细节
先查找当前是否存在该值如果存在则不插入取模计算出哈希地址再头插新节点 运用开链法后虽然没有哈希冲突了但是链表长度过长也会影响效率。所以哈希表也需要通过扩容来使链表长度变短理想的状态是负载因子为1时扩容。
悄悄说一句链表过长还有另一种解决方法那就是在该哈希桶下改挂一棵红黑树~
if (_n _tables.size())//负载因子为1时扩容{size_t newsize _tables.size() * 2;vectorNode* newtables(newsize);for (auto cur : _tables){while (cur){Node* next cur-_next;//将旧表结点重新映射到新表上size_t hashi hash(cur-_kv.first) % newsize;cur-_next newtables[hashi];newtables[hashi] cur;//跳回旧表的下一结点cur next;}}_tables.swap(newtables);}细节
二倍扩容本来应该是接近2倍的素数这里简单起见没实现遍历旧表将旧表结点重新映射到新表上这里直接链接而不是创建新节点最后交换旧表和新表
3.6 删除
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;--_n;return true;}prev cur;cur cur-_next;}return false;
}细节
单链表删除设置prev前置指针注意头删的情况分类处理
3.7 哈希化
由于除留余数法涉及到取模运算而只有整型才能取模。所以针对非整型的数据需要将其转化为整型这一过程称为哈希化。
templateclass K
struct HashFunc
{size_t operator()(const K key){return key;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto ch : s){hash hash * 31 ch;}return hash;}
};细节
第一个哈希化函数针对的是内置类型整型或浮点型等返回值设置为size_t相近类型会进行隐式类型转换第二个哈希化函数针对的是字符串运用了模板的特化。同时为了防止字符串的异位串对应字符数相同而位置不同并不是直接相加而是每次相加后乘以31保证肯定不重复。同时如果针对特殊的类用户可以手写一个特定的哈希化函数进行模板传参
总结
相比闭散列开散列看似增加了存储指针的空间开销实际上闭散列要保证大量的空闲单元以降低哈希冲突所以开散列反而更加节省空间其空间利用率更高 哈希表与红黑树的对比
哈希表平均查找可达O(1)但最坏降到O(N)哈希冲突红黑树最坏查找也可保持O(logN)比较稳定
数据有序性哈希表无序而红黑树有序
适用场景哈希表适合单点查找红黑树适合范围查找 真诚点赞手有余香
