用帝国做的网站,建筑设计私活平台,欧美一级a做爰片免费网站,互动平台网站欢迎来到博主的专栏#xff1a;数据结构 博主ID#xff1a;代码小豪 文章目录 哈希表的思想映射方法#xff08;哈希函数#xff09;除留余数法 哈希表insert闭散列负载因子扩容find和erase 哈希表的思想
在以往的线性表中#xff0c;查找速度取决于线性表是否有序#…欢迎来到博主的专栏数据结构 博主ID代码小豪 文章目录 哈希表的思想映射方法哈希函数除留余数法 哈希表insert闭散列负载因子扩容find和erase 哈希表的思想
在以往的线性表中查找速度取决于线性表是否有序如果是无序的线性表我们就要从表头开始匹配key值是否相同因此时间复杂度取决于线性表的元素个数为ON。
如果线性表有序则可以通过二分查找法大大的减少查找时间时间复杂度为OlogN这个时间复杂度看起来让人满意但是我们要考虑到一点那就是保持线性表的有序性是要付出代价的使用排序算法也有ON*logN的时间复杂度。
即使是使用关联式容器它的查找速度也是OlogN但是好处在于插入和删除元素并不会破坏查找速度。但是查找的速度就局限于此了吗 已现实为例如果我们想要在城里找到大舅妈肯定不会遍历整个城的街道从街道口走到街道尾去找大舅妈的家我们会先知道大舅妈的住址直接去这个住址就能找到大舅妈。 这就是哈希表的查找的方式了将key值放在映射的地址处这样查找key值就不用从头开始遍历了。举个例子假设现在有一个能容纳十个元素的哈希表。我们规定key值的个位数就是映射的地址值即让1位于1号2位于2号。以此类推而10则放在0号。 假设我们要查找13那么去3号处就能找到对应值查找速度为O1。这就是哈希表查找的优势。
映射方法哈希函数
哈希表中的映射方法叫做哈希函数以上表为例其哈希函数为F(key)key%10。于是F(13)3F(25)5。一个好的哈希函数很重要。这将决定哈希表的查找插入删除的速率最主要还是查找。哈希函数需要能将key值的数据转换成整形的能力。
但是并非所有类型都可以和整形转换。比如string就不能通过F(key)key%10的方式获得映射值此时我们就需要设计一个使用于string的哈希函数比如可以设计让string的所有元素相加为映射值的哈希函数即F(string){a1a2……an}。实际上字符串的哈希函数设计绝没这么简单感兴趣可以在网上搜索。
那么自定义类型当然也要依靠自定义的哈希函数才能获得其映射值通常哈希函数的设计需要考虑一下几点 1选取的key值的独特性比如我们在数据库中查找一个人如果选择“姓名”作为映射值那么肯定效率不佳因为全国同名同性的人是在太多了如果我们选择“生日姓名”作为映射值就会好很多。
2哈希函数的结果要尽可能的分散假设现在有N个元素要插入到哈希表那么它们的映射值越分散在哈希表就越好如果N个元素经过哈希函数的运算结果的映射值都是1那么肯定是毫无效率可言的。
3哈希函数的计算结果要包含在哈希表的域中如果一个哈希表能容纳100个元素即可容纳映射值0-99的元素那么如果一个key值计算出映射值为101那么肯定是没法插入的。
在c标准库中的unordered_map就是用哈希表为底层的容器其允许我们传入自定义的哈希函数已适配那些自定义的类型的映射值计算。
template class Key, // unordered_map::key_typeclass T, // unordered_map::mapped_typeclass Hash hashKey, //可以传入自定义的哈希函数// unordered_map::hasherclass Pred equal_toKey, // unordered_map::key_equalclass Alloc allocator pairconst Key,T // unordered_map::allocator_type class unordered_map;除留余数法
除留余数法是一个比较通用而且简单的哈希函数。其主要方法为
设哈希表可容纳最大地址数为m取一个不超过m的值p作为除数其哈希函数为hash(key)key%p。
比如当前哈希表的最大地址数为50待插入的key的哈希值为313则其映射值为313%5013。
在后续哈希表的底层设计中博主将采用这个方法。
哈希表
hash表的底层可以用序列式容器vector或者deque因为哈希表的映射值与下标很适配。
templateclass key,class value
class hash_tab
{
public:hash_tab(){_tab.resize(10);_n 0;}typedef pairkey, value value_type;private:vectorhash_datavalue_type _tab;size_t _n;//当前有效数据
};而哈希表每个元素都要存储两个数据分别是data以及状态state。由于vector一次性开了十个元素的空间因此有些空间是没有有效数据的。这些没有有效数据的元素的状态记为空empty如果元素具有有效数据则记为有exist如果元素的有效数据被删除则记为删除delete。
enum state
{EXIST,//存在映射DELETE,//删除映射EMPTY//空的映射
};templateclass T
struct hash_data
{hash_data(){_state EMPTY;}hash_data(const T data,state state){_data data;_state state;}const hash_data operator(const hash_data hashdata){_data hashdata._data;_state hashdata._state;return *this;}T _data;state _state;
};insert
insert的方式如下 1先通过hash函数计算出key值的映射地址处。博主采用除留余数法。 2将元素插入到映射值对应的地方。
比如现在插入的元素key值为60由于当前哈希表的最大空间为10默认构造函数因此除留余数法为hash6060%100。插入在0下标处。 ok现在我们来面临第一个问题如果我们现在插入30那么它该插入在什么位置呢根据哈希函数hash3030%100。那么它应该插入在映射值为0的下标处但是0下标处已经存在60这个数据了那么该如何处理呢
这种情况被称为“哈希冲突”即不同的key值30与60但是经过哈希函数计算后得到了相同的映射值0。如果想要减少哈希冲突优化哈希函数是一个不错的选择但是这并不能解决哈希冲突通常我们会用两种方法解决哈希冲突闭散列和开散列。这篇文章我们先来了解闭散列的哈希表在下一篇中博主再谈谈开散列的哈希表如何实现。
闭散列
闭散列也称开放地址法当发生哈希冲突时。探测哈希表的空位置将key值插入在冲突位置的下一个空位置处。探测方法也分为多种
方法1线性探测
线性探测从冲突位置开始依次往后探测直到找到下一个新位置为止。以上例为例由于30插入的位置与60发生了哈希冲突那么30从0下标开始线性探测后续位置直到遇到第一个空位置EMPTY,DELETE也算作空位置。 如果此时在插入一个20与60依然发生了哈希冲突根据线性探测的方法20应该插入在下标2的位置。 假如这个哈希表满了那么再次插入一个key值会发生什么事呢 根据线性探测的规则插入2的位置会陷入一个死循环因为在这个哈希表中已经不存在空位置了在这个哈希表中无论探测多少次都找不到位置。
实际上当哈希表中的元素占比整个空间越来越多时哈希冲突发生的几率会越来越高而每次发生哈希冲突时都会带来额外的时间开销线性探测。因此最好的解决方法是控制元素与空间之间的占比。
负载因子
我们将哈希表中元素与空间之间的占比成为负载因子。即 负载因子元素个数÷哈希表的总容量 负载因子与元素个数成正比与哈希表的总容量成反比当负载因子小时发生哈希冲突的几率低插入效率高但是空间利用率也低。当负载因子大时发生哈希冲突的几率大插入效率低但是空间利用率高。因此控制负载因子在一定的数值内也是很重要的。
通常来说采取线性探测的哈希表其负载因子应该控制到0.7~0.8。如果负载因子超过这个区间就要对哈希表进行扩容。以降低哈希表的负载因子。
扩容
哈希表的扩容策略是异地扩容即先构造一个新的哈希表这个新的哈希表是原哈希表的二倍然后再讲原哈希表的元素重新插入在新哈希表当中。最后交换新旧两个哈希表。那么为什么要这样做呢与其说异地扩容的好处不如讲讲原地扩容的坏处。
假如我们将上例中的哈希表扩容两倍即新哈希表的容量为20. 由于哈希表的最大容量发生了变化那么哈希函数也会随之变化因为我们设定的哈希函数为 hashkeykey%size 由于size从10变成了20那么哈希函数就变成了key%20。那么哈希表中17的映射值为 hash1717%2017这个插入位置就不对。因此更好的方式是新建一个新哈希表。将旧表的内容插入至新表当中。 bool insert(const value_type kv){//负载因子过多需要扩容 负载因子等于size%_nif (double(_n) / _tab.size() 0.7){hash_tab new_tab;new_tab._tab.resize(_tab.size() * 2);//建立新表for (auto e : _tab){if (e._state EXIST)//只插入有效值{new_tab.insert(e._data);//将旧表的值插入到新表当中}}_tab.swap(new_tab._tab);//交换新旧两表}size_t hashnum kv.first % _tab.size();//哈希函数——除留余数法while (_tab[hashnum]._state EXIST )//线性探测{hashnum;hashnum % _tab.size();}_tab[hashnum] hash_datavalue_type(kv, EXIST);//插入新值_n;return true;}find和erase
find函数的方法如下
通过哈希函数计算出映射值找到映射的位置然后线性检测找到正确的key值然后返回节点如果线性检测到空节点DELETE不算空节点仅EMPTY。就说明哈希表中不存在对应key值返回nullptr。 hash_datavalue_type* find(const key key){size_t hashnum key % _tab.size();while (_tab[hashnum]._state ! EMPTY){if (key _tab[hashnum]._data.first_tab[hashnum]._state!DELETE){return _tab[hashnum];}hashnum;hashnum % _tab.size();}return nullptr;}erase的实现就更简单我们先通过find查找到待删除的元素然后将该元素的状态调整成DELETE就可以了因为对这个元素的data进行修改不是一个明智的选择。这会影响到映射关系。 bool erase(const key key)
{size_t hashnum key % _tab.size();hash_datavalue_type* ptrfind(key);if (ptr nullptr)return false;ptr-_state DELETE;_n--;return true;
}
