电子商务网站运营方案,网站建设优化服务案例,百度短链接,网站建网站建设专业在顺序结构以及平衡树中#xff0c;由于元素关键码与其存储位置之间没有对应的关系#xff0c;因此在查找一个元素时#xff0c;必须要经过关键码的多次比较#xff1b;比如顺序表中需要从表头开始依次往后比对寻找#xff0c;查找时间复杂度为 O(N)#xff0c;平衡树中需… 在顺序结构以及平衡树中由于元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较比如顺序表中需要从表头开始依次往后比对寻找查找时间复杂度为 O(N)平衡树中需要从第一层开始逐层往下比对寻找查找时间复杂度为 O(logN)即搜索的效率取决于搜索过程中元素的比较次数。 尽管平衡树的查找方式已经很快了但我们仍然认为该方法不够极致我们最理想的查找方式不像二叉树那样经过层层比较能够用O(1)的时间复杂度直接查询到我们需要的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系那么在查找时通过该函数可以很快找到该元素。
一.哈希思想 1.1 哈希思想的概念 构造一种存储结构我们通过某种方法使元素的存储位置与其查找的元素建立某种映射关系从而利用O1的时间复杂度一次性查找到我们需要的元素这就是哈希思想。 当向该结构中
插入元素时根据待插入元素的特性提取出一个关键码以此通过转换函数计算出该元素的存储位置并按此位置进行插入。搜索元素时对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功。 该方法即为 哈希 (散列) 方法哈希方法中使用的转换函数称为哈希 (散列) 函数构造出来的结构称为哈希表 (Hash Table) (或者称散列表)。 ps我们上面提到的不管是顺序搜索、平衡树搜索还是哈希搜索其 key 值都是唯一的也就是说搜索树中不允许出现相同 key 值的节点哈希表中也不允许出现相同 key 值的元素我们下文所进行的所有操作也都是在这前提之上进行的。
假设 数据集合 {1 7 6 4 5 9} 存储空间为10
哈希函数设置为 hash(key) key % capacity ;
capacity 为存储元素底层空间总的大小。 我们通过 查找元素与下标关系 构建一个数组 当我们查找1 时可以直接定位到下标1这个位置实现O1时间内的查找。 1.2 哈希函数
哈希函数有如下设计原则 哈希函数应该要满足待插入的所有元素使用其值域如果在0到m-1之间那么他就必须有m个空间。哈希函数计算出来的地址要尽量能均匀分布在整个空间中哈希函数应该比较简单 我们有几个比较常见的哈希函数 1.2.1 直接定址法
直接定址法是最简单的哈希函数顾名思义直接定址就是根据 key 值直接得到存储位置最多再进行一个简单的常数之间的转换其定义如下
HashKey A*Key B (A B 均为常数)这个如果不懂假设A0,B0Key为常数即根据Key值直接确定存储位置。 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况 直接定址法不适用于数据范围分散的情况因为这样会导致哈希表的空间利用率很低会浪费很多空间
比如int arr[] { 123, 126, 125, 138, 122331, 1}; 假设A,B都为0 Hash(1) 1;
Hash1223112231
那么我们根据哈希函数的定义至少要用12231个int大小的数组来建立哈希表那么它就会占用很多存储空间。
1.2.2 除留余数法 (最常用) 为了应对数据范围分散的情况有人设计出了除留余数法 – 设哈希表中允许的地址数为m取一个不大于m但最接近或者等于m的素数p作为除数。
Hash(key) key % p (pm) 简单来说就是用 key 值除以哈希表的大小得到的余数作为哈希映射的地址将 key 保存到该地址中除留余数的优点是可以处理数据范围分散的数据缺点是会引发哈希冲突下文会提及.
例如对于数据集合 {176459}存储空间为10 它的哈希表如下 ps 接下来我们在文章中如果提到哈希函数默认为除留余数法。
1.3 哈希冲突 如何有两个元素 xy但是 hashxhashy这种明明不同的元素但是经过哈希函数计算后得到的结果一致我们就将这种情况称为哈希冲突。
哈希冲突有两种常见的解决办法 闭散列 (开放定址法)当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去 开散列 (链地址法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码 (哈希冲突) 归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中也就是说当发生哈希冲突时把 key 直接链接在该位置的下面。 假设我们在 插入一个11和21 二、闭散列法的哈希表 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去那如何寻找下一个空位置呢有两种方法 – 线性探测法常用和二次探测法。
2.1线性探测法 线性探测法是指从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止
插入11和21后 2.2 哈希表的基本框架
//通过空和存在判断插入通过删除状态判断查找
enum State {EXIST,EMPTY,DELETE
};templateclass K,class V
struct HashData {pairK, V _kv; //每个节点存储KV结构State _state EMPTY; //默认为空
};templateclass K, class V
class HashTable {typedef HashDataK, V Data;HashTable(): _n(0){//将哈希表的大小默认给为10_tables.resize(10);}
private://把哈希函数封装一下size_t Hashifunction(const K key){//这里我们采用除留余数法return key% _tables.size();}
private:vectorData _tables;size_t _n; //记录表中有效数据的个数
}; 如上为了方便在哈希表中我们使用了 vector 来存储数据并增加了一个变量 n 来记录表中有效数据的个数这是我们哈希表的底层实现。 同时我们在哈希表的每个位置的数据中还增加了一个 state 变量来记录该位置的状态但为什么要有三个变量呢我们不是只需要存在或者不存在不就足够了吗这是为了以后哈希表的查找做基础。
2.3 哈希表的插入
插入通过哈希函数得到余数即数组下标如果该下标的状态为删除或为空则插入如果为存在则向后寻找下一个状态为删除/空的位置进行插入。扩容一会单独讲 bool Insert(const pairK,V kv){if (find(kv.first)){//先判断是否查找到因为不能存储相同的结构如果查找到返回falsereturn false;}//根据除留余数法判断该插入数组的哪个位置size_t hashi Hashifunction(kv.first);while (_tables[hashi]._state EXIST) {hashi;hashi hashi % _tables.size(); //如果探测到末尾则从头开始重新探测}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}2.4 哈希表的查找 查找通过哈希函数得到余数即数组下标取出小标位置的key与目标key进行比较相等就返回该位置的地址不相等就继续往后查找如果查找到状态为空的下标位置就返回 nullptr注意这里有三个细节 当遇到状态为空的下标位置才返回 nullptr而不是遇到状态为 删除的位置就返回 nullptr因为你要查找的数据可能在已删除位置的后面这也是我们需要添加一个删除状态的原因如果你把一个位置的元素删除并设置为EMPTY状态那么我们该如何进行查找呢我们插入时其元素可能在删除元素后面例如
如果是这样那么你该如何查找呢 将查找函数返回值定义为 Data*而不是 bool这样可以方便我们进行删除和修改 (修改 key 对应的 value) – 查找到之后直接通过指针解引用来修改 value 与 state 哈希表经过不断插入删除最终可能会出现一种极端情况 – 哈希表中元素的状态全为 EXIST 和 DELETE此时如果我们找空就会造成死循环所以我们需要对这种情况单独进行处理. Data* find(const K key) {size_t hashi Hashifunction(key);//增加一个数字 如果查找一周 返回falsesize_t start hashi;while (_tables[hashi]._state! EMPTY)//如果不为空则继续查找{if (_tables[hashi]._stateEXIST_tables[hashi]._kv.first key){return _tables[hashi];}hashi;//此时已经查找了一圈退出循环if (hashi start) {break;}hashi % _tables.size();}//为空查找失败return nullptr;} 2.5 哈希表的删除 删除这里直接复用查找函数查找到就通过查找函数的返回值将小标位置数据的状态置为 删除找不到就返回 false。 这里采用伪删除法将状态改为DELETE就好毕竟我们重新插入时也是只看位置的状态伪删除法还减少了删除消耗。 bool Erase(const K key){HashDataK, V* ret find(key);if(ret){ret-_state DELETE;--_n;return true;}else {return false;}}
2.6 哈希表的扩容 哈希表的扩容和顺序表的不同它并不是存储空间满了的时候才开始扩容而是依据负载因子。 其本质原因就是因为有哈希冲突的存在当我们插入时如果发生了哈希冲突那么我们的插入查找删除效率最低都可以达到On)级别那就将我们哈希表的各种优势都变得很微弱甚至是变成劣势相比红黑树等来说有可能退化为顺序表。 因此我们引入了负载因子这一概念其本质为一个阈值定义为 负载因子散列表中的元素个数/散列表的长度 这里我们定义我们的负载因子为0.7并且当负载因子每次超过这个值时我们都将其容量扩大为2倍。 同时注意我在代码区编写的注意事项
代码如下: void HashExpansion(const size_t fac){//开始扩容if (fac 7){//我们直接采用老板思维创建一个长度为2*n的新表然后一个个插入最后直接交换//因为扩容后数组长度发生变化哈希函数也会变化哈希表对应的位置也会变化//因此不能单纯的把数组长度变为2倍需要一个个借助新表的插入函数重新建立映射关系HashTableK, V newData;newData._tables.resize(_tables.size() * 2);for (size_t i 0; i _tables.size(); i){if (_tables[i]._state EXIST){newData.Insert(_tables[i]._kv);}}_tables.swap(newData._tables);}}
更改后的insert代码 bool Insert(const pairK,V kv){if (find(kv.first)){//先判断是否查找到因为不能存储相同的结构如果查找到返回falsereturn false;}//根据除留余数法判断该插入数组的哪个位置size_t hashi Hashifunction(kv.first);//这里我们通过一点小学知识将0.7 化为整数7HashExpansion(_n * 10 / _tables.size());while (_tables[hashi]._state EXIST) {hashi;hashi hashi % _tables.size(); //如果探测到末尾则从头开始重新探测}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}
2.7 哈希表的仿函数 我们的哈希表就已经完成的差不多了还有很多细节问题比如说我们如果key类型是一个string类型的对象我们该如何经过除留余数法得到我们应该对应的下标呢 我们这里建议创建几个仿函数分别对应不同的类型得到不同的求解方法。 关于整形我们的仿函数模板如下直接放回其对应的整形值
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};
关于其它类型我们先将其转化为整形然后再将其返回如字符串类型
template
struct HashFuncstring
{size_t operator()(const string key){// BKDR转换方法size_t hash 0;for (auto e : key){hash * 31;hash e;}//cout key : hash endl;return hash;}
}; 但是请注意其他类型不同的值可能会经过转换的结果是相同的这是因为int或者其它整形一共就几十个bit位而string等等类型我只能说无穷无尽也。 因此建议用一些专用的转换方法这些是专业string转换整形方法的链接各种字符串Hash函数 - clq - 博客园
模板更改和函数更改 2.8 测试代码 打印函数 void Print(){for (size_t i 0; i _tables.size(); i){if(_tables[i]._stateEXIST){//cout [ i ]- _tables[i]._kv.first : _tables[i]._kv.second endl;printf(_tables._state[%d] , i);cout _tables[i]._kv.first - _tables[i]._kv.second endl;}else if (_tables[i]._state DELETE) {printf(_tables._state[%d] DELETE\n, i);}else {printf(_tables._state[%d] EMPTY\n, i);}}cout endl endl;}
测试代码1 void TestHT1()
{HashTableint, int ht;int a[] { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.Erase(3);ht.Print();if (ht.find(3)){cout 3存在 endl;}else{cout 3不存在 endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();
}
结果为 测试代码2
void TestHT2()
{string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString ht;HashTablestring, int ht;for (auto e : arr){//auto ret ht.Find(e);HashDatastring, int* ret ht.find(e);if (ret){ret-_kv.second;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair(apple, 1));ht.Insert(make_pair(sort, 1));ht.Insert(make_pair(abc, 1));ht.Insert(make_pair(acb, 1));ht.Insert(make_pair(aad, 1));ht.Print();
}代码结果为
2.9 完整代码
#pragma once
#includeiostream
#includevector
using namespace std;templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 11:46继续
//HashFuncstring
template
struct HashFuncstring
{size_t operator()(const string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}//cout key : hash endl;return hash;}
};//通过空和存在判断插入通过删除状态判断查找
enum State {EXIST,EMPTY,DELETE
};templateclass K,class V
struct HashData {pairK, V _kv; //每个节点存储KV结构State _state EMPTY; //默认为空
};//templateclass K, class V
templateclass K, class V, class Hash HashFuncK
class HashTable {typedef HashDataK, V Data;
public:HashTable(): _n(0){//将哈希表的大小默认给为10_tables.resize(10);}bool Insert(const pairK,V kv){if (find(kv.first)){//先判断是否查找到因为不能存储相同的结构如果查找到返回falsereturn false;}//根据除留余数法判断该插入数组的哪个位置size_t hashi Hashifunction(kv.first);//这里我们通过一点小学知识将0.7 化为整数7HashExpansion(_n * 10 / _tables.size());while (_tables[hashi]._state EXIST) {hashi;hashi hashi % _tables.size(); //如果探测到末尾则从头开始重新探测}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}Data* find(const K key) {size_t hashi Hashifunction(key);//增加一个数字 如果查找一周 返回falsesize_t start hashi;while (_tables[hashi]._state! EMPTY)//如果不为空则继续查找{if (_tables[hashi]._stateEXIST_tables[hashi]._kv.first key){return _tables[hashi];}hashi;//此时已经查找了一圈退出循环if (hashi start) {break;}hashi % _tables.size();}//为空查找失败return nullptr;}bool Erase(const K key){HashDataK, V* ret find(key);if(ret){ret-_state DELETE;--_n;return true;}else {return false;}}void HashExpansion(const size_t fac){//开始扩容if (fac 7){//我们直接采用老板思维创建一个长度为2*n的新表然后一个个插入最后直接交换//因为扩容后数组长度发生变化哈希函数也会变化哈希表对应的位置也会变化//因此不能单纯的把数组长度变为2倍需要一个个借助新表的插入函数重新建立映射关系HashTableK, V newData;newData._tables.resize(_tables.size() * 2);for (size_t i 0; i _tables.size(); i){if (_tables[i]._state EXIST){newData.Insert(_tables[i]._kv);}}_tables.swap(newData._tables);}}void Print(){for (size_t i 0; i _tables.size(); i){if(_tables[i]._stateEXIST){//cout [ i ]- _tables[i]._kv.first : _tables[i]._kv.second endl;printf(_tables._state[%d] , i);cout _tables[i]._kv.first - _tables[i]._kv.second endl;}else if (_tables[i]._state DELETE) {printf(_tables._state[%d] DELETE\n, i);}else {printf(_tables._state[%d] EMPTY\n, i);}}cout endl endl;}private://把哈希函数封装一下size_t Hashifunction(const K key){//这里我们采用除留余数法Hash kot;return kot(key)% _tables.size();}
private:vectorData _tables;size_t _n; //记录表中有效数据的个数
};void TestHT1()
{HashTableint, int ht;int a[] { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.Erase(3);ht.Print();if (ht.find(3)){cout 3存在 endl;}else{cout 3不存在 endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();
}void TestHT2()
{string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString ht;HashTablestring, int ht;for (auto e : arr){//auto ret ht.Find(e);HashDatastring, int* ret ht.find(e);if (ret){ret-_kv.second;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair(apple, 1));ht.Insert(make_pair(sort, 1));ht.Insert(make_pair(abc, 1));ht.Insert(make_pair(acb, 1));ht.Insert(make_pair(aad, 1));ht.Print();
}三. 开散列表法的哈希表 开散列法又叫 链地址法 (开链法)首先对关键码集合用散列函数计算散列地址即 key 映射的下标位置具有相同地址的关键码 (哈希冲突) 归于同一子集合每一个子集合称为一个桶 (哈希桶)各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中也就是说当发生哈希冲突时把 key 作为一个节点直接链接到通过哈希函数转换后对应下标的哈希桶中。
3.1 哈希表的基本框架
//两个仿函数直接CV
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};//HashFuncstring
template
struct HashFuncstring
{size_t operator()(const string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}//cout key : hash endl;return hash;}
};//这里就不用状态表示了因为我们无论节点是否存在都可以进行插入
/*enum State {EXIST,EMPTY,DELETE
};*///节点定义
templateclass K,class V
struct HashNode {pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK,V kv):_kv(kv),_next(nullptr){}
};//哈希表的基本框架
templateclass K, class V, class Hash HashFuncK
class HashTable {typedef HashNodeK, V Node;
private://把哈希函数封装一下size_t Hashifunction(const K key) {//这里我们采用除留余数法Hash kot;return kot(key) % _tables.size();}
private:vectorNode* _tables; //指针数组size_t _n; //表中有效数据的个数
};
3.2 哈希表的插入函数 开散列插入的前部分和闭散列一样根据哈希函数得到映射的下标位置与闭散列不同的是由于哈希表中每个下标位置都是一个哈希桶即一个单链表那么对于发现哈希冲突的元素我们只需要将其链接到哈希桶中即可这里一共有两种链接方式 将元素链接到单链表的末尾即尾插 将元素链接到单链表的开头即头插。 这里显然是选择元素进行头插因为尾插还需要找尾会导致效率降低插入部分代码如下 bool Insert(const pairK, V kv) {if (find(kv.first)) {return false;}//这里待会需要补一个扩容size_t hashi Hashifunction(kv.first);//哈希桶头插Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;} 3.3 开散列的查找 开散列的查找也很简单根据哈希函数找到下标由于下标位置存储的是链表首元素地址所以我们只需要取出首元素地址然后顺序遍历单链表即可
Node* find(const K key) {size_t hashi Hashifunction(key);Node* cur _tables[hashi];while (cur) {if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;
}
3.4 开散列的删除 开散列的删除不能单纯的依靠查找函数来进行直接删除因为在删除函数中我们不仅要对本应查找到的节点进行删除还要改变其父节点的指向让他指向删除节点的下一个节点。 bool erase(const K key) {size_t hashi Hashifunction(key);Node* cur _tables[hashi];//记录上一个节点的父节点Node* prev nullptr;while (cur) {if (cur-_kv.first key) {if (cur _tables[hashi]) {_tables[hashi] cur-_next;}else {prev-_next cur-_next;}delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;}
3.5 开散列的扩容
开散列的扩容可以和闭散列的扩容一样借用insert函数但是我们有更好的方法。 方法一 借用insert函数。 方法二 将原本链表挨个头插入新的哈希表。 if (fac 7) {//这里我们有两种方法//一是借用 以前我们开散列中的insert插入方法//此种实现比较简单但相比第二种有其对应的缺点//实现/* HashTableK, V newTable;newTable._tables.resize(_tables.size() * 2,nullptr);for (int i 0; i _tables.size(); i) {Node* cur _tables[i];while (cur) {newTable.Insert(cur);cur cur-_next;}}_tables.swap(newTable._tables);}*///二是直接把原先的哈希表中的每个单链表 按照新的哈希函数//直接头插进新链表//这个方法我们可以看出少借用insert的一部分//也就是说我们没有创建节点的消耗。//是真正的空间转移 因此效率比第一种方法高很多我们以后用这个方法vectorNode* newtable;newtable.resize(_tables.size() * 2, nullptr);for (int i 0; i _tables.size(); i) {Node* cur _tables[i];while (cur) {Node* next cur-_next;size_t hashi Hashifunction(cur-_kv.first, newtable);cur-_next newtable[hashi];newtable[hashi] newtable;cur next;}_tables[i] nullptr;}_tables.swap(newtable);}
}3.6 开散列的测试代码
print函数和以前也要有所不同。
void Print() {for (int i 0; i _tables.size(); i) {Node* cur _tables[i];cout i :;while (cur) {cout [ cur-_kv.first - cur-_kv.second ] ;cur cur-_next;}cout endl;}cout endl;}
两段测试代码 void TestHT1(){HashTableint, int ht;int a[] { 4,14,24,34,5,7,1 };for(auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.erase(3);ht.Print();if (ht.find(3)){cout 3存在 endl;}else{cout 3不存在 endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();
}void TestHT2()
{string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString ht;HashTablestring, int ht;for (auto e : arr){//auto ret ht.Find(e);HashNodestring, int* ret ht.find(e);if (ret){ret-_kv.second;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair(apple, 1));ht.Insert(make_pair(sort, 1));ht.Insert(make_pair(abc, 1));ht.Insert(make_pair(acb, 1));ht.Insert(make_pair(aad, 1));ht.Print();
}
代码一结果 测试代码二结果
3.7 完整代码
#pragma once
#includeiostream
#includevector
using namespace std;namespace BucketHash {//两个仿函数直接CVtemplateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};//HashFuncstringtemplatestruct HashFuncstring{size_t operator()(const string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}//cout key : hash endl;return hash;}};//这里就不用状态表示了因为我们无论节点是否存在都可以进行插入/*enum State {EXIST,EMPTY,DELETE};*///节点定义templateclass K,class Vstruct HashNode {pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK,V kv):_kv(kv),_next(nullptr){}};//哈希表的基本框架templateclass K, class V, class Hash HashFuncKclass HashTable {typedef HashNodeK, V Node;public:HashTable():_n(0){_tables.resize(10, nullptr);}bool Insert(const pairK, V kv) {if (find(kv.first)) {return false;}HashExpansion(_n * 10 / _tables.size());//这里待会需要补一个扩容size_t hashi Hashifunction(kv.first,_tables.size());//哈希桶头插Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}Node* find(const K key) {size_t hashi Hashifunction(key,_tables.size());Node* cur _tables[hashi];while (cur) {if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}bool erase(const K key) {size_t hashi Hashifunction(key,_tables.size());Node* cur _tables[hashi];//记录上一个节点的父节点Node* prev nullptr;while (cur) {if (cur-_kv.first key) {if (cur _tables[hashi]) {_tables[hashi] cur-_next;}else {prev-_next cur-_next;}delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;}void HashExpansion(const size_t fac){if (fac 7) {//这里我们有两种方法//一是借用 以前我们开散列中的insert插入方法//此种实现比较简单但相比第二种有其对应的缺点//实现/* HashTableK, V newTable;newTable._tables.resize(_tables.size() * 2,nullptr);for (int i 0; i _tables.size(); i) {Node* cur _tables[i];while (cur) {newTable.Insert(cur);cur cur-_next;}}_tables.swap(newTable._tables);}*///二是直接把原先的哈希表中的每个单链表 按照新的哈希函数//直接头插进新链表//这个方法我们可以看出少借用insert的一部分//也就是说我们没有创建节点的消耗。//是真正的空间转移 因此效率比第一种方法高很多我们以后用这个方法//但是哈希函数就不好处理了这里我建议直接把哈希函数改一下直接传入表的长度vectorNode* newtable;newtable.resize(_tables.size() * 2, nullptr);for (int i 0; i _tables.size(); i) {Node* cur _tables[i];while (cur) {Node* next cur-_next;size_t hashi Hashifunction(cur-_kv.first, newtable.size());cur-_next newtable[hashi];newtable[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newtable);}}void Print() {for (int i 0; i _tables.size(); i) {Node* cur _tables[i];cout i :;while (cur) {cout [ cur-_kv.first - cur-_kv.second ] ;cur cur-_next;}cout endl;}cout endl;}private://把哈希函数封装一下size_t Hashifunction(const K key,size_t size) {//这里我们采用除留余数法Hash kot;return kot(key) % size;}private:vectorNode* _tables; //指针数组size_t _n; //表中有效数据的个数};void TestHT1(){HashTableint, int ht;int a[] { 4,14,24,34,5,7,1 };for(auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.erase(3);ht.Print();if (ht.find(3)){cout 3存在 endl;}else{cout 3不存在 endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();
}void TestHT2()
{string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString ht;HashTablestring, int ht;for (auto e : arr){//auto ret ht.Find(e);HashNodestring, int* ret ht.find(e);if (ret){ret-_kv.second;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair(apple, 1));ht.Insert(make_pair(sort, 1));ht.Insert(make_pair(abc, 1));ht.Insert(make_pair(acb, 1));ht.Insert(make_pair(aad, 1));ht.Print();
}
}
