个人网站的订单,网站建设中 页面,番禺人才网官网,怎么做网站dns加速程序猿的读书历程#xff1a;x语言入门—x语言应用实践—x语言高阶编程—x语言的科学与艺术—编程之美—编程之道—编程之禅—颈椎病康复指南。
前言#xff1a;
哈希表#xff08;Hash Table#xff09;是一种高效的键值对存储数据结构x语言入门—x语言应用实践—x语言高阶编程—x语言的科学与艺术—编程之美—编程之道—编程之禅—颈椎病康复指南。
前言
哈希表Hash Table是一种高效的键值对存储数据结构广泛应用于各种需要快速查找的场景如数据库索引、缓存系统、集合等。它的基本思想是通过哈希函数将键映射到哈希表中的一个位置从而实现快速的数据插入、删除和查找操作。下面我们将详细介绍哈希表的工作原理、实现方式、优缺点以及应用场景。
一、哈希概念
哈希是一种思想普遍是通过一个哈希数组来存储数据的。学哈希思想最重要的就是抓住映射两个字它是一个无序的数据结构所以想要找到存储的数据就必须通过相对应的哈希关系来寻找。 对于该数据结构 插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置 取元素比较若关键码相等则搜索成功一般来说的计算方法都是对值取余 该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称 为哈希表。 以最简单的整形数据来举例哈希结构想要与整形产生映射关系最简单的就是跟哈希数组的下标产生映射。如果存储数据的哈希数组大小为10例如数据集合{176459}哈希函数设置为hash(key) key % capacity;capacity为存储元素底层空间总的大小 。 就通过把他们的值取余一个数组大小10虽好放入相应下标的数组空间中这就是最简单的映射关系把1存储到下标为1的地方4存储到下标为下标为4的地方6存储到下标为6的地方。就算存储十位数百位数也是如此操作。 这样我们就能通过这个映射关系可以不经过任何比较一次直接从表中得到要搜索的元素。
二、哈希冲突
但是通过上面的介绍相信不少童鞋已经发现了一个下标只能存储一个数据如果我们有两个数转换后的下标相同呢
即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。
倘若数据中发生了哈希冲突我们应该怎么做呢 引起哈希冲突的一个原因可能是 哈希函数设计不够合理 。所以我们要先来了解一下哈希函数的涉及原则 1、哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有 m 个地址时其值 域必须在 0 到 m-1 之间 2、哈希函数计算出来的地址能均匀分布在整个空间中 3、哈希函数应该比较简单 常见的哈希函数主要是有两种一种是直接定址法 取关键字的某个线性函数为散列地址 Hash Key A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况 另外一种是除留余数法也是我们一开始用的这种 设散列表中允许的 地址数为 m 取一个不大于 m 但最接近或者等于 m 的质数 p 作为除数 按照哈希函数 Hash(key) key% p(pm), 将关键码转换成哈希地址 除此之外还有其他许多的方法一般来说哈希函数设计的越巧妙就越能减少哈希冲突。 当然在精巧的哈希函数也难免出现哈希冲突这个时候就需要我们自己去解决了。 解决哈希冲突两种常见的方法是闭散列和开散列。 1、闭散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有 空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 呢 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 就相当于上厕所时在还有空位当代情况下第一个你选择的坑位已经有人了那你这个时候肯定不会站在门口等着而是会选择旁边的位置。 二次探测从发生冲突的位置开始以一定变化向后依次探测空位比如第1处第2处随后是第4处第8处...... 在决定好寻找下一个空位置的方法后我们就设定好比例当空位已经不足一个比例时比如已经有十分之七的位置被使用这样哈希冲突产生的概率就会大大提高因此就需要我们对其进行扩容操作随后把原本的值依照新的存储空间大小来进行新的定址操作。 在使用闭散列方法时我们删除一个元素不能把他置为空节点之类因为如果此节点后续仍有同义词就会影响其的查找。 于是我们需要定义三个状态空删除有值。我们查找一个元素时碰见删除或者有值的话就继续查找直到碰见空就停止了。插入时碰见有值就继续寻找空位遇见空和删除就进行插入操作。 通过上面的介绍我们会发现开散列的方法并不如我们所想的那样解决哈希冲突所谓堵不如疏并没有从本质上解决哈希冲突而是一昧的选择寻找其他空位。导致哈希函数的一一对照关系并不明显表现出来。 那有没有什么方法那个解决这个缺点呢 答案是开散列。 2、开散列 开散列开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个同中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 这样有个好处就是一定会按照哈希函数对应的关系来进行分配哪怕我此时在插入一个14,24也只会找到下标位4的链表随后插入到此链表中不会跑到下标为3,5的链表里。 为了防止一条链表的数据过多影响性能我们一般也会对其进行扩容操作而开散列方法只需要将链表转移到新哈希表中就行不必要在全部拷贝一份数据。 三、其他数据类型的存储问题 哈希函数采用处理余数法被模的key必须要为整形才可以处理我们之前的思路只能解决int类型的存储问题如果那个值是string是char我们又应该怎么解决呢 string与char类型不能被取余我们想到那就把它转化为int类型不就可以了吗。 由于字符串长度我们不能确定但abcd与acbd两个字符串的ASCII码值确实一样如果光是ASCII码值之和来计算难免会出现比较离谱的存储结果。据此通过研究我们可以通过一些条件来减少ASCII码值的巧合 class Str_to_Int
{
public:size_t operator()(const string s){const char* str s.c_str();unsigned int seed 131; // 31 131 1313 13131 131313unsigned int hash 0;while (*str){hash hash * seed (*str);}return (hash 0x7FFFFFFF);}
}; 通过这种处理就能明显减少巧合的发生将其分配到正确的地址上。 四、哈希表闭散列线性探测实现 我们先写一个简单的哈希表的闭散列实现来理解一下哈希表的底层逻辑。 #pragma once
#includevector// 哈希函数采用除留余数法
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 哈希表中支持字符串的操作
template//这是对前面模板HashFunc的string特化类型
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash * 31;//防止abcd与dcba的ASCII码值之和相同hash e;}return hash;}
};// 以下采用开放定址法即线性探测解决冲突
namespace open_address
{enum State{EXIST,EMPTY,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;};templateclass K, class V, class Hash HashFuncKclass HashTable{public:HashTable(){_tables.resize(10);}bool Insert(const pairK, V kv){if (Find(kv.first))//如果以前插入过相同键值{return false;}if ((_n * 10) / _tables.size() 7)//扩容{HashTableK, V, Hashnewh;newh._tables.resize(2 * _tables.size());for (int i 0; i _tables.size(); i){if (_tables[i]._state EXIST){newh.Insert(_tables[i]._kv);}}_tables.swap(newh._tables);}Hash h;size_t index h(kv.first) % _tables.size();//确定插入下标while (_tables[index]._state EXIST){index;index index % _tables.size();}_tables[index]._state EXIST;_tables[index]._kv kv;_n;return true;}HashDataK, V* Find(const K key){Hash h;size_t index h(key) % _tables.size();//确定查找下标while (_tables[index]._state ! EMPTY){if ( key _tables[index]._kv.first){return _tables[index];}index;index % _tables.size();}return nullptr;}bool Erase(const K key){HashDataK, V* ret find(key);if (ret){ret-_state DELETE;return true;}else{return false;}}private:vectorHashDataK, V _tables;size_t _n 0; // 表中存储数据个数};
}慢慢看这层代码。 我们用K代表key值V代表Value值用Hash来代表一个模板函数这个函数是为了实现我们的转化key值的作用就是string类型的key转化为int值。 我们首先实现了哈希函数的模板让任意类型的K值得以转化为int类型的参数。注意对于能够转化为int类型的内置类型我们直接使用强制转化就行但是对于经常常用到的string却又不能直接转换为int我们就可以写一个特化要求当K为string时直接调用我们的特化函数就行了。 随后在我们的作用于中定义一个枚举类型代表上面说的三个状态存在空删除。 寻常的内置类型自然不会包含我们才定义的枚举状态自然就需要定义一个自定义类型。于是HashData出世了。 随后就是平常的接口的编写: 对于find接口如果我们找到了对应的值就需要返回这个值的指针HashDataK, V*如果没找到就返回空指针。而查找就是先通过Hash来找到初始的键值处开始线性查找直到找到或者为空找不到。 对于insert插入接口我们先判断是否已经插入过相同键值然后在判断是否达到扩容标准如果达到了就进行扩容操作创建一个新的哈希数组随后复用insert进行插入最后交换两个哈希数组就行新创建的会自动进行销毁。扩容后也是先通过Hash来找到初始的键值但我们这次应该通过线性探测来查找空位置或者删除的位置。 对于erase接口我们可以先复用find找到相应的位置随后把其的_state属性改为delete就行不必进行数据内容上的修改。我们访问任意一个地址都是先判断其state属性是否满足条件。 五、哈希表开散列哈希桶的实现 先看代码 #pragma once
#includevectortemplateclass K
struct HashFunc//哈希函数把K类型转化为int
{size_t operator()(const K key){return (size_t)key;}
};
template
struct HashFuncstring//当K类型时string时的特化函数
{size_t operator()(const string s){size_t ret 0;for (auto it : s)//我们这里对string的每个字母采用乘以31再相加的方法{ret * 31;ret it;}return ret;}
};namespace hash_bucket
{templateclass Tstruct HashNode//哈希桶存储的单链表的节点结构{T _data;HashNodeT* next;HashNode(const Tdata):_data(data),next(nullptr){}};templateclass K,class T,class HashHashFuncKclass HashTable{struct keyofT//我这里的实现方法有些特殊多增加了一个keyofT函数这个函数时为了后面用哈希桶实现unordered_map与unordered_set//而实现的由于那个时候哈希桶才是底层所以现在只使用底层代码就会变得奇怪{const K operator()(const Tkv)//传递一个string int类型的参数就得//HashTablestring, pairstring, inthash;{return kv.first;}};public:typedef HashNodeT Node;HashTable():_n(0){_tables.resize(10);}~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-next;delete cur;cur next;}_tables[i] nullptr;}}bool insert(const T data){Hash h;if (_n _tables.size())//扩容{vectorNode* newtables(_tables.size() * 2, nullptr);for (int i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-next;size_t newindex h(keyofT()(cur-_data)) % newtables.size();cur-next newtables[newindex];newtables[newindex] cur;cur next; }_tables[i] nullptr;}_tables.swap(newtables);}Node* newnode new Node(data);size_t index h(keyofT()(data)) % _tables.size();newnode-next _tables[index];_tables[index] newnode;_n;return true;}Node* find(const K key){Hash h;size_t index h(key) % _tables.size();Node* cur _tables[index];while (cur){if (cur-_data.first key){return cur;}else{cur cur-next;}}return nullptr;}bool erase(const K key){Hash h;size_t index h(key) % _tables.size();Node* prev nullptr;Node* cur _tables[index];while (cur){if (cur-_data.first key){if (prev nullptr){_tables[index] cur-next;}else{prev-next cur-next;}delete cur;cur nullptr;return true;}else{prev cur;cur cur-next;}}return false;}private:vectorNode*_tables;size_t _n;};
}; 相较于闭散列stl库里实现unordered_map与unordered_set两个容器时底层都用的开散列所以我这里的开散列实现的有些奇怪增加的keyofT函数更有利于后续的封装容器。 但是大体结构仍然没有改变同样用到了Hash来解决不同类型转化为int的问题。唯一值得一提的就是由于我们的节点是指针的链接方式所以扩容时我们不需要再赋值节点只需要把每个节点指针插入到新的哈希table里进行交换就行。 六、哈希表性能分析 哈希表的性能主要取决于哈希函数的设计和哈希冲突的处理方式。哈希表在最理想的情况下即哈希函数将元素均匀分布到哈希表中时查找、插入、删除操作的时间复杂度为 O(1)O(1)O(1)。但当发生大量哈希冲突时时间复杂度可能退化到 O(n)O(n)O(n)这是最坏情况。为了优化性能我们可以从以下几个方面着手 设计良好的哈希函数哈希函数应尽可能均匀地将元素分布到哈希表中避免哈希冲突。对数据的特性进行分析选择合适的哈希函数如前文提到的直接定址法、除留余数法等。 扩容当哈希表中存储的元素个数接近表容量时哈希冲突的概率会增加因此需要动态扩容保持较低的装载因子如装载因子不超过0.7。 合理选择哈希冲突解决策略开散列链地址法通常比闭散列开放定址法表现更好尤其是在高装载因子的情况下链表法通过链表的结构减少了冲突对性能的影响。 七、哈希表应用场景 哈希表作为一种高效的数据结构应用非常广泛特别是在需要快速查找的场景中。例如 数据库索引哈希表在数据库系统中用于索引结构能够快速查找数据。 缓存系统例如Redis等内存缓存系统广泛使用哈希表存储键值对实现高效的数据存取。 集合类操作哈希表在语言标准库中的实现如C的unordered_map、unordered_set用于高效的查找和去重操作。 字典查找哈希表是构建字典和符号表的基础广泛用于自然语言处理、编译器等场景。 八、哈希表的优缺点 优点 查找、插入、删除操作在理想情况下的时间复杂度为 O(1)O(1)O(1)性能非常高效。实现简单适合键值对的快速存储和检索。 缺点 在发生大量哈希冲突的情况下性能可能退化到 O(n)O(n)O(n)。哈希函数的设计需要谨慎容易出现偏斜分布从而影响性能。哈希表无法保证元素的顺序适用于无序集合或字典的应用场景。 九、总结 哈希表作为一种重要的数据结构提供了高效的查找、插入和删除操作。通过设计良好的哈希函数和适当的冲突解决策略可以最大化哈希表的性能。了解哈希表的工作原理和实现方式有助于在实际应用中选择合适的解决方案并有效提升系统的性能。 希望本篇文章对大家有所帮助
