数据结构 5分钟带你搞定哈希表(建议收藏)!!!

您所在的位置：网站首页 › 常用的哈希算法 › 数据结构 5分钟带你搞定哈希表(建议收藏)!!!

数据结构 5分钟带你搞定哈希表(建议收藏)!!!

2023-08-27 11:42| 来源: 网络整理| 查看: 265

对比之前博客讨论的二叉排序树二叉平衡树红黑树，它们的查找都是先从根节点进行查找，从节点取出数据或索引与查找值进行比较。那么，有没有一种函数H，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个比较。这样就预先知道key所在的位置，直接找到数据，提升效率

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表

常见的哈希函数

一个哈希函数的好不好，取决于以下三点

哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有m个地址时，其值域必须在0 到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单

除留余数法（最常用）函数：Hash（key）=key MOD p （p.07，也就是大于我们的负载因子就需要进行扩容。扩容的时候要注意，我们需要将原来的数据移动到新的表中，但是如果是单纯的赋值获取，那哈希冲突并没有解决，而此时我们应该将旧表中的数据重新以插入的方式插入到新的表中，从而减少哈希冲突的次数在这里插入图片描述查找：哈希的优势之一也就是在于查找，查找的效率是非常高，只要通过key来计算哈希地址，如果计算的哈希位置的值与要查找的key相同，则表示已经找到，如果遇到空之后还没找到表示不存在这个要查找的数。并且要注意的是，如果查找到末尾就需要将查找的索引置为0，从头开始查找

二次探测

二次探测和线性探测都属于闭散列，其原理都一样，两者的主要区别就是探测的方式不同，线性探测是如果要插入的位置已有元素，会一个一个往后查找到新的空位置。而二次探测是通过该位置的哈希冲突次数的平方来向后查找新的位置在这里插入图片描述将产生哈希冲突的数据分散，使不堆积在一起。但是这两种方法都有很大的缺陷，就是空间利用率低。在这个基础上，引进一种新的技术来解决哈希冲突----开散列

开散列

开散列方法又叫链地址法，哈希表中存储的是链表的头结点。具有相同的哈希地址会存放在同一链表中，每个链表中的元素都具有相同的哈希地址。在这里插入图片描述该哈希表示由指针数组来组成的，每个数组中的元素都是一个链表的头指针。从该表中我们可以看出，产生哈希冲突的元素并不会占用其他元素的位置，每个链表中的元素都是哈希冲突的元素

插入：当我们插入时，计算出哈希地址，就可以直接定位到该key对应的链表的头结点，但是由于不能存放相同的key，我们需要遍历该链表中是否存在相同元素，如果不存在才进行插入。插入时我们可以进行头插或者尾插，这里头插会更简单些，创建key的一个新的结点cur，让该结点指向该链表的头结点，并将该链表的头结点更新为新创建的新结点cur 在这里插入图片描述增容：开散列的增容并不像闭散列一样要求那么严格，虽然也是有个负载因子，但是这个负载因子可以为1，也就是当有10个元素，负载因子为1时。此时10个元素都没有产生哈希冲突，这效率才是最高的，所以我们没必要限制它的上限。也就是当元素比哈希表的元素大时才需要进行扩容，来减少产生哈希冲突。哈希表中每个元素都是一个链表的头结点，我们可以创建新的一个指针数组，遍历旧的哈希表，只要遍历的链表头结点不为空，就定义一个cur，用来遍历这个单链表，遍历单链表的也需要记录该当前节点的下一个结点，否则会下一个结点会被丢弃。我们在当前节点cur中计算它的哈希地址，然后在新的指针数组中的指定位置进行头插。每遍历完一个单链表，都需要将旧的链表的头结点置为空，因为后面我们需要交换这两个指针数组，然后释放掉旧的指针数组。在这里插入图片描述查找：查找一个元素，我们可以先计算出要查找元素的哈希地址，直接定位到指定的链表的头结点，然后遍历该条链表，如果当前节点的值和要查找的元素的值相同，则表示查找，返回所找到的结点，如果没有找到则返回空删除：这里的删除是实际上的删除，我们可以先通过查找，查看要删除的值是否存在哈希表中，如果不存直接返回false，存在则需要先计算当前删除的结点的所在链表的哈希地址，找到后遍历该链表，并用一个prev结点记录要删除的前一个结点，当遍历找到我们删除的结点时，要先判断该节点是否为链表的头结点，如果为头结点，则将要删除的结点的下一个结点置为头结点，如果不是头结点则将记录的前结点prev的下一个结点的next置为要删除结点的下一个结点。最后将有效元素-1并删除要删除的结点在这里插入图片描述

代码

代码：闭散列----线性探测

enum STATE { EXIST, DELETE, EMPTY }; //哈希表：线性探测解决哈希冲突 template struct HashNode { pair _kv;//数据 STATE _state = EMPTY;//状态 }; //顺序表实现哈希 template class HashTable { public: typedef HashNode Node; HashTable(size_t n = 10) :_hTable(n) ,_size(0) {} bool insert(const pair& kv) { //0.检查容量 checkCapacity(); //1.当前元素的哈希位置 int idx = kv.first % _hTable.size(); //2.判断key是否存在 while (_hTable[idx]._state != EMPTY)//当前位置已有数据或者为删除位置，都不能存放 { //当前位置存在数据且key相同，则不能插入 if (_hTable[idx]._state == EXIST && _hTable[idx]._kv.first == kv.first) { return false; } //继续往后搜索空位置 ++idx; //走到末尾，需要从头开始找 if (idx == _hTable.size()) idx = 0; } _hTable[idx]._kv = kv; _hTable[idx]._state = EXIST; ++_size; return true; } void checkCapacity() { //负载因子[0, 1],这里定负载因子为0.7 if (_hTable.size() == 0 || _size * 10 / _hTable.size() >= 7) { //创建新表 int newC = _hTable.size() == 0 ? 10 : 2 * _hTable.size(); HashTable newHt(newC); for (size_t i = 0; i newHt.insert(_hTable[i]._kv); } } //交换两个表的内容 Swap(newHt); } } void Swap(HashTable& Ht) { swap(_hTable, Ht._hTable); swap(_size, Ht._size); } Node* find(const K& key) { //计算位置 int idx = key % _hTable.size(); while (_hTable[idx]._state != EMPTY) { //找到 if (_hTable[idx]._state == EXIST && key == _hTable[idx]._kv.first) { return &_hTable[idx]; } ++idx; if (idx == _hTable.size()) idx = 0; } //如果遇到空格则表示没找到，返回空 return nullptr; } bool erase(const K& key) { Node* node = find(key); if (node) { //伪删除 --_size; node->_state = DELETE; return true; } return false; } private: vector _hTable;//表 size_t _size;//有效元素个数 };

测试：在这里插入图片描述

代码：开散列法

#include #include using namespace std; template struct HashNode { typedef HashNode Node; K _val; Node* _next; HashNode(const K& val) :_val(val) , _next(nullptr) {} }; template class HTable { public: typedef HashNode Node; HTable(int n = 10) :_ht(n) , _size(0) {} bool insert(const K& val) { //0.检查容量 checkCapacity(); //1.计算hash位置 int idx = val % _ht.size(); //2.查找 Node* cur = _ht[idx]; while (cur) { if (cur->_val == val) return false; cur = cur->_next; } //3.插入--头插 cur = new Node(val); cur->_next = _ht[idx]; _ht[idx] = cur; ++_size; return true; } void checkCapacity() { if (_size == _ht.size()) { int newC = _size == 0 ? 10 : 2 * _size; //创建新的指针数组 vector newHt(newC); //遍历旧表 for (size_t i = 0; i Node* next = cur->_next; //计算新的位置 int idx = cur->_val % newHt.size(); //头插 cur->_next = newHt[idx]; newHt[idx] = cur; cur = next; } //旧表指针置空 _ht[i] = nullptr; } //交换新表和旧表 swap(_ht, newHt); } } Node* find(const K& val) { int idx = val % _ht.size(); Node* cur = _ht[idx]; while (cur) { if (cur->_val == val) return cur; cur = cur->_next; } return nullptr; } bool erase(const K& val) { Node* node = find(val); if (node) { int idx = val % _ht.size(); Node* cur = _ht[idx]; Node* prev = nullptr; while (cur != node) { prev = cur; cur = cur->_next; } Node* next = cur->_next; if (prev) prev->_next = next; else _ht[idx] = next; --_size; delete node; return true; } return false; } private: //指针数组 vector _ht; int _size; };

测试：在这里插入图片描述

【本文地址】

数据结构 5分钟带你搞定哈希表(建议收藏)!!!

数据结构 5分钟带你搞定哈希表(建议收藏)!!!

今日新闻

推荐新闻