微商城网站建设价位,58做二手车网站应该怎么推广,vps搭建网站教程,不要钱做网站软件数据结构/C#xff1a;哈希表 哈希表概念哈希函数直接定址法除留余数法 哈希冲突闭散列 - 开放定址法基本结构查找插入删除总代码展示 开散列 - 哈希桶基本结构查找插入删除代码展示 哈希表概念
在顺序表中#xff0c;查找一个数据的时间复杂度为O(N)#xff1b;在平衡树这… 数据结构/C哈希表 哈希表概念哈希函数直接定址法除留余数法 哈希冲突闭散列 - 开放定址法基本结构查找插入删除总代码展示 开散列 - 哈希桶基本结构查找插入删除代码展示 哈希表概念
在顺序表中查找一个数据的时间复杂度为O(N)在平衡树这种树形结构中查找一个数据的时间复杂度为O( log N \log_{}{N} logN )。尽管平衡树的搜索已经很优秀了但是我们理想中的搜索方法是不经过任何比较一次直接从数据结构中拿到想要的元素也就是把搜索的复杂度优化为O(1)。这看似天方夜谭但是哈希表可以做到本博客就讲解哈希表以及它的多种实现方案。
如果某个字符串中只有小写字母a-z请你统计所有字母出现的次数。你会怎么做
我们可以创建一个长为26的数组arr然后让a对应arr[0]b对应arr[1]以此类推每个位置都对应一个字母然后遍历一遍字符串。假设当前字母为i按照转换规则arr[i - a]进行转换。
其实这就是一个哈希表的思想我们把数据a - z通过i - a这个映射关系转化为了一个数字然后再把对应的数组下标赋予对应的意义。此时这个数组就是一个哈希表。
所以哈希表可以简单理解为把数据转化为数组的下标然后用数组的下标对应的值来表示这个数据。如果我们想要搜索这个数据直接计算出这个数据的下标然后就可以直接访问数组对应的位置所以可以用O(1)的复杂度直接找到数据。
其中这个数据对应的数字叫做关键码(Key)这个把关键码转化为下标的规则叫做哈希函数(Hash)。
要注意的是有一些数据并不是整型比如字符串对象等等。对于这种数据我们要先用一套规则把它们转化为整数关键码然后再通过哈希函数映射为数组下标。 哈希函数
哈希函数原则
哈希函数转换后生成的地址下标必须小于哈希表的最大地址下标哈希函数计算出来的地址下标必须均匀地分布哈希函数尽可能简单
接下来我们看一些常见的哈希函数
直接定址法 取关键字的某个线性函数为哈希表的地址 Hash (Key) A × Key B \text { Hash (Key) }A × \text { Key }B Hash (Key) A× Key B
这种哈希函数特点就是简单均匀。但是由于我们没有限制这个地址的范围其有可能对数组越界访问所以要提前知道数据的范围。
比如我们刚刚通过字母的ASCII码直接减去a的ASCII码的过程就是一个直接定址过程。在这之前我们知道小写字母只有26个所以没有发生越界访问。
这种哈希函数在一些数据简单的算法题中高频使用。
除留余数法 假设哈希表的地址数目为m取Key对m取模后得到的值作为下标 Hash (Key) K e y % m \text { Hash (Key) }\text Key\ \% \ m Hash (Key) Key % m
该方法通过取模简单地把地址控制在了目标范围内STL库中使用的就是这种方法本博客后续也使用这种方法。
此外还有一些哈希函数但是都不常用了此处不做讲解了。 哈希冲突
现在我们采用除留余数法作为哈希函数我们尝试对一个长度为10的哈希表插入值 其哈希函数为 Hash (Key) K e y % 10 \text { Hash (Key) }\text Key\ \% \ 10 Hash (Key) Key % 10
现在我们插入1815124四个数字
根据哈希函数的规则我们把这四个数字映射到了合适的位置。现在我们载插入数字14你会发现14 % 10 4但是下标为4的位置已经被124占用了这该怎么办
这种多个数据占用一个位置的情况叫做哈希冲突解决哈希冲突有两种方法分别是闭散列和开散列我们现在就讲解两种方案以及对应哈希表的实现方法。 闭散列 - 开放定址法
闭散列也叫做开放定址法当发生哈希冲突时如果哈希表没有被装满说明哈希表中还有空位置那么我们可以把发生冲突的数据放到下一个空位置去。
比如在刚刚的情况中我们插入14发现下标为4的位置被占用了于是到下标为5的位置发现下标为5的位置也被占用了于是到下标为6的位置。最后就插入下标6的位置 当我们查找14的时候先通过哈希函数计算出下标为4然后发现哈希表中下标为4的位置不是14于是向后查找发现下标为5的位置不是14再往后查找发现14在下标为6的位置。
再比如我们查找44的时候先通过哈希函数计算出下标为4然后发现哈希表中下标为4的位置不是44于是向后查找发现下标为5的位置不是44再往后查找发现下标为6的位置不是44再向后查找发现下标为7的位置没有数据了于是推断出44数据不存在于哈希表中。
基本结构
首先我们需要一个枚举来标识哈希表的不同状态
enum State
{EMPTY,EXIST,DELETE
};EMPTY空节点 EXIST数值存在 DELETE数值被删除 为什么要这样标识节点呢 我们看到以下情况
现在我们将15这个数据从哈希表中删除其面临着两个问题 删除后应该替换为什么数据如果我们替换后的数据与插入的数据冲突怎么办 因此我们不能直接替换来删除一个数据而是用一个额外的变量来标识状态EMPTY空EXIST存在。
现在我们删除后试试看 现在我们面临第二个问题 我们删除节点后会面临原本连续的数据被截断的问题。如果我们现在要查找数据14其会从下标为4的位置开始查找但是查找到下标为5的位置发现没有数据了于是停止查找。 这个过程中由于删除后的数据被标识为EMPTY此时查找就发生了问题因此我们要把删除DELETE和空EMPTY区分开来当查找数据时发现DELETE的节点应该继续往后查找。
最后我们就得到了节点的三种状态标识
现在我们再看到哈希表的基本结构
enum State
{EMPTY,EXIST,DELETE
};templateclass K, class V
struct HashData
{pairK, V _kv;State _state EMPTY;//标记状态
};templateclass K, class V
class HashTable
{
public:HashTable(size_t size 10){_tables.resize(size);}private:vectorHashDataK, V _tables;//哈希表size_t _n 0;//元素个数
};哈希表的节点HashData pairK, V _kv哈希表存储的键值对 State _state EMPTY标识节点的状态默认状态为空-EMPTY 在哈希表的类HashTable中存在两个成员变量 vectorHashDataK, V _tables哈希表表中存储着HashDataK, V也就是键值对 size_t _n 0哈希表中的元素个数初始值为0 HashTable构造函数
HashTable(size_t size 10)
{_tables.resize(size);
}一开始给哈希表10个大小的空间装不下再扩容。 查找
想要在哈希表中查找数据无非就遵顼以下规则 通过哈希函数计算出数据对应的地址 去地址处查找如果地址处不是目标值往后继续查找 遇到EMPTY还没有找到说明数据不存在哈希表中 遇到DELETE和EXIST继续往后查找 代码如下
HashDataK, V* Find(const K key)
{size_t hashi key % _tables.size();while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._kv.first key _tables[hashi]._state EXIST)return _tables[hashi];hashi;hashi % _tables.size();}return nullptr;
}代码解析 HashDataK, V* Find(const K key) 查找函数输入一个key值返回指向该值节点的指针 size_t hashi key % _tables.size(); 通过除留余数法计算出key对应的下标hashi while (_tables[hashi]._state ! EMPTY) 只要hashi对应的下标不为EMPTY就继续往后查找 if (_tables[hashi]._kv.first key _tables[hashi]._state EXIST) 只有当前节点存在EXIST并且节点内的值等于目标值就返回该节点的地址 hashi;hashi % _tables.size(); 如果当前节点不是目标值往后一个节点查找。但是这个过程有可能越界此时如果遇到哈希表末尾则通过取模计算从头部继续查找 return nullptr; 如果前面没有找到说明目标值不存在返回空指针 但是当前的代码存在一个问题哈希表作用于泛型key % _tables.size()有可能是违法的行为因为key可能不是一个数字。这该怎么办
解决以上问题就是把传进来的数据转化为整型。对此我们可以在模板中多加一个仿函数的参数用户可以在仿函数中自定义数据 - 整型的转换规则然后我们在对这个整型使用除留余数法获取地址。
在那之前我们可以先写一个仿函数用于处理整型 - 整型的转化
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};因为本身就是整型所以返回自己就可以了。 另外的由于我们经常使用哈希表存储字符串所以我们还可以写一个string - 整型的转换规则
经过研究有人发现把字符串的每一位的ASCII加起来并且每次加和后乘以一个数值得到的数值分散性很强
struct HashFunc
{size_t operator()(const string s){size_t hash 0;for (auto e : s)//把字符串的每一个字符ASCII码值加起来{hash e;hash * 131; // 31, 131313(任意由13间断排列的数字)}return hash;}
};其中这个数值由1和3间断地排列这样得出来的值分散性最强我此处采用数值131。
在STL中整型- 整型转化的函数被写为了一个模板而这个string - 整型被写为了一个模板特化
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto e : s)//把字符串的每一个字符ASCII码值加起来{hash e;hash * 131; // 31, 131313(任意由13间断排列的数字)}return hash;}
};现在我们给哈希表加上第三个模板参数Hash用于传入仿函数
templateclass K, class V, class Hash
class HashTable
{};然后我们将这个HashFuncK仿函数作为哈希表的第三个模板参数的默认值
templateclass K, class V, class Hash HashFuncK
class HashTable
{};由于我们的string - 整型被写为了一个模板特化此时我们的string也可以通过默认值直接转化不用自己传入模板参数。
原先我们获得下标的代码如下
size_t hashi key % _tables.size();现在我们要通过仿函数来统一获得整型再进行除留余数操作
Hash hs;
size_t hashi hs(key) % _tables.size();这样我们就可以让多种数据转为整型了。 插入
插入的基本逻辑如下 先通过Find接口查找目标值在不在哈希表中如果目标值已经存在返回flse表示插入失败通过哈希函数计算出目标值对应的下标向下标中插入数据 如果下标对应的位置已经有数据往后查找直到某一个位置为EMPTY或者DELETE如果下标对应的位置没有数据直接插入 插入后把对应位置的状态转化为EXIST 代码如下
bool Insert(const pairK, V kv)
{if (Find(kv.first))return false;Hash hs;//仿函数实例化出的对象size_t hashi hs(kv.first) % _tables.size();//获得目标值对应的下标while (_tables[hashi]._state EXIST)//往后查找合适的位置插入{hashi;hashi % _tables.size();}_tables[hashi]._kv kv;//插入_tables[hashi]._state EXIST;//改变状态_n;//哈希表中的元素个数1return true;
}目前还有一个问题那就是如果哈希表满了怎么办
如果哈希表满了我们就要进行扩容操作但是我们并不是在哈希表满的时候扩容。其实我们可以发现当这个哈希表越满我们查找数据的效率就越低甚至说如果查找一个不存在的数据我们可能要用O(N)的复杂度遍历整个哈希表。因此我们因该把哈希表的负载率控制在一定值当超过一定值我们就要进行扩容操作。在此我把负载率控制在70%负载率超过70%我们就进行扩容
if ((double)_n / _tables.size() 0.7)
{//扩容
}要注意的是_n和_tables.size()都是整型它们之间进行除法是整数除法所以我们要把前者强制转化为double让其进行小数除法。
对于扩容我有两个方案 新建一个更大的vector把所有数值重新映射到哈希表中新建一个更大的哈希表把所有数值insert到哈希表中然后把新的哈希表里面的vector交换给自己 两者对比有一个重要的区别就是我们已经写过哈希表的insert函数了我们只要遍历一遍原哈希表的数据就可以完成插入操作。但是对于vector我们想要重新映射就需要重写一个vector的映射逻辑。因此最好采用后者
if ((double)_n / _tables.size() 0.7)
{size_t newSize _tables.size() * 2;HashTableK, V, Hash newHT(newSize);for (auto e : _tables){if (e._state EXIST)newHT.Insert(e._kv);}_tables.swap(newHT._tables);
}代码解析 size_t newSize _tables.size() * 2: 计算出新的哈希表的大小这里采用二倍扩容 HashTableK, V, Hash newHT(newSize) 创建一个新的哈希表newHT其大小为原哈希表的两倍 for (auto e : _tables) 遍历原哈希表其实就是遍历哈希表里面的数组 if (e._state EXIST) {newHT.Insert(e._kv)} 只要当前节点的值状态为EXIST就把它插入到新表 _tables.swap(newHT._tables); 把新创建的哈希表的vector交换给当前哈希表。 这里有一个细节问题那就是我们临时创建的哈希表newHT生命周期仅在这个if的括号内。当出了生命周期newHT就会调用析构函数自动销毁内部的vector而我们把原先的较小的那个vector交换给了这个newHT此时这个newHT还起到了销毁原先的小vector的功能。
插入总代码
bool Insert(const pairK, V kv)
{if (Find(kv.first))return false;if ((double)_n / _tables.size() 0.7){size_t newSize _tables.size() * 2;HashTableK, V, Hash newHT(newSize);for (auto e : _tables){if (e._state EXIST)newHT.Insert(e._kv);}_tables.swap(newHT._tables);}Hash hs;size_t hashi hs(kv.first) % _tables.size();while (_tables[hashi]._state EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;
}删除
删除也是一个比较简单的逻辑 先通过Find接口找到要删除的值 如果没找到返回false表示删除失败如果找到把对应节点的状态改为DELETE 最后再把哈希表的_n - 1表示存在的节点数少了一个。 代码如下
bool Erase(const K key)
{HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;_n--;return true;}return false;
}至此我们就完成了一个闭散列的哈希表。 总代码展示
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto e : s)//把字符串的每一个字符ASCII码值加起来{hash e;hash * 131; // 31, 131313(任意由13间断排列的数字)}return hash;}
};enum State
{EMPTY,EXIST,DELETE
};templateclass K, class V
struct HashData
{pairK, V _kv;State _state EMPTY;//标记状态
};templateclass K, class V, class Hash HashFuncK
class HashTable
{
public:HashTable(size_t size 10){_tables.resize(size);}HashDataK, V* Find(const K key){Hash hs;size_t hashi hs(key) % _tables.size();while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._kv.first key _tables[hashi]._state EXIST)return _tables[hashi];hashi;hashi % _tables.size();}return nullptr;}bool Insert(const pairK, V kv){if (Find(kv.first))return false;if ((double)_n / _tables.size() 0.7){size_t newSize _tables.size() * 2;HashTableK, V, Hash newHT(newSize);for (auto e : _tables){if (e._state EXIST)newHT.Insert(e._kv);}_tables.swap(newHT._tables);}Hash hs;size_t hashi hs(kv.first) % _tables.size();while (_tables[hashi]._state EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;_n--;return true;}return false;}private:vectorHashDataK, V _tables;size_t _n 0;//元素个数
};开散列 - 哈希桶
其实闭散列并不是一个优秀的方案来处理哈希冲突因为一个数值的位置被占用后这个数值就会去占用别人的位置这种拆东墙补西墙的行为会导致恶性循环查找的效率也很低。最差的情况实际复杂度会退化到O(N)。
在STL库中采用的是更加优秀的开散列方案。
哈希表的数组vector中不再直接存储数据而是存储一个链表的指针。当一个数值映射到对应的下标后就插入到这个链表中。其中每一个链表称为一个哈希桶每个哈希桶中存放着哈希冲突的元素。 一般而言我们的链表使用单向链表就够了因为一个哈希桶中一般不会出现太多元素。
现在我们来尝试实现这个开散列哈希表 基本结构
对于每一个节点其要存储当前节点的值也要存储下一个节点的指针基本结构如下
templateclass K, class V
struct HashNode
{HashNodeK, V* _next;pairK, V _kv;HashNode(const pairK, V kv):_kv(kv),_next(nullptr){}
};_kv节点存储但键值对 _next指向下一个节点的指针 哈希表
templateclass K, class V, class Hash HashFuncK
class HashTable
{typedef HashNodeK, V Node;
public:HashTable(size_t size 10){_tables.resize(size);}private:vectorNode* _tables; //链表指针数组size_t _n 0;//元素个数
};基本结构和开散列是一致的但是vector内部存储的不再是节点了而是指向节点的指针Node*。
对于这个哈希表由于我们开辟了外部资源所以我们还要自己写一个析构函数防止内存泄漏
~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;}
}基本逻辑就是遍历整个vector然后把每个元素指向的链表都delete释放掉。 查找
查找的基本逻辑如下 先通过哈希函数计算出数据对应的下标通过下标找到对应的链表遍历链表找数据 如果某个节点的数据匹配上了返回该节点指针如果遍历到了nullptr返回空指针表示没找到 代码如下
Node* Find(const K key)
{Hash hs;size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key)return cur;cur cur-_next;}return nullptr;
}这个很基础就不详细解释了。 插入
插入的基本逻辑如下 先通过Find接口查找目标值在不在哈希表中如果目标值已经存在返回flse表示插入失败通过哈希函数计算出目标值对应的下标向下标中插入数据 我们思考一个问题我们将数据插入到链表中时是头插还是尾插 由于我们不知道访问同一个哈希桶中的数据时会访问哪一个所以哈希桶中数据的先后是没有区别的。但是尾插需要找尾会增加插入的时间因此我们直接头插就可以了。
代码如下
bool Insert(const pairK, V kv)
{if (Find(kv.first))return false;Hash hs;size_t hashi hs(kv.first) % _tables.size();//计算下标Node* newNode new Node(kv);//创建节点newNode-_next _tables[hashi];//头插_tables[hashi] newNode;_n;//更新元素个数return true;
}经过以上逻辑我们就可以插入一个数据到哈希表中了。但是我们面临着相同的问题如果哈希表太满时间复杂度会发生退化因此我们要在负载率过高时进行扩容。
与闭散列不同的是开散列的哈希桶之间不会互相影响因此这个负载率可以高一些。在STL中其负载率控制在100%。
if (_n _tables.size())//负载率100%
{//扩容
}我们可以像之前一个创建一个新的哈希表然后把所有的值都插入进去这当然是一个不错的办法。但是闭散列与开散列有一个很大的区别就是哈希桶会额外创建大量的链表节点。如果我们单纯的进行插入就要把原先的所有节点释放掉再创建新的节点。这样会浪费很多时间。我们最好把原先创建的节点利用起来因此我们要重写一个逻辑把原先的节点进行迁移。
先创建一个新的vector
vectorNode* newTables(_tables.size() * 2, nullptr);新的vector的大小是原先的两倍所有节点初始化为nullptr
再用两层循环遍历所有节点 for (size_t i 0; i _tables.size(); i)
{Node* cur _tables[i];while (cur){Node* next cur-_next;cur next;}
}对于每一个节点我们要得到它的值然后计算出它在新的表中的下标插入到对应的下标位置
size_t hashi hs(cur-_kv.first) % newTables.size();//计算下标cur-_next newTables[hashi];//头插
newTables[hashi] cur;//头插要注意的是我们每遍历完一个哈希桶要把原先的vector中指向哈希桶的指针置空否则原先的vector在销毁的时候调用析构函数会把我们转移的节点给销毁掉。
扩容总代码如下
if (_n _tables.size())
{vectorNode* newTables(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi hs(cur-_kv.first) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr; //防止移交的节点被析构}_tables.swap(newTables);
}删除
删除逻辑 通过哈希函数计算出对应的下标到对应的哈希桶中查找目标值 如果找到删除对应的节点如果没找到返回false表示删除失败 _n - 1表示删除了一个元素 代码如下
bool Erase(const K key)
{Hash hs;size_t hashi hs(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){if (prev)prev-_next cur-_next;else_tables[hashi] cur-_next;delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;
}这个逻辑也比较简单但是要注意的是我们删除链表节点后要把这个节点的前后连接起来所以我们需要一个额外的parent来标识前面一个节点。 代码展示
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto e : s)//把字符串的每一个字符ASCII码值加起来{hash e;hash * 131; // 31, 131313(任意由13间断排列的数字)}return hash;}
};templateclass K, class V
struct HashNode
{HashNodeK, V* _next;pairK, V _kv;HashNode(const pairK, V kv):_kv(kv),_next(nullptr){}
};templateclass K, class V, class Hash HashFuncK
class HashTable
{typedef HashNodeK, V Node;
public:HashTable(size_t size 10){_tables.resize(size);}~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;}}Node* Find(const K key){Hash hs;size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key)return cur;cur cur-_next;}return nullptr;}bool Insert(const pairK, V kv){if (Find(kv.first))return false;Hash hs;//哈希桶情况下负载因子到1才扩容if (_n _tables.size()){vectorNode* newTables(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi hs(cur-_kv.first) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr; //防止移交的节点被析构}_tables.swap(newTables);}size_t hashi hs(kv.first) % _tables.size();Node* newNode new Node(kv);newNode-_next _tables[hashi];_tables[hashi] newNode;_n;return true;}bool Erase(const K key){Hash hs;size_t hashi hs(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){if (prev)prev-_next cur-_next;else_tables[hashi] cur-_next;delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;}private:vectorNode* _tables; //链表指针数组size_t _n 0;//元素个数
};
