当前位置： 首页 > ai >正文

哈 希 表

ai 2025/7/17 15:31:23

哈希(hash)⼜称散列，是⼀种组织数据的⽅式。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找。

使用的方法是除留余数法（让该值%表的大小），余数是多少就存在哪一个位置。

但是这样会出现哈希冲突（不同的值可能会映射到相同的位置）。

为了解决哈希冲突有两种方法：
1，闭散列：开放定址法（自己位置被占了，就去占到其他的一个空位置存储）（冲突次数越多，效率越低）。

2.开散列：哈希桶/拉链法。（将余数一样的像链表一样挂到表的下面）

为解决哈希冲突便引入了负载因子。负载因子=表格中数据的个数/size()的大小。

不能是表格中数据的个数/capacity()的大小 是因为capacity比size大，除了之后可能会越界，查的时候找不到。

负载因子越大，冲突越高。

开放定址法实现哈希表的代码如下：

template<class K>//仿函数:将其他类型转整形
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};enum State//定义表格的状态;存在、删除、空{EMPTY,EXIST,DELETE};template<class K,class V>//定义哈希表中的元素struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K,class V,class Hash = HashFunc<K>>class HashTable{public:HashTable()//先扩容{_tables.resize(10);}bool Insert(const pair<K, V>& kv)//插入{if (_n * 10 / _tables.size() >= 7)//如果负载因子>=7，就需要扩容{// 旧表重新计算负载到新表HashTable<K, V, Hash> newHT;newHT._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._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;}HashData<K, V>* Find(const K& key)//查找{Hash hs;size_t hashi = hs(key) % _tables.size();// 线性探测while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST &&_tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key)//删除{HashData<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = DELETE;--_n;return true;}}private:vector<HashData<K, V>> _tables;size_t _n = 0;  // 有效数据个数};

哈希桶实现：

template<class K,class V>
struct HashNode
{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){ }
};template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{typedef HashNode<K, V> Node;
public:HashTable()//构造函数，提前扩容。{_tables.resize(10, nullptr);}~HashTable()//析构函数：先把每一个桶的所有节点释放。{for (int 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 pair<K, V>& kv)//插入{Hash hs;size_t hashi = hs(kv.first) % _tables.size();//负载因子==1就扩容if (_n == _tables.size()){vector<Node*>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 hashi = hs(cur->_kv.first) % newtables.size();cur->_next = newtables[hashi];//头插到新表newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}Node* Find(const K& key)//此时key已经是确定到_tables[i]了,所以不需要for循环{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 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 == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}
private:vector<Node*> _tables;//指针数组size_t _n = 0;//存储数据个数
};

unordered_map和unordered_set和map与set的区别是：  map与set是有序的。unordered_map和unordered_set是无序的。

 unordered_map和unordered_set的底层就是哈希桶。

 unordered_map和unordered_set的模拟实现：

封装的哈希表：

namespace Map_Set_DiCeng
{template<class T>struct HashNode{T _data;HashNode<K, V>* _next;HashNode(const T& data):_data(data),_next(nullptr){ }};template<class K, class T, class Hash, class KeyOfT>class HashTable{typedef HashNode<T> Node;public://内部类template<class Ptr,class Ref>实现迭代器struct __HTIterator{typedef HashNode<T> Node;typedef __HTIterator Self;Node* _node;const HashTable* _pht;__HTIterator(Node* node, const HashTable* pht):_node(node), _pht(pht){}Node* _node;const HashTable* _pht;__HTIterator(Node* node, const HashTable* pht):_node(node), _pht(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->_next){// 当前桶没走完，找当前桶的下一个节点_node = _node->_next;}else{// 当前桶走完了，找下一个不为空的桶的第一个节点KeyOfT kot;Hash hs;size_t i = hs(kot(_node->_data)) % _pht->_tables.size();//kot(_node->_data)再hs因为kot类型可能是pair,所以先判断是pait还是T，在进行hs类型转换++i;for (; i < _pht->_tables.size(); i++){if (_pht->_tables[i])//如果遍历到该桶是个空的就跳过进行下一轮循环。break;}if (i == _pht->_tables.size()){// 所有桶都走完了，最后一个的下一个用nullptr标记_node = nullptr;}else{_node = _pht->_tables[i];}}return *this;}bool operator!=(const Self& s){return _node != s._node;}};typedef __HTIterator<T*, T&> iterator;typedef __HTIterator<const T*, const T&> const_iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur)//如果不为空{// this 相当于是 HashTable*return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}const_iterator begin() const//const迭代器{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){// this -> const HashTable*return const_iterator(cur, this);}}return end();}const_iterator end() const{return const_iterator(nullptr, this);}HashTable()//构造函数，提前扩容。{_tables.resize(10, nullptr);}~HashTable()//析构函数：先把每一个桶的所有节点释放。{for (int i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}pair<iterator, bool> Insert(const T& data)//插入{KeyOfT kot;iterator it = Find(kot(data));if (it != end())return make_pair(it, false);Hash hs;//负载因子==1就扩容if (_n == _tables.size()){vector<Node*>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 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(kot(data)) % _tables.size();Node* newnode = new Node(data);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return end();}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 == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables;//指针数组size_t _n = 0;//存储数据个数};
}

        map的模拟实现：

template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename hash_Map_Set_DiCeng::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;//比较复杂iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};

http://www.xdnf.cn/news/10320.html

相关文章：

  • 快速掌握 GO 之 RabbitMQ 结合 gin+gorm 案例
  • 设计模式——策略设计模式（行为型）
  • GitLab CI、GitHub Actions和Jenkins进行比较
  • DAY 18 推断聚类后簇的类型
  • 核心机制:TCP 断开连接(四次挥手)
  • learn react course
  • TDengine 集群容错与灾备
  • 多自主水下航行器（AUV）协同围捕策略
  • 汽车安全：功能安全FuSa、预期功能安全SOTIF与网络安全Cybersecurity 解析
  • 【前端】成长路线
  • C#语音录制：使用NAudio库实现语音录制功能详解
  • MyBatis、MyBatis-Plus与MyBatis-Flex的区别
  • .net Avalonia应用程序生命周期
  • 经典面试题：一文了解常见的缓存问题
  • 视觉分析明火检测助力山东化工厂火情防控
  • 【前端】Vue中使用CKeditor作为富文本编辑器
  • Python应用for循环临时变量作用域
  • MATLAB中properties函数用法
  • 408《数据结构》——第二章：线性表
  • 【harbor】--配置https
  • 【LLM相关知识点】关于LLM项目实施流程的简单整理（一）
  • 操作系统学习（七）——互斥
  • 深入Java性能调优：原理详解与实战
  • STM32F103C8T6，bxCAN收发配置实例，包含ID过滤
  • 香港中乐团六月京津巡演 携多位国际艺术家献演
  • 边缘计算场景下的大模型落地：基于 Cherry Studio 的 DeepSeek-R1-0528 本地部署
  • spring事务的面试题 —— 事务的特性、传播机制、隔离机制、注解
  • 趋势直线指标
  • 机器视觉2D定位引导-合同要点重度讲解-技术要点及注意事项
  • Web开发实战：HTML+CSS+JS期末复习全梳理