模擬實現unordered_map

1.定義

unordered_map?是 C++ 標準庫中的哈希表容器，特點是無序存儲、平均 O (1) 時間復雜度的插入 / 查找 / 刪除操作。其核心原理是通過哈希函數將關鍵字映射到哈希桶（bucket），再通過鏈表或紅黑樹處理哈希沖突。

2.實現原理

1. 哈希表（Hash Table）
  • 作用：存儲鍵值對的底層數據結構，由哈希桶數組組成。
  • 結構：vector<Node*>?或?vector<list<Node>>，每個元素（桶）對應一個鏈表（處理哈希沖突）。
2. 哈希函數（Hash Function）
  • 作用：將關鍵字（Key）映射為哈希桶的索引（整數）。
  • 要求：
    • 輸出范圍需在哈希桶數組大小范圍內（通過取模?% bucket_count?實現）。
    • 盡可能減少哈希沖突（不同 Key 映射到同一索引）。

?例子：

template <typename Key>
size_t HashFunc(const Key& key) {// 對整數直接取哈希return static_cast<size_t>(key);
}// 對字符串的哈希
template <>
size_t HashFunc(const std::string& key) {size_t hash = 0;for (char c : key) {hash = hash * 31 + c; // 31 是質數，減少沖突}return hash;
}

3. 哈希沖突（Hash Collision）
  • 問題：不同的 Key 通過哈希函數得到相同的桶索引。
  • 解決方式：
    • 鏈地址法（最常用）：每個桶對應一個鏈表，沖突的鍵值對依次插入鏈表。
    • 開放定址法：沖突時尋找下一個空桶（較少用于?unordered_map）。
4. 負載因子（Load Factor）
  • 定義：負載因子 = 元素個數 / 桶數量。
  • 作用：衡量哈希表的擁擠程度，超過閾值（通常為 1.0）時需要擴容。
  • 擴容機制：
    • 創建新的、更大的桶數組（通常為原大小的 2 倍，且為質數）。
    • 將所有元素重新哈希（rehash）到新桶中，避免哈希沖突加劇。
5. 鍵值對（Key-Value Pair）
  • 結構：存儲關鍵字（Key）和值（Value）的節點，例如：
template <typename Key, typename Value>
struct Node {Key key;Value value;Node* next; // 指向鏈表中下一個節點（處理沖突）Node(const Key& k, const Value& v) : key(k), value(v), next(nullptr) {}
};

3.主要實現

1. 構造函數與析構函數

template <typename Key, typename Value>
class my_UnorderedMap {
private:std::vector<Node<Key, Value>*> buckets; // 哈希桶數組size_t size; // 當前元素個數size_t bucket_count; // 桶數量const float load_factor_threshold = 1.0f; // 負載因子閾值public:// 構造函數：初始化桶數量（默認 10 個桶）my_UnorderedMap(size_t init_buckets = 10) : bucket_count(init_buckets), size(0) {buckets.resize(bucket_count, nullptr);}// 析構函數：釋放所有節點和桶~my_UnorderedMap() {for (auto bucket : buckets) {Node<Key, Value>* cur = bucket;while (cur) {Node<Key, Value>* next = cur->next;delete cur;cur = next;}}}
};

2.插入操作

bool my_insert(const Key& key, const Value& value) {// 檢查是否需要擴容if (size * 1.0 / bucket_count >= load_factor_threshold) {rehash(bucket_count * 2); // 擴容為原大小的 2 倍}// 計算哈希索引size_t index = HashFunc(key) % bucket_count;// 檢查 Key 是否已存在（不允許重復 Key）Node<Key, Value>* cur = buckets[index];while (cur) {if (cur->key == key) {return false; // Key 已存在，插入失敗}cur = cur->next;}// 插入新節點（頭插法）Node<Key, Value>* new_node = new Node<Key, Value>(key, value);new_node->next = buckets[index]; // 新節點指向原鏈表頭buckets[index] = new_node; // 桶頭指向新節點size++;return true;
}

?3.查找

Value* my_find(const Key& key) {size_t index = HashFunc(key) % bucket_count;Node<Key, Value>* cur = buckets[index];while (cur) {if (cur->key == key) {return &(cur->value); // 找到 Key，返回值的指針}cur = cur->next;}return nullptr; // 未找到
}

?4.刪除

bool my_erase(const Key& key) {size_t index = HashFunc(key) % bucket_count;Node<Key, Value>* cur = buckets[index];Node<Key, Value>* prev = nullptr;while (cur) {if (cur->key == key) {// 移除節點if (prev == nullptr) {// 頭節點刪除buckets[index] = cur->next;} else {prev->next = cur->next;}delete cur;size--;return true;}prev = cur;cur = cur->next;}return false; // 未找到 Key
}

?5.擴容

void my_rehash(size_t new_bucket_count) {if (new_bucket_count <= bucket_count) return; // 新桶數量必須更大// 創建新桶數組std::vector<Node<Key, Value>*> new_buckets(new_bucket_count, nullptr);// 將舊桶中的元素重新哈希到新桶for (size_t i = 0; i < bucket_count; i++) {Node<Key, Value>* cur = buckets[i];while (cur) {Node<Key, Value>* next = cur->next; // 保存下一個節點// 計算新索引size_t new_index = HashFunc(cur->key) % new_bucket_count;// 插入新桶（頭插法）cur->next = new_buckets[new_index];new_buckets[new_index] = cur;cur = next;}}// 替換舊桶數組buckets.swap(new_buckets);bucket_count = new_bucket_count;
}

6.移動復制和拷貝賦值

// 拷貝賦值運算符my_UnorderedMap& operator=(const UnorderedMap& other) {if (this != &other) {clear();bucket_count = other.bucket_count;load_factor_threshold = other.load_factor_threshold;hash_fn = other.hash_fn;equal_fn = other.equal_fn;buckets.resize(bucket_count, nullptr);for (size_t i = 0; i < other.bucket_count; ++i) {Node* current = other.buckets[i];while (current != nullptr) {insert(current->key, current->value);current = current->next;}}}return *this;}// 移動賦值運算符my_UnorderedMap& operator=(UnorderedMap&& other) noexcept {if (this != &other) {clear();buckets = std::move(other.buckets);element_count = other.element_count;bucket_count = other.bucket_count;load_factor_threshold = other.load_factor_threshold;hash_fn = std::move(other.hash_fn);equal_fn = std::move(other.equal_fn);other.element_count = 0;other.bucket_count = 0;}return *this;}

---完整代碼；

#include <vector>
#include <cstddef>
#include <functional>
#include <stdexcept>template <typename Key, typename Value, typename Hash = std::hash<Key>, typename Equal = std::equal_to<Key>>
class my_UnorderedMap {
private:// 鍵值對節點結構struct Node {Key key;Value value;Node* next;Node(const Key& k, const Value& v) : key(k), value(v), next(nullptr) {}};std::vector<Node*> buckets;  // 哈希桶數組size_t element_count;        // 當前元素數量size_t bucket_count;         // 桶的數量float load_factor_threshold; // 負載因子閾值// 哈希函數包裝器Hash hash_fn;// 相等比較器Equal equal_fn;// 檢查是否為質數bool is_prime(size_t num) const {if (num <= 1) return false;if (num == 2) return true;if (num % 2 == 0) return false;for (size_t i = 3; i * i <= num; i += 2) {if (num % i == 0) return false;}return true;}// 獲取下一個質數size_t next_prime(size_t num) const {if (num <= 2) return 2;size_t candidate = num;if (candidate % 2 == 0) ++candidate;while (!is_prime(candidate)) {candidate += 2;}return candidate;}// 重新哈希所有元素到新的桶數組void my_rehash(size_t new_bucket_count) {if (new_bucket_count <= bucket_count) return;std::vector<Node*> new_buckets(new_bucket_count, nullptr);// 將舊桶中的所有節點遷移到新桶for (size_t i = 0; i < bucket_count; ++i) {Node* current = buckets[i];while (current != nullptr) {Node* next = current->next;size_t new_index = hash_fn(current->key) % new_bucket_count;current->next = new_buckets[new_index];new_buckets[new_index] = current;current = next;}}// 交換新舊桶數組buckets.swap(new_buckets);bucket_count = new_bucket_count;}public:// 構造函數explicit my_UnorderedMap(size_t initial_buckets = 10, const Hash& hash = Hash(), const Equal& equal = Equal()): element_count(0), bucket_count(next_prime(initial_buckets)),load_factor_threshold(1.0f),hash_fn(hash),equal_fn(equal) {buckets.resize(bucket_count, nullptr);}// 析構函數~my_UnorderedMap() {clear();}// 拷貝構造函數my_UnorderedMap(const UnorderedMap& other): element_count(0), bucket_count(other.bucket_count),load_factor_threshold(other.load_factor_threshold),hash_fn(other.hash_fn),equal_fn(other.equal_fn) {buckets.resize(bucket_count, nullptr);for (size_t i = 0; i < other.bucket_count; ++i) {Node* current = other.buckets[i];while (current != nullptr) {insert(current->key, current->value);current = current->next;}}}// 移動構造函數my_UnorderedMap(UnorderedMap&& other) noexcept: buckets(std::move(other.buckets)),element_count(other.element_count),bucket_count(other.bucket_count),load_factor_threshold(other.load_factor_threshold),hash_fn(std::move(other.hash_fn)),equal_fn(std::move(other.equal_fn)) {other.element_count = 0;other.bucket_count = 0;}// 拷貝賦值運算符my_UnorderedMap& operator=(const UnorderedMap& other) {if (this != &other) {clear();bucket_count = other.bucket_count;load_factor_threshold = other.load_factor_threshold;hash_fn = other.hash_fn;equal_fn = other.equal_fn;buckets.resize(bucket_count, nullptr);for (size_t i = 0; i < other.bucket_count; ++i) {Node* current = other.buckets[i];while (current != nullptr) {insert(current->key, current->value);current = current->next;}}}return *this;}// 移動賦值運算符my_UnorderedMap& operator=(UnorderedMap&& other) noexcept {if (this != &other) {clear();buckets = std::move(other.buckets);element_count = other.element_count;bucket_count = other.bucket_count;load_factor_threshold = other.load_factor_threshold;hash_fn = std::move(other.hash_fn);equal_fn = std::move(other.equal_fn);other.element_count = 0;other.bucket_count = 0;}return *this;}// 插入元素bool my_insert(const Key& key, const Value& value) {// 檢查負載因子，必要時擴容if (static_cast<float>(element_count) / bucket_count >= load_factor_threshold) {rehash(next_prime(bucket_count * 2));}size_t index = hash_fn(key) % bucket_count;Node* current = buckets[index];// 檢查鍵是否已存在while (current != nullptr) {if (equal_fn(current->key, key)) {return false; // 鍵已存在，插入失敗}current = current->next;}// 創建新節點并插入鏈表頭部Node* new_node = new Node(key, value);new_node->next = buckets[index];buckets[index] = new_node;++element_count;return true;}// 查找元素Value* my_find(const Key& key) {size_t index = hash_fn(key) % bucket_count;Node* current = buckets[index];while (current != nullptr) {if (equal_fn(current->key, key)) {return &(current->value);}current = current->next;}return nullptr; // 未找到}// 查找元素（const 版本）const Value* my_find(const Key& key) const {size_t index = hash_fn(key) % bucket_count;Node* current = buckets[index];while (current != nullptr) {if (equal_fn(current->key, key)) {return &(current->value);}current = current->next;}return nullptr; // 未找到}// 重載[]運算符Value& operator[](const Key& key) {Value* value_ptr = find(key);if (value_ptr == nullptr) {// 鍵不存在，插入默認值insert(key, Value());value_ptr = find(key);}return *value_ptr;}// 刪除元素bool my_erase(const Key& key) {size_t index = hash_fn(key) % bucket_count;Node* current = buckets[index];Node* previous = nullptr;while (current != nullptr) {if (equal_fn(current->key, key)) {if (previous == nullptr) {// 刪除頭節點buckets[index] = current->next;} else {previous->next = current->next;}delete current;--element_count;return true;}previous = current;current = current->next;}return false; // 未找到鍵}// 獲取元素數量size_t size() const {return element_count;}// 檢查是否為空bool my_empty() const {return element_count == 0;}// 清空容器void clear() {for (size_t i = 0; i < bucket_count; ++i) {Node* current = buckets[i];while (current != nullptr) {Node* next = current->next;delete current;current = next;}buckets[i] = nullptr;}element_count = 0;}// 獲取負載因子float load_factor() const {return static_cast<float>(element_count) / bucket_count;}// 獲取負載因子閾值float max_load_factor() const {return load_factor_threshold;}// 設置負載因子閾值void max_load_factor(float new_threshold) {if (new_threshold > 0) {load_factor_threshold = new_threshold;}}// 調整桶的數量void reserve(size_t count) {size_t new_bucket_count = next_prime(count);if (new_bucket_count > bucket_count) {rehash(new_bucket_count);}}// 迭代器類class Iterator {private:Node* current;const std::vector<Node*>* buckets;size_t bucket_index;size_t bucket_count;// 移動到下一個非空桶void move_to_next_bucket() {while (current == nullptr && bucket_index < bucket_count) {++bucket_index;if (bucket_index < bucket_count) {current = (*buckets)[bucket_index];}}}public:Iterator(Node* node, const std::vector<Node*>* b, size_t index, size_t count): current(node), buckets(b), bucket_index(index), bucket_count(count) {if (current == nullptr) {move_to_next_bucket();}}Iterator& operator++() {if (current != nullptr) {current = current->next;if (current == nullptr) {++bucket_index;move_to_next_bucket();}}return *this;}bool operator==(const Iterator& other) const {return current == other.current;}bool operator!=(const Iterator& other) const {return !(*this == other);}std::pair<const Key&, Value&> operator*() const {return {current->key, current->value};}std::pair<const Key&, Value&>* operator->() const {// 這里簡化實現，實際需要返回一個代理對象throw std::runtime_error("Arrow operator not fully implemented");}};// 迭代器接口Iterator begin() const {if (empty()) {return end();}return Iterator(buckets[0], &buckets, 0, bucket_count);}Iterator end() const {return Iterator(nullptr, &buckets, bucket_count, bucket_count);}
};

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

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

相關文章

史上最詳細Java并發多線程（面試必備，一篇足矣）

史上最詳細Java并發多線程（面試必備，一篇足矣）

第一章&#xff1a;線程基礎 1.1 線程與進程 進程&#xff1a;系統資源分配的基本單位&#xff0c;擁有獨立的內存空間 線程&#xff1a;CPU調度的基本單位&#xff0c;共享進程內存空間 關系&#xff1a;一個進程可包含多個線程&#xff0c;線程切換成本遠低于進程 1.2 線程的…
閱讀更多...
【DataFlow】數據合成流水線工具

【DataFlow】數據合成流水線工具

1.整體解讀 核心思想&#xff1a;以數據為中心的AI&#xff08;Data-Centric AI&#xff09; DataFlow 的核心目標是通過一系列自動化“流水線”&#xff08;Pipelines&#xff09;來處理和生成高質量的數據&#xff0c;從而提升大語言模型&#xff08;LLM&#xff09;在特定領…
閱讀更多...
Hangfire 調用報錯解決方案總結

Hangfire 調用報錯解決方案總結

System.ArgumentNullException: 值不能為 null 錯誤在使用 Hangfire 時確實是一個常見問題&#xff0c;特別是在配置 Hangfire 服務器時。問題分析這個錯誤通常發生在以下情況&#xff1a;沒有正確配置 Hangfire 服務器隊列配置缺失或不正確連接字符串配置問題解決方案要點正確…
閱讀更多...
MySQL的使用

MySQL的使用

MySQL的使用一、mysql中的周邊命令1. 檢查版本2. 查看字符集3. 查看客戶端連接4. 查看最后一條警告消息二、數據庫、數據表的管理1. 語法規則2. 數據庫2.1 查看數據庫2.2 創建數據庫2.3 選擇數據庫2.4 查看創建數據庫命令2.5 創建庫時添加字符集2.6 修改數據庫字符集2.7 刪除數…
閱讀更多...
2025Nginx最新版講解/面試

2025Nginx最新版講解/面試

維護系統多服務器部署&#xff0c;將我們請求代理到各個服務器。代理正向代理&#xff0c;代理對象是我們的客戶端&#xff0c;目標對象不知道我們用戶。VPN就是典型的正向代理。反向代理&#xff0c;代理對象是服務端&#xff0c;用戶不知道服務端具體信息。而這正是Nginx所做…
閱讀更多...
JAVASCRIPT 前端數據庫-V8--仙盟數據庫架構-—-—仙盟創夢IDE

JAVASCRIPT 前端數據庫-V8--仙盟數據庫架構-—-—仙盟創夢IDE

老版本 在v1 版本中我們講述了 基礎版的應用 JAVASCRIPT 前端數據庫-V1--仙盟數據庫架構-—-—仙盟創夢IDE-CSDN博客 接下載我們做一個更復雜的的其他場景 由于&#xff0c;V1查詢字段必須 id 接下來我們修改了了代碼 JAVASCRIPT 前端數據庫-V2--仙盟數據庫架構-—-—仙盟創…
閱讀更多...
UNIX 域套接字實現本地進程間通信

UNIX 域套接字實現本地進程間通信

&#x1f680; 使用 UNIX 域套接字 (AF_UNIX) 實現高效進程通信 在 Linux 和其他類 UNIX 系統中&#xff0c;進程間通信 (IPC) 的方法有很多種&#xff0c;例如管道、消息隊列、共享內存等。然而&#xff0c;當你的應用程序需要在 同一臺機器上的不同進程間進行高效、低延遲的數…
閱讀更多...
【Axure教程】中繼器間圖片的傳遞

【Axure教程】中繼器間圖片的傳遞

中繼器在Axure中可以作為圖片保存的數據庫&#xff0c;在實際系統中&#xff0c;我們經常需要將選擇數據庫的圖片添加到其他圖片列表中&#xff0c;所以今天就教大家&#xff0c;怎么在Axure中實現中繼器之間的圖片傳遞&#xff0c;包含將一個中繼器中的圖片列表傳遞到另一個中…
閱讀更多...
專題：2025云計算與AI技術研究趨勢報告|附200+份報告PDF、原數據表匯總下載

專題：2025云計算與AI技術研究趨勢報告|附200+份報告PDF、原數據表匯總下載

原文鏈接&#xff1a;https://tecdat.cn/?p42935 關鍵詞&#xff1a;2025, 云計算&#xff0c;AI 技術&#xff0c;市場趨勢&#xff0c;深度學習&#xff0c;公有云&#xff0c;研究報告 云計算和 AI 技術正以肉眼可見的速度重塑商業世界。過去十年&#xff0c;全球云服務收…
閱讀更多...
從代碼學習深度強化學習 - PPO PyTorch版

從代碼學習深度強化學習 - PPO PyTorch版

文章目錄 前言PPO 算法簡介從 TRPO 到 PPOPPO 的兩種形式：懲罰與截斷代碼實踐：PPO 解決離散動作空間問題 (CartPole)環境與工具函數定義策略與價值網絡PPO 智能體核心實現訓練與結果代碼實踐：PPO 解決連續動作空間問題 (Pendulum)環境準備適用于連續動作的網絡PPO 智能體 (連…
閱讀更多...
PortsWiggerLab: Blind OS command injection with output redirection

PortsWiggerLab: Blind OS command injection with output redirection

實驗目的This lab contains a blind OS command injection vulnerability in the feedback function.The application executes a shell command containing the user-supplied details. The output from the command is not returned in the response. However, you can use o…
閱讀更多...
星云穿越與超光速飛行特效的前端實現原理與實踐

星云穿越與超光速飛行特效的前端實現原理與實踐

文章目錄 1，引言2，特效設計思路3，技術原理解析1. 星點的三維分布2. 視角推進與星點運動3. 三維到二維的投影4. 星點的視覺表現5. 色彩與模糊處理4，關鍵實現流程圖5，應用場景與優化建議6，總結1，引言 在現代網頁開發中，炫酷的視覺特效不僅能提升用戶體驗，還能為產品增添…
閱讀更多...
【Linux】C++項目分層架構：核心三層與關鍵輔助

【Linux】C++項目分層架構：核心三層與關鍵輔助

C 項目分層架構全指南&#xff1a;核心三層 關鍵輔助一、核心三層架構 傳統的三層架構&#xff08;或三層體系結構&#xff09;是構建健壯系統的基石&#xff0c;包括以下三層&#xff1a; 1. 表現層&#xff08;Presentation Layer&#xff09; 負責展示和輸入處理&#xff0…
閱讀更多...
【機器學習】保序回歸平滑校準算法

【機器學習】保序回歸平滑校準算法

保序回歸平滑校準算法&#xff08;SIR&#xff09;通過分桶合并線性插值解決廣告預估偏差問題&#xff0c;核心是保持原始排序下糾偏。具體步驟&#xff1a;1&#xff09;按預估分升序分桶&#xff0c;統計每個分桶的后驗CTR&#xff1b;2&#xff09;合并逆序桶重新計算均值&a…
閱讀更多...
項目開發日記

項目開發日記

框架整理學習UIMgr&#xff1a;一、數據結構與算法 1.1 關鍵數據結構成員變量類型說明m_CtrlsList<PageInfo>當前正在顯示的所有 UI 頁面m_CachesList<PageInfo>已打開過、但現在不顯示的頁面&#xff08;緩存池&#xff09; 1.2 算法邏輯查找緩存頁面&#xff1a;…
閱讀更多...
60 美元玩轉 Li-Fi —— 開源 OpenVLC 平臺入門（附 BeagleBone Black 驅動簡單解析）

60 美元玩轉 Li-Fi —— 開源 OpenVLC 平臺入門（附 BeagleBone Black 驅動簡單解析）

60 美元玩轉 Li-Fi —— 開源 OpenVLC 平臺入門&#xff08;附 BeagleBone Black 及驅動解析&#xff09;一、什么是 OpenVLC&#xff1f; OpenVLC 是由西班牙 IMDEA Networks 研究所推出的開源可見光通信&#xff08;VLC / Li-Fi&#xff09;研究平臺。它把硬件、驅動、協議棧…
閱讀更多...
Python性能優化

Python性能優化

Python 以其簡潔和易用性著稱，但在某些計算密集型或大數據處理場景下，性能可能成為瓶頸。幸運的是，通過一些巧妙的編程技巧，我們可以顯著提升Python代碼的執行效率。本文將介紹8個實用的性能優化技巧，幫助你編寫更快、更高效的Python代碼。 　　一、優化前的黃金法則：先測…
閱讀更多...
easyui碰到想要去除頂部欄按鈕邊框

easyui碰到想要去除頂部欄按鈕邊框

只需要加上 plain"true"<a href"javascript:void(0)" class"easyui-linkbutton" iconCls"icon-add" plain"true"onclick"newCheck()">新增</a>
閱讀更多...
C++字符串詳解：原理、操作及力扣算法實戰

C++字符串詳解：原理、操作及力扣算法實戰

一、C字符串簡介在C中&#xff0c;字符串的處理方式主要有兩種&#xff1a;字符數組&#xff08;C風格字符串&#xff09;和std::string類。雖然字符數組是C語言遺留的底層實現方式&#xff0c;但現代C更推薦使用std::string類&#xff0c;其封裝了復雜的操作邏輯&#xff0c;提…
閱讀更多...
CMU15445-2024fall-project1踩坑經歷

CMU15445-2024fall-project1踩坑經歷

p1目錄&#xff1a;lRU\_K替換策略LRULRU\_K大體思路SetEvictableRecordAccessSizeEvictRemoveDisk SchedulerBufferPoolNewPageDeletePageFlashPage/FlashAllPageCheckReadPage/CheckWritePagePageGuard并發設計主邏輯感謝CMU的教授們給我們分享了如此精彩的一門課程&#xff…
閱讀更多...
最新文章

Copyright @ 2022~2023