C++數據結構——哈希桶HashBucket

目錄

一、前言

1.1 閉散列

1.2 開散列

1.3 string 與 非 string?

二、哈希桶的構成

2.1 哈希桶的節點

2.2 哈希桶類

三、 Insert 函數

3.1 無需擴容時

3.2 擴容

復用 Insert：

逐個插入：

優缺點比對：

第一種寫法優點

第一種寫法缺點

第二種寫法優點

第二種寫法缺點

3.3 完整代碼

四、 Erase 函數

4.1 析構函數

4.2 Erase 函數

五、 Find 函數

六、完整代碼?

一、前言

上一篇文章講的哈希表，屬于閉散列。可以解決哈希沖突有兩種方式：閉散列和開散列。現在要學習的哈希桶就是開散列。

1.1 閉散列

閉散列：也叫開放定址法，當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有
空位置，那么可以把key存放到沖突位置中的“下一個” 空位置中去。

1.2 開散列

開散列法又叫鏈地址法(開鏈法)，首先對關鍵碼集合用散列函數計算散列地址，具有相同地
址的關鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈
接起來，各鏈表的頭結點存儲在哈希表中。

下面則是即將學習的哈希桶的簡易圖：

類似于一個數組中存了若干個鏈表頭，每個頭所代表的鏈表成為一個桶。

1.3 string 與 非 string?

在上一篇博客的最后：哈希表HashTable-CSDN博客
探討過當 Key 為負數、浮點數、字符串...時，類函數邏輯中有關 Key 取模的問題，當 Key 為負數、浮點數、字符、字符串時，顯然這幾個內置類型無法完成取模的操作，這時就用到了仿函數，這里不再多說，直接來看仿函數的代碼，下面會直接使用仿函數來完成 HashBucket

template<class T>
class HashFunc<>
{size_t operator()(const T& Key){return (size_t)Key;}
}
template<>
class HashFunc<string>
{size_t operator()(const string& Key){size_t hash = 0;for (auto ch : Key){hash *= 131;hash += ch;}return hash;}
}

二、哈希桶的構成

2.1 哈希桶的節點

由上圖就可以看出來，每個結點必要存一個 pair 和一個指向下一個節點的指針 _next。

template<class K, class V>
struct HashNode
{pair<K, V> _kv;HashNode* _next;
}

2.2 哈希桶類

哈希桶類的構成和哈希表類似，都是一個由一個 vector 存放每個節點，但是這里與 HashTable 不同的是需要存放的是節點的指針。還有一個 _n 代表有效數據的個數：

template<class K, class V, class Hash = HashFunc<K>>
class HashBucket
{typedef HashNode Node;
private:vector<Node*> _bucket;size_t _n;
};

三、 Insert 函數

3.1 無需擴容時

下面要介紹的是不需要擴容時的插入邏輯：

此時只需要使用 Key 模數組的大小來計算出該節點需要連接在 vector 上的位置，然后使用 new 得到儲存 kv 的新節點，當 new 一個新節點時，節點的構造函數必不可少，下面先來看一下單個節點的構造函數以及類的構造函數：

template<class K, class V>
struct HashNode
{pair<K, V> _kv;HashNode* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashBucket
{    typedef HashNode<K, V> Node;HashBucket(){_bucket.resize(10, nullptr);_n = 0;}
private:vector<Node*> _bucket;size_t _n;
}

此時需要思考的是，既然 vector 每個節點都要存放一個鏈表，那么鏈表頭插還是尾插的效率更高呢？

顯然是頭插，所以這個新結點就需要以類似頭插的方式添加到 vector 的這個位置上，

bool Insert(const pair<K, V>& kv)
{Hash hs;size_t index = hs(kv.first) % _bucket.size(); Node* newnode = new Node(kv);newnode->_next = _bucket[index];_buckte[index] = newnode;++_n;return true;
}

3.2 擴容

這里的載荷因子可以直接設為1，至于載荷因子是什么，可以查看上一篇博客哈希表HashTable-CSDN博客，在擴容中的何時擴容標題下，介紹了載荷因子的概念。

在擴容中，既可以使用 HashTable 中類似的寫法直接復用 Insert ，也可以直接挨個讓節點插入，下面先介紹每種方式，再進行優缺點的處理：

復用 Insert：

bool Insert(const pair<K, V>& kv)
{Hash hs;if (_n == _bucket.size()){HashBucket newHB = new HashBucket;newHB._bucket.resize(_bucket.size() * 2, nullptr);for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while(cur){Node* next = cur->_next;  // 保存下一個節點指針newHB.Insert(cur->_kv);   // 插入當前節點的鍵值對到新哈希表cur = next;               // 移動到下一個節點}_bucket[i] = nullptr;}_bucket.swap(newHB);}
}

逐個插入：

bool Insert(const pair<K, V>& kv)
{Hash hs;if (_n == _bucket.size()){vector<Node*> newBucket(_bucket.size() * 2, nullptr);for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){Node* next = cur->_next;size_t index = hs(cur->_kv.first) % newBucket.size();cur->_next = newBucket[index];newBucket[index] = cur;cur = next;}_bucket[i] = nullptr;}_bucket.swap(newBucket);}
}

優缺點比對：

第一種寫法優點
  1. 代碼復用：通過調用 newHB.Insert(cur->_kv) 來重新插入節點，重用了 Insert 方法，減少了代碼重復。
  2. 邏輯清晰：將舊節點遷移到新桶中，然后交換桶，邏輯分離清晰。
第一種寫法缺點
  1. 性能：因為每次擴容時調用 Insert，可能會多次計算哈希值和處理沖突，性能可能稍差。
第二種寫法優點
  1. 性能：直接處理節點遷移，無需調用 Insert 方法，減少了函數調用和重復計算，提高了性能。
  2. 直接操作：直接操作指針，代碼簡潔，性能高效。
第二種寫法缺點
  1. 代碼重復：需要手動處理節點遷移邏輯，代碼重復。
  2. 復雜性：直接操作指針可能增加代碼的復雜性，增加錯誤的可能性。

3.3 完整代碼

    bool Insert(const pair<K, V>& kv){if (Find(kv.first)) return false;Hash hs;if (_n == _bucket.size()){HashBucket newHB;newHB._bucket.resize(_bucket.size() * 2, nullptr);for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){Node* next = cur->_next;  // 保存下一個節點指針newHB.Insert(cur->_kv);   // 插入當前節點的鍵值對到新哈希表cur = next;               // 移動到下一個節點}_bucket[i] = nullptr;}_bucket.swap(newHB._bucket);}size_t index = hs(kv.first) % _bucket.size();Node* newnode = new Node(kv);newnode->_next = _bucket[index];_bucket[index] = newnode;++_n;return true;}bool Insert(const pair<K, V>& kv){if (Find(kv.first)) return false;Hash hs;if (_n == _bucket.size()){vector<Node*> newBucket(_bucket.size() * 2, nullptr);for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){Node* next = cur->_next;size_t index = hs(cur->_kv.first) % newBucket.size();cur->_next = newBucket[index];newBucket[index] = cur;cur = next;}_bucket[i] = nullptr;}_bucket.swap(newBucket);}size_t index = hs(kv.first) % _bucket.size();Node* newnode = new Node(kv);newnode->_next = _bucket[index];_bucket[index] = newnode;++_n;return true;}

四、 Erase 函數

4.1 析構函數

根據 Insert 函數中，可以得知， HashBucket 的每個節點都是 new 出來的，那刪除的時候就要使用 delete ，又因為每個節點都是自定義類型，所以要為 HashBucket 寫一個析構函數。
對類的析構就是遍歷 vector 的每個節點，再從每個節點遍歷每個鏈表，以此遍歷全部節點。

    ~HashBucket(){for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_bucket[i] = nullptr;}}

4.2 Erase 函數

下面介紹一下Erase函數的步驟：

  1. 計算哈希值：使用哈希函數 hs 計算給定鍵 Key 的哈希值，并確定它在桶中的索引 index。

  2. 遍歷鏈表：從索引 index 開始，遍歷鏈表中的每個節點。

  3. 查找節點：檢查當前節點的鍵是否等于 Key。

    • 如果找到匹配節點：
      • 如果該節點是鏈表的第一個節點，將桶的頭指針 _bucket[index] 指向下一個節點。
      • 否則，將前一個節點的 _next 指針指向當前節點的下一個節點。
      • 刪除當前節點 cur，釋放內存。
      • 返回 true，表示刪除成功。
    • 如果沒有找到匹配節點，繼續遍歷鏈表，更新 prev 和 cur。

  4. 返回結果：如果遍歷完整個鏈表未找到匹配節點，返回 false，表示刪除失敗。

    bool Erase(const K& Key){Hash hs;size_t index = hs(Key) % _bucket.size();Node* cur = _bucket[index];Node* prev = nullptr;while (cur){if (cur->_kv.first == Key){//刪除的是第一個節點if (prev == nullptr){_bucket[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}

五、 Find 函數

這里的 Find 函數與 HashTable 中的 Find 函數邏輯略有不同，因為這里如果發送哈希沖突，那么存儲的位置還是 vector 中取模后的位置，不需要像 HashTable 那樣進行線性探測，只需要取一個指針挨個遍歷位于 _bucket[index] 鏈表上的節點即可。

    Node* Find(const K& Key){if (_bucket.empty()) return nullptr;Hash hs;size_t index = hs(Key) % _bucket.size();Node* cur = _bucket[index];while (cur){if (cur->_kv.first == Key)return cur;else cur = cur->_next;}return nullptr;}

寫完 Find 后，還可以進一步改進 Insert 函數，在插入時可以先進行查找，如果存在，那就插入失敗；如果不存在，再繼續插入。這樣避免了哈希桶中數據冗余的結果。

六、完整代碼?

#pragma once
#include <iostream>
#include <vector>
#include <string>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 (auto ch : Key){hash *= 131;hash += ch;}return hash;}
};template<class K, class V>
struct HashNode
{pair<K, V> _kv;HashNode* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}
};template<class K, class V, class Hash = HashFunc<K>>
class HashBucket
{typedef HashNode<K, V> Node;
public:HashBucket(){_bucket.resize(10, nullptr);_n = 0;}~HashBucket(){for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_bucket[i] = nullptr;}}bool Insert(const pair<K, V>& kv){if (Find(kv.first)) return false;Hash hs;if (_n == _bucket.size()){vector<Node*> newBucket(_bucket.size() * 2, nullptr);for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){Node* next = cur->_next;size_t index = hs(cur->_kv.first) % newBucket.size();cur->_next = newBucket[index];newBucket[index] = cur;cur = next;}_bucket[i] = nullptr;}_bucket.swap(newBucket);}size_t index = hs(kv.first) % _bucket.size();Node* newnode = new Node(kv);newnode->_next = _bucket[index];_bucket[index] = newnode;++_n;return true;}bool Insert(const pair<K, V>& kv){if (Find(kv.first)) return false;Hash hs;if (_n == _bucket.size()){HashBucket newHB;newHB._bucket.resize(_bucket.size() * 2, nullptr);for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){Node* next = cur->_next;  // 保存下一個節點指針newHB.Insert(cur->_kv);   // 插入當前節點的鍵值對到新哈希表cur = next;               // 移動到下一個節點}_bucket[i] = nullptr;}_bucket.swap(newHB._bucket);}size_t index = hs(kv.first) % _bucket.size();Node* newnode = new Node(kv);newnode->_next = _bucket[index];_bucket[index] = newnode;++_n;return true;}bool Erase(const K& Key){Hash hs;size_t index = hs(Key) % _bucket.size();Node* cur = _bucket[index];Node* prev = nullptr;while (cur){if (cur->_kv.first == Key){//刪除的是第一個節點if (prev == nullptr){_bucket[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}Node* Find(const K& Key){if (_bucket.empty()) return nullptr;Hash hs;size_t index = hs(Key) % _bucket.size();Node* cur = _bucket[index];while (cur){if (cur->_kv.first == Key)return cur;else cur = cur->_next;}return nullptr;}
private:vector<Node*> _bucket;size_t _n;
};
void TestHB1()
{int ret[] = {5, 15, 3, 12, 13, 31};HashBucket<int, int> hb;for (auto e : ret){hb.Insert(make_pair(e, e));}cout << hb.Erase(0) << endl;cout << hb.Erase(5) << endl;
}
void TestHB2()
{HashBucket<string, int> hb;hb.Insert(make_pair("sort", 1));hb.Insert(make_pair("left", 1));hb.Insert(make_pair("insert", 1));}

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

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

相關文章

gfast：基于全新Go Frame 2.3+Vue3+Element Plus構建的全棧前后端分離管理系統

gfast：基于全新Go Frame 2.3+Vue3+Element Plus構建的全棧前后端分離管理系統

gfast&#xff1a;基于全新Go Frame 2.3Vue3Element Plus構建的全棧前后端分離管理系統 隨著信息技術的飛速發展和數字化轉型的深入&#xff0c;后臺管理系統在企業信息化建設中扮演著越來越重要的角色。為了滿足市場對于高效、靈活、安全后臺管理系統的需求&#xff0c;gfast應…
閱讀更多...
OpenUI 可視化 AI：打造令人驚艷的前端設計！

OpenUI 可視化 AI：打造令人驚艷的前端設計！

https://openui.fly.dev/ai/new 可視化UI的新時代&#xff1a;通過人工智能生成前端代碼 許久未更新, 前端時間在逛github&#xff0c;發現一個挺有的意思項目&#xff0c;通過口語化方式生成前端UI頁面&#xff0c;能夠直觀的看到效果&#xff0c;下面來給大家演示下 在現代…
閱讀更多...
SAP FS00如何導出會計總賬科目表

SAP FS00如何導出會計總賬科目表

輸入T-code : S_ALR_87012333 根據‘FS00’中找到的總賬科目&#xff0c;進行篩選執行 點擊左上角的列表菜單&#xff0c;選擇‘電子表格’導出即可
閱讀更多...
echarts-地圖

echarts-地圖

使用地圖的三種的方式&#xff1a; 注冊地圖(用json或svg,注冊為地圖)&#xff0c;然后使用map地圖使用geo坐標系&#xff0c;地圖注冊后不是直接使用&#xff0c;而是注冊為坐標系。直接使用百度地圖、高德地圖&#xff0c;使用百度地圖或高德地圖作為坐標系。 用json或svg注…
閱讀更多...
C++中string類的初步介紹

C++中string類的初步介紹

C語言中的字符串 在C語言中&#xff0c;字符串是以\0結尾的一些字符的集合&#xff0c;C標準庫中提供了一系列str系列的庫函數&#xff0c;但這些庫函數與字符串是分離的&#xff0c;不符合面向對象的編程思想。 string類的大致介紹 1.string是表示字符串的字符串類 2.stri…
閱讀更多...
GpuMall智算云：meta-llama/llama3/Llama3-8B-Instruct-WebUI

GpuMall智算云：meta-llama/llama3/Llama3-8B-Instruct-WebUI

LLaMA 模型的第三代&#xff0c;是 LLaMA 2 的一個更大和更強的版本。LLaMA 3 擁有 35 億個參數&#xff0c;訓練在更大的文本數據集上GpuMall智算云 | 省錢、好用、彈性。租GPU就上GpuMall,面向AI開發者的GPU云平臺 Llama 3 的推出標志著 Meta 基于 Llama 2 架構推出了四個新…
閱讀更多...
pycharm畫圖貓和老鼠

pycharm畫圖貓和老鼠

在PyCharm中&#xff0c;你可以使用turtle模塊來畫圖。以下是一個簡單的例子&#xff0c;展示如何使用turtle模塊來繪制一個貓和一個老鼠。 import turtle # 設置窗口標題 turtle.title("畫圖貓和老鼠") # 創建兩個turtle對象&#xff0c;一個用于繪制貓&#xf…
閱讀更多...
AWS聯網和內容分發之API Gateway

AWS聯網和內容分發之API Gateway

Amazon API Gateway是一種完全托管的服務&#xff0c;可以幫助開發人員輕松創建、發布、維護、監控和保護任意規模的API。API充當應用程序的前門&#xff0c;可從您的后端服務訪問數據、業務邏輯或功能。使用API Gateway&#xff0c;您可以創建RESTful API和WebSocket API&…
閱讀更多...
lightGBM 集成學習模型 - 以銀行風控業務為例

lightGBM 集成學習模型 - 以銀行風控業務為例

LightGBM&#xff08;Light Gradient Boosting Machine&#xff09;是基于梯度提升決策樹&#xff08;GBDT&#xff09;的一種改進實現。其核心思想是通過加法模型&#xff08;additive model&#xff09;和前向分布算法&#xff08;forward distribution algorithm&#xff09…
閱讀更多...
Qt pro工程文件編寫匯總（區分debug和release、32位和64位的方法，編譯輸出目錄等）

Qt pro工程文件編寫匯總（區分debug和release、32位和64位的方法，編譯輸出目錄等）

前言&#xff1a; 從事qt開發已經好幾年了&#xff0c;但有關pro編寫的一些細節問題一直沒有一個很好的梳理匯總——因為實際工作開發中&#xff0c;往往只需要編譯特定版本的軟件&#xff08;例如32位release版本&#xff09;&#xff0c;項目創建好后并設置好編譯路徑&#x…
閱讀更多...
ML307R OpenCPU GPIO使用

ML307R OpenCPU GPIO使用

一、GPIO使用流程圖 二、函數介紹 三、GPIO 點亮LED 四、代碼下載地址 一、GPIO使用流程圖 這個圖是官網找到的&#xff0c;ML307R GPIO引腳電平默認為1.8V&#xff0c;需注意和外部電路的電平匹配&#xff0c;具體可參考《ML307R_硬件設計手冊_OpenCPU版本適用.pdf》中的描…
閱讀更多...
零基礎PHP入門（一）選擇IDE和配置環境

零基礎PHP入門（一）選擇IDE和配置環境

配置環境 官網下載安裝包&#xff0c;windows https://windows.php.net/download#php-8.3 我是下載的最新版&#xff0c;也可以切換其他版本 https://windows.php.net/downloads/releases/archives/ 下載好壓縮文件后&#xff0c;雙擊解壓到一個目錄 D:\soft\php 復制ph…
閱讀更多...
成都愛爾眼科醫院《中、歐國際近視手術大數據白皮書2.0》解讀會圓滿舉行

成都愛爾眼科醫院《中、歐國際近視手術大數據白皮書2.0》解讀會圓滿舉行

2024年5月12日&#xff0c;愛爾眼科聯合中國健康促進基金會健康傳播與促進專項基金、新華社新媒體中心與中南大學愛爾眼科研究院、愛爾數字眼科研究所重磅發布《中、歐國際近視手術大數據白皮書2.0》。這是繼2021、2022年在國內相繼發布《國人近視手術白皮書》、《2022中、歐近…
閱讀更多...
Ubuntu系統初始化相關配置

Ubuntu系統初始化相關配置

目錄 Ubuntu文件傳輸： ubuntu怎么打開word：安裝wps（應用中心搜索） Ubuntu安裝annoconda
閱讀更多...
模型蒸餾筆記

模型蒸餾筆記

文章目錄 一、什么是模型蒸餾二、如何蒸餾三、實踐四、參考文獻 一、什么是模型蒸餾 Hinton在NIPS2014提出了知識蒸餾&#xff08;Knowledge Distillation&#xff09;的概念&#xff0c;旨在把一個大模型或者多個模型ensemble學到的知識遷移到另一個輕量級單模型上&#xff0…
閱讀更多...
【SpringBoot】SpringBoot中防止接口重復提交（單機環境和分布式環境）

【SpringBoot】SpringBoot中防止接口重復提交（單機環境和分布式環境）

&#x1f4dd;個人主頁&#xff1a;哈__ 期待您的關注 目錄 &#x1f33c;前言 &#x1f512;單機環境下防止接口重復提交 &#x1f4d5;導入依賴 &#x1f4c2;項目結構 &#x1f680;創建自定義注解 ?創建AOP切面 &#x1f697;創建Conotroller &#x1f4bb;分布…
閱讀更多...
構建高效的在線培訓機構CRM應用架構實踐

構建高效的在線培訓機構CRM應用架構實踐

在當今數字化時代&#xff0c;在線培訓已成為教育行業的重要趨勢之一。為了提供更好的學習體驗和管理服務&#xff0c;在線培訓機構需要構建高效的CRM&#xff08;Customer Relationship Management&#xff09;應用架構。本文將探討在線培訓機構CRM應用架構的設計與實踐。 一、…
閱讀更多...
PTA 6-3 入侵者圍剿第二關3情報解密

PTA 6-3 入侵者圍剿第二關3情報解密

經過上一步已經將2個分隊得到的秘密情報合并到一起&#xff0c;并進行了信息去重。接下來&#xff0c;經過情報的分析&#xff0c;發現情報進行加密的方式&#xff0c;將鏈表從正中間斷開&#xff0c;然后后面的鏈表全部接到前面&#xff0c;輸出來的次序就是敵方的武器發射次序…
閱讀更多...
綠色智能：AI機器學習在環境保護中的深度應用與實踐案例

綠色智能：AI機器學習在環境保護中的深度應用與實踐案例

&#x1f9d1; 博主簡介&#xff1a;阿里巴巴嵌入式技術專家&#xff0c;深耕嵌入式人工智能領域&#xff0c;具備多年的嵌入式硬件產品研發管理經驗。 &#x1f4d2; 博客介紹&#xff1a;分享嵌入式開發領域的相關知識、經驗、思考和感悟&#xff0c;歡迎關注。提供嵌入式方向…
閱讀更多...
在vps的centos系統中用Python和青龍檢測網頁更新

在vps的centos系統中用Python和青龍檢測網頁更新

環境&#xff1a;vps&#xff0c;centos7&#xff0c;python3.8.10&#xff0c;青龍面板&#xff08;用寶塔安裝&#xff09; 任務&#xff1a;用python代碼&#xff0c;監控一個網站頁面是否有更新&#xff08;新帖子&#xff09;&#xff0c;若有&#xff0c;則提醒&#xf…
閱讀更多...
最新文章

Copyright @ 2022~2023