C++哈希

一.哈希概念

哈希又叫做散列。本質就是通過哈希函數把關鍵字key和存儲位置建立映射關系，查找時通過這個哈希函數計算出key存儲的位置，進行快速查找。

上述概念可能不那么好懂，下面的例子可以輔助我們理解。

無論是數組還是鏈表，查找一個數都需要通過遍歷的方式，假設用單向查找最壞的情況就是查找n次，假設雙向查找最壞的情況是查找n/2次，在數據量很大的情況下查找一個數就變得比較困難。最好的情況就是希望一下子就可以找到目標數字，由此出現了哈希表。

什么是映射關系？

映射關系分為兩種：一對一和一對多

一對一：假設有2 3 90 100這四個數據，那我就開100個空間，將每一個數存在對應下標的位置，這樣查找數據的時候一下子就找到了。

一對一的弊端十分明顯，就是當數據較為分散，例如存儲1和1001，那就要開辟1001個空間，十分浪費。那么一對多的存儲就會比較好。

一對多：就是一個空間對應著多個數據。按照概念存儲數據的時候肯定會產生沖突，這就是哈希沖突。

二.除法散列法

針對沖突的情況可以用除法散列法來解決。顧名思義，假設哈希表大小為M，那么通過Key除以M的余數作為映射位置下標，也就是哈希函數為：h(key)=key%M

例如：假設數字為12，哈希表大小為10

12/10的余數是2，那么就將12映射到2的位置，但是如果還要存儲32這個數據，不難發現32/10的余數仍然是2于是就產生了沖突，那該怎么解決呢？

2.1線性探測

從發生沖突的位置開始，依次線性向后探測，直到尋找到下一個沒有存儲數據的位置為止，如果走到哈希表尾，則繞回到哈希表頭的位置。

就像上面的例子，12已經映射到2的位置，那么32就需要向后線性探測，假如下標為3的位置沒有數據存儲 那么就將32存儲到下標為3的位置。

我們最初的目標就是避免遍歷，那如果數據一直沖突的話也就無法解決這個問題了，很簡單通過擴容就可以解決這個問題。

2.1.1哈希因子

說到擴容就不得不提到哈希因子了，哈希因子就是有效數據個數/哈希表大小。

例如數據個數為2，哈希表大小為10，那么哈希因子就是0.2，一般來說當哈希因子到0.7時就需要開始擴容了。

2.1.2哈希桶

有時候擴容仍然無法解決沖突的問題，那么哈希桶就很好解決了這個問題。

哈希桶概念：哈希表中存儲一個指針，當沒有數據映射到這個位置時，這個指針為空；有多個數據映射到這個位置時，把沖突的數據連接成一個鏈表，掛在哈希表這個位置下面。

哈希桶的擴容：

 // 擴容函數void Resize() {size_t newSize = _tables.size() * 2;vector<Node*> newTables(newSize, nullptr);KeyOfT kot;Hash hs;// 重新哈希所有元素for (size_t i = 0; i < _tables.size(); ++i) {Node* cur = _tables[i];while (cur) {Node* next = cur->_next;size_t hashi = hs(kot(cur->_data)) % newSize;cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}}_tables.swap(newTables);}

?代碼中出現KeyOfT是因為set和map取出key方式不一樣，set可以直接取出key而map需要從pair中取出。

三.key不是整數的情況?

在計算位置的時候需要用到key來除以哈希表大小，當key不為整數時分兩種情況：

  • double等可以直接強制類型轉換為int
  • string不能強制類型轉換成int
template<class K>
struct HashFunc {size_t operator()(const K& key) {return (size_t)key; // 默認實現：適用于整數類型}
};// 字符串類型特化
template<>
struct HashFunc<string> {size_t operator()(const string& key) {size_t hash = 0;for (char c : key) {hash = hash * 131 + c; // 使用BKDR哈希算法處理字符串}return hash;}
};

完整代碼：

#pragma once
#include<vector>
#include<iostream>
using namespace std;
// 通用哈希函數模板（默認使用類型轉換）
template<class K>
struct HashFunc {size_t operator()(const K& key) {return (size_t)key; // 默認實現：適用于整數類型}
};// 字符串類型特化
template<>
struct HashFunc<string> {size_t operator()(const string& key) {size_t hash = 0;for (char c : key) {hash = hash * 131 + c; // 使用BKDR哈希算法處理字符串}return hash;}
};
namespace hash_bucket {template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>class HashTable {typedef HashNode<T> Node;public:// 構造函數HashTable() {_tables.resize(10, nullptr);}// 析構函數：釋放所有節點內存~HashTable() {for (auto& bucket : _tables) {Node* cur = bucket;while (cur) {Node* next = cur->_next;delete cur;cur = next;}bucket = nullptr;}_n = 0;}// 插入元素bool Insert(const T& data) {KeyOfT kot;Hash hs;const K& key = kot(data); // 提取鍵// 檢查鍵是否已存在if (Find(key)) return false;// 負載因子超過1時擴容if (_n >= _tables.size()) {Resize();}// 計算哈希值并插入size_t hashi = hs(key) % _tables.size();Node* newNode = new Node(data);newNode->_next = _tables[hashi];_tables[hashi] = newNode;++_n;return true;}// 查找元素bool Find(const K& key) {Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur) {if (kot(cur->_data) == key) {return true;}cur = cur->_next;}return false;}// 刪除元素bool Erase(const K& key) {Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur) {if (kot(cur->_data) == 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:// 擴容函數void Resize() {size_t newSize = _tables.size() * 2;vector<Node*> newTables(newSize, nullptr);KeyOfT kot;Hash hs;// 重新哈希所有元素for (size_t i = 0; i < _tables.size(); ++i) {Node* cur = _tables[i];while (cur) {Node* next = cur->_next;size_t hashi = hs(kot(cur->_data)) % newSize;cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}}_tables.swap(newTables);}private:vector<Node*> _tables;size_t _n = 0;};} // namespace hash_bucket

四.unordered_set和unordered_map的封裝

1.unordered_set

#define _CRT_SECURE_NO_WARNINGS
#include"hashi.h"
namespace happy
{template<class K>class unorder_set{struct SetKeyOfT{ const K& operator()(const K& key) {return key;}};public://取類模板的內嵌類型需要typenametypedef typename hash_bucket::HashTable<K, const K, SetKeyOfT>::Iterator iterator;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT>::const_Iterator Citerator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}Citerator begin()const{return _ht.begin();}Citerator end()const{return _ht.end();}pair<iterator,bool> insert(const K& key){return _ht.Insert(key);}private:hash_bucket::HashTable<K, const K,SetKeyOfT> _ht;};void print(const unorder_set<int>& s){unorder_set<int>::Citerator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}
}

2.unordered_map

#pragma once
#include"hashi.h"
#include <utility> // pair
#include <iostream>
using namespace std;
namespace happy
{template<class K, class V, class Hash = HashFunc<K>>class unorder_map{struct MapKeyOfT{const K& operator() (const pair<const K, V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_Iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pair<iterator, bool> insert(const pair<const K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert({ key, V() });return ret.first->second;}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_unordered_map(){unorder_map<string, string> dict;dict.insert({ "string", "字符串" });dict.insert({ "left", "左邊" });unorder_map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;// 測試 operator[]dict["right"] = "右邊";cout << "dict[\"right\"]: " << dict["right"] << endl;}
}

3.hashi?

#pragma once
#include<vector>
#include<iostream>
using namespace std;
// 通用哈希函數模板（默認使用類型轉換）
template<class K>
struct HashFunc {size_t operator()(const K& key) {return (size_t)key; // 默認實現：適用于整數類型}
};// 字符串類型特化
template<>
struct HashFunc<string> {size_t operator()(const string& key) {size_t hash = 0;for (char c : key) {hash = hash * 131 + c; // 使用BKDR哈希算法處理字符串}return hash;}
};
namespace hash_bucket {template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class T, class KeyOfT, class Hash >class HashTable;template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash = HashFunc<K>>struct HTIterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef HTIterator<K, T,Ref,Ptr, KeyOfT, Hash> iterator;Node* _node;//結點指針const HT* _ht;//哈希表指針HTIterator(Node*node,const HT*ht):_node(node),_ht(ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const iterator& s){return _node != s._node;}bool operator==(const iterator& s){return _node == s._node;}iterator& operator++(){if (_node->_next){_node = _node->_next;}else{KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else{++hashi;}}//所有桶走完if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>class HashTable {typedef HashNode<T> Node;//友元聲明template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash >friend struct HTIterator;public:typedef HTIterator<K, T,T&,T*, KeyOfT, Hash> Iterator;typedef HTIterator<K, T,const T&,const T*, KeyOfT, Hash> const_Iterator;Iterator begin(){for (size_t hashi = 0; hashi < _tables.size(); hashi++){if (_tables[hashi]){return Iterator(_tables[hashi],this);}}return end();}Iterator end(){return Iterator(nullptr, this);}const_Iterator begin()const{for (size_t hashi = 0; hashi < _tables.size(); hashi++){if (_tables[hashi]){return const_Iterator(_tables[hashi], this);}}return end();}const_Iterator end()const{return const_Iterator(nullptr, this);}// 構造函數HashTable() {_tables.resize(10, nullptr);}// 析構函數：釋放所有節點內存~HashTable() {for (auto& bucket : _tables) {Node* cur = bucket;while (cur) {Node* next = cur->_next;delete cur;cur = next;}bucket = nullptr;}_n = 0;}// 插入元素pair<Iterator,bool> Insert(const T& data) {KeyOfT kot;Hash hs;Iterator it = Find(kot(data));const K& key = kot(data); // 提取鍵// 檢查鍵是否已存在if (it != end()) return { it,false };// 負載因子超過1時擴容if (_n >= _tables.size()) {Resize();}// 計算哈希值并插入size_t hashi = hs(key) % _tables.size();Node* newNode = new Node(data);newNode->_next = _tables[hashi];_tables[hashi] = newNode;++_n;return { {newNode,this},true };}// 查找元素Iterator Find(const K& key) {Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur) {if (kot(cur->_data) == key) {return Iterator(cur, nullptr);}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 (kot(cur->_data) == 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:// 擴容函數void Resize() {size_t newSize = _tables.size() * 2;vector<Node*> newTables(newSize, nullptr);KeyOfT kot;Hash hs;// 重新哈希所有元素for (size_t i = 0; i < _tables.size(); ++i) {Node* cur = _tables[i];while (cur) {Node* next = cur->_next;size_t hashi = hs(kot(cur->_data)) % newSize;cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}}_tables.swap(newTables);}private:vector<Node*> _tables;size_t _n = 0;};} // namespace hash_bucket

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/82912.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/82912.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/82912.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

iOS 使用CocoaPods 添加Alamofire 提示錯誤的問題

iOS 使用CocoaPods 添加Alamofire 提示錯誤的問題

Sandbox: rsync(59817) deny(1) file-write-create /Users/aaa/Library/Developer/Xcode/DerivedData/myApp-bpwnzikesjzmbadkbokxllvexrrl/Build/Products/Debug-iphoneos/myApp.app/Frameworks/Alamofire.framework/Alamofire.bundle把這個改成 no 2 設置配置文件
閱讀更多...
mysql的Memory引擎的深入了解

mysql的Memory引擎的深入了解

目錄 1、Memory引擎介紹 2、Memory內存結構 3、內存表的鎖 4、持久化 5、優缺點 6、應用 前言 Memory 存儲引擎 是 MySQL 中一種高性能但非持久化的存儲方案&#xff0c;適合臨時數據存儲和緩存場景。其核心優勢在于極快的讀寫速度&#xff0c;需注意數據丟失風險和內存占…
閱讀更多...
若依項目AI 助手代碼解析

若依項目AI 助手代碼解析

基于 Vue.js 和 Element UI 的 AI 助手組件 一、組件整體結構 這個 AI 助手組件由三部分組成&#xff1a; 懸浮按鈕&#xff1a;點擊后展開 / 收起對話窗口對話窗口&#xff1a;顯示歷史消息和輸入框API 調用邏輯&#xff1a;與 AI 服務通信并處理響應 <template><…
閱讀更多...
Vue2的diff算法

Vue2的diff算法

diff算法的目的是為了找出需要更新的節點&#xff0c;而未變化的節點則可以復用 新舊列表的頭尾先互相比較。未找到可復用則開始遍歷&#xff0c;對比過程中指針逐漸向列表中間靠攏&#xff0c;直到遍歷完其中一個列表 具體策略如下&#xff1a; 同層級比較 Vue2的diff算法只…
閱讀更多...
mongodb集群之分片集群

mongodb集群之分片集群

目錄 1. 適用場景2. 集群搭建如何搭建搭建實例Linux搭建實例(待定)Windows搭建實例1.資源規劃2. 配置conf文件3. 按順序啟動不同角色的mongodb實例4. 初始化config、shard集群信息5. 通過router進行分片配置 1. 適用場景 數據量大影響性能 數據量大概達到千萬級或億級的時候&…
閱讀更多...
DEEPSEEK幫寫的STM32消息流函數，直接可用.已經測試

DEEPSEEK幫寫的STM32消息流函數，直接可用.已經測試

#include "main.h" #include "MessageBuffer.h"static RingBuffer msgQueue {0};// 初始化隊列 void InitQueue(void) {msgQueue.head 0;msgQueue.tail 0;msgQueue.count 0; }// 檢查隊列狀態 type_usart_queue_status GetQueueStatus(void) {if (msgQ…
閱讀更多...
華為歐拉系統中部署FTP服務與Filestash應用：實現高效文件管理和共享

華為歐拉系統中部署FTP服務與Filestash應用：實現高效文件管理和共享

華為歐拉系統中部署FTP服務與Filestash應用：實現高效文件管理和共享 前言一、相關服務介紹1.1 Huawei Cloud EulerOS介紹1.2 Filestash介紹1.3 華為云Flexus應用服務器L實例介紹二、本次實踐介紹2.1 本次實踐介紹2.2 本次環境規劃三、檢查云服務器環境3.1 登錄華為云3.2 SSH遠…
閱讀更多...
React---day5

React---day5

4、React的組件化 組件的分類&#xff1a; 根據組件的定義方式&#xff0c;可以分為&#xff1a;函數組件(Functional Component )和類組件(Class Component)&#xff1b;根據組件內部是否有狀態需要維護&#xff0c;可以分成&#xff1a;無狀態組件(Stateless Component )和…
閱讀更多...
測試策略：AI模型接口的單元測試與穩定性測試

測試策略：AI模型接口的單元測試與穩定性測試

測試策略：AI模型接口的單元測試與穩定性測試 在構建支持AI能力的系統中，開發者不僅要關注業務邏輯的正確性，也必須保障AI模型接口在各種環境下都能穩定運行。這就要求我們在開發階段制定清晰的測試策略，從功能驗證到性能保障，逐步推進系統可用性、可維護性與可擴展性的提…
閱讀更多...
UniApp 生產批次管理模塊技術文檔

UniApp 生產批次管理模塊技術文檔

UniApp 生產批次管理模塊技術文檔 1. 運行卡入站頁面 (RunCardIn) 1.1 頁面結構 <template><!-- 頁面容器 --><view class"runCardIn" :style"{ paddingTop: padding }"><!-- 頁頭組件 --><pageHeader :title"$t(MENU:…
閱讀更多...
針對Helsinki-NLP/opus-mt-zh-en模型進行雙向互翻的微調

針對Helsinki-NLP/opus-mt-zh-en模型進行雙向互翻的微調

引言 ?題目聽起來有點怪怪的&#xff0c;但是實際上就是對Helsinki-NLP/opus-mt-en-es模型進行微調。但是這個模型是單向的&#xff0c;只支持中到英的翻譯&#xff0c;反之則不行。這樣的話&#xff0c;如果要做中英雙向互翻就需要兩個模型&#xff0c;那模型體積直接大了兩倍…
閱讀更多...
Object轉Map集合

Object轉Map集合

對象與 Map 轉換詳解&#xff1a; Object.entries() 和 Object.fromEntries() 1&#xff0c;Object.fromEntries() 的主要用途就是將鍵值對集合&#xff08;如 Map&#xff09;轉換為普通對象。 2&#xff0c;Object.entries() 返回一個二維數組&#xff0c;其中每個子數組包…
閱讀更多...
優先隊列用法

優先隊列用法

第 5 行定義了一個隊首是最大值的優先隊列,第 10 行的輸出如下: 27 - wuhan 21 - shanghai 11 - beijing 第 13 行定義了一個隊首是最小值的優先隊列,第 19 行的輸出如下: 11 - beijing 21 - shanghai 27 - wuhan #include <bits/stdc.h> using namespace std; int…
閱讀更多...
Spring Boot3.4.1 集成redis

Spring Boot3.4.1 集成redis

Spring Boot3.4.1 集成redis 第一步 引入依賴 <!-- redis 緩存操作 --> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId> </dependency> <!-- pool 對象池 …
閱讀更多...
Replacing iptables with eBPF in Kubernetes with Cilium

Replacing iptables with eBPF in Kubernetes with Cilium

source: https://archive.fosdem.org/2020/schedule/event/replacing_iptables_with_ebpf/attachments/slides/3622/export/events/attachments/replacing_iptables_with_ebpf/slides/3622/Cilium_FOSDEM_2020.pdf 使用Cilium&#xff0c;結合eBPF、Envoy、Istio和Hubble等技術…
閱讀更多...
英一真題閱讀單詞筆記 05年

英一真題閱讀單詞筆記 05年

2005 年 Text 1 第一段 序號 單詞 音標 詞義 1 fat [ft] a. 豐厚的&#xff0c;巨額的&#xff1b;肥胖的 2 pay [pe?] n. 薪水 3 rise [ra?z] n. 上漲&#xff0c;增加&#xff1b;斜坡 4 pleasure [ple??(r)] n. 快樂&#xff1b;樂事 5 pleasure a…
閱讀更多...
FastAPI集成APsecheduler的BackgroundScheduler+mongodb(精簡)

FastAPI集成APsecheduler的BackgroundScheduler+mongodb(精簡)

項目架構&#xff1a; FastAPI(folder) >app(folder) >core(folder) >models(folder) >routers(folder) >utils(folder) main.py(file) 1 utils文件夾下新建schedulers.py from apscheduler.schedulers.background import BackgroundScheduler from apschedu…
閱讀更多...
聊一聊接口測試中耗時請求如何合理安排？

聊一聊接口測試中耗時請求如何合理安排？

目錄 一、異步處理與輪詢機制 輪詢檢查機制 二、 并行化測試執行 三、模擬與樁技術&#xff08;Mock/Stub&#xff09; 四、動態超時與重試策略 五、測試架構設計優化 分層測試策略 并行化執行 網絡優化 六、測試用例分層管理 金字塔策略 七、 緩存與數據復用 響應…
閱讀更多...
深入詳解DICOMweb：WADO與STOW-RS的技術解析與實現

深入詳解DICOMweb：WADO與STOW-RS的技術解析與實現

&#x1f9d1; 博主簡介&#xff1a;CSDN博客專家、CSDN平臺優質創作者&#xff0c;高級開發工程師&#xff0c;數學專業&#xff0c;10年以上C/C, C#, Java等多種編程語言開發經驗&#xff0c;擁有高級工程師證書&#xff1b;擅長C/C、C#等開發語言&#xff0c;熟悉Java常用開…
閱讀更多...
Splunk Validated Architecture (SVA)：構建企業級可觀測性與安全的基石

Splunk Validated Architecture (SVA)：構建企業級可觀測性與安全的基石

Splunk Validated Architecture (SVA) 是 Splunk 官方提供的一套經過嚴格測試、性能驗證和最佳實踐指導的參考架構藍圖。它并非單一固定方案&#xff0c;而是根據企業數據規模、性能需求、高可用性目標和合規要求&#xff0c;提供一系列可落地的部署模型。SVA 的核心價值在于為…
閱讀更多...
最新文章

Copyright @ 2022~2023