哈希沖突的常見解決方法【附C++代碼】

????????在C++中,哈希表是一種常用的數據結構,用于實現快速的插入、刪除和查找操作。

哈希表的核心在于哈希函數,它將輸入的關鍵字轉換為一個數組索引。然而,不同的關鍵字可能映射到相同的索引,這種情況稱為哈希沖突。

有效地解決哈希沖突是確保哈希表性能的關鍵。

1. 開放地址法

概念:開放地址法是指當一個關鍵字映射的位置已經被占用時,會尋找下一個空閑的位置進行存放。查找時,若原位置沒有找到,則按照同樣的規則繼續查找下一個可能的位置。

優點:實現簡單,無需額外的數據結構。

缺點:可能會導致某些區域過于密集,影響性能;刪除操作復雜

代碼示例

#include <iostream>
#include <vector>class OpenAddressingHashTable {
public:explicit OpenAddressingHashTable(size_t size) : table(size, -1), used(size, false) {}void insert(int key) {size_t index = key % table.size();while (used[index]) {index = (index + 1) % table.size(); // 線性探測法}table[index] = key;used[index] = true;}bool search(int key) {size_t index = key % table.size();while (used[index]) {if (table[index] == key) return true;index = (index + 1) % table.size();}return false;}private:std::vector<int> table;std::vector<bool> used;
};

2. 鏈地址法(哈希桶)

概念:鏈地址法是在每個數組位置上掛接一個鏈表,所有映射到該位置的元素都存儲在這個鏈表中。

優點:沖突少時效率高,支持動態擴容,刪除操作簡單。

缺點:鏈表過長時,查找效率降低。

代碼示例(基于之前提供的哈希桶示例):

#include <iostream>
#include <list>
#include <vector>class HashBucket {
public:explicit HashBucket(size_t size = 10) : buckets(size) {}void insert(int key, std::string value) {size_t index = hashFunction(key);buckets[index].push_back({key, value});}std::string search(int key) {size_t index = hashFunction(key);for (const auto& pair : buckets[index]) {if (pair.first == key) {return pair.second;}}return "Not Found";}void remove(int key) {size_t index = hashFunction(key);auto& bucket = buckets[index];bucket.erase(std::remove_if(bucket.begin(), bucket.end(),[key](const auto& p){ return p.first == key; }),bucket.end());}private:std::size_t hashFunction(int key) const {return key % buckets.size(); // 簡單的取模哈希函數}std::vector<std::list<std::pair<int, std::string>>> buckets;
};int main() {HashBucket hashTable;hashTable.insert(10, "Apple");hashTable.insert(25, "Banana");hashTable.insert(20, "Cherry");std::cout << "Search 10: " << hashTable.search(10) << std::endl; // 應輸出 Applestd::cout << "Search 30: " << hashTable.search(30) << std::endl; // 應輸出 Not FoundhashTable.remove(20);std::cout << "Search 20 after removal: " << hashTable.search(20) << std::endl; // 應輸出 Not Foundreturn 0;
}

3. 再哈希法

概念:當發生沖突時,使用第二個哈希函數計算另一個位置,如果仍沖突,則繼續使用第三個或更多哈希函數,直到找到空位。

優點:可以減少聚集現象。

缺點:需要設計多個哈希函數,增加了實現復雜度。

代碼示例(簡略示例):

class RehashHashTable {
public:void insert(int key) {size_t index = primaryHash(key);if (isOccupied(index)) {index = secondaryHash(key); // 假設這是第二個哈希函數// 可能需要更多的檢查和重哈希直到找到空位}// 實際插入邏輯省略}private:size_t primaryHash(int key) { /* 主哈希函數實現 */ }size_t secondaryHash(int key) { /* 輔助哈希函數實現 */ }bool isOccupied(size_t index) { /* 檢查位置是否已被占用 */ }
};

4. 建立公共溢出區(使用率低)

概念:當主表滿時,額外分配一塊區域作為溢出區,所有沖突的元素都放入這個區域,并以某種順序(如鏈表)鏈接起來。

優點:實現簡單。

缺點:查找效率較低,因為可能需要遍歷整個溢出區。

????????解決哈希沖突的策略各有優劣,選擇哪種方法取決于具體的應用場景和性能要求。開放地址法適合內存有限且數據量不大的情況;鏈地址法則更適合數據量大且需要頻繁插入刪除的場景;再哈希法和建立公共溢出區則是針對特定需求的解決方案,可能在某些特殊場景下更為合適。

????????在實際應用中,還需要考慮哈希函數的設計、哈希表的動態擴容機制等因素,以進一步優化性能。C++標準庫中的std::unordered_mapstd::unordered_set就是使用了類似鏈地址法的實現,結合了動態擴容機制,提供了高效的哈希表操作接口。

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

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

相關文章

走進全球LED顯示龍頭艾比森,深挖逆勢增長43%的數智化邏輯

在大環境不景氣的情況下&#xff0c;有一家智能制造企業在2023年營收40億&#xff0c;同比增長高達43%&#xff0c;海外營收增長約 46%&#xff0c;并且連續12年單品牌出口額第一。 這就是全球LED顯示龍頭艾比森。 5月9日&#xff0c;紛享銷客帶領近70位企業高管走進紛享銷客…

使用Nginx將服務器目錄、文件共享出來

1.配置映射路徑&#xff0c;加入映射目錄 location /abc/ { autoindex on; autoindex_localtime on; charset utf-8; alias /usr/mydir/; } 2.重載Nginx配置 nginx -s reload 3.訪問 http://XXX.XXX.XXX.XXX/abc/ 即可 注&#xff1a; 如果…

短視頻再度重逢:四川京之華錦信息技術公司

短視頻再度重逢 在數字化時代的浪潮中&#xff0c;短視頻以其獨特的魅力迅速崛起&#xff0c;成為現代人生活中不可或缺的一部分。而當我們談論起短視頻&#xff0c;我們不僅僅是在談論一種娛樂方式&#xff0c;更是在談論一種情感的載體&#xff0c;一種回憶的媒介。今天&…

PHP8.0 match函數

match 表達式是 PHP 8.0 引入的一個新的控制結構&#xff0c;它提供了一種簡潔且更強大的方式來進行條件匹配。與 switch 語句相比&#xff0c;match 表達式具有以下優勢&#xff1a; 返回值&#xff1a;match 是一個表達式&#xff0c;它會返回一個值。嚴格比較&#xff1a;m…

MyBatis系統學習篇 - MyBatis逆向工程

MyBatis的逆向工程是指根據數據庫表結構自動生成對應的Java實體類、Mapper接口和XML映射文件的過程。逆向工程可以幫助開發人員快速生成與數據庫表對應的代碼&#xff0c;減少手動編寫重復代碼的工作量。 我們在MyBatis中通過逆向工具來幫我簡化繁瑣的搭建框架&#xff0c;減少…

iOS推送證書過期處理

蘋果推送證書的有效期都是一年&#xff0c;將要過期的時候&#xff0c;蘋果官方會發郵件提醒。 一、過期 在電腦上找到并打開其它->鑰匙串訪問&#xff1b; 我的證書可以看到各個App的推送證書&#xff0c;如果過期了&#xff0c;顯示紅色X 二、重新創建 1、登陸apple開…

如何解決三層單點故障

我給他整成下面這樣行不行呀 一個pc的默認網關只有一個&#xff0c;pc1配置的是1.1&#xff0c;那么路由壞了&#xff0c;他還是給1.1發送數據&#xff0c;冗余的那個也沒用上呀 用VRRP&#xff08;虛擬路由冗余協議&#xff09;解決以上問題 那光把這個R1和R2虛擬成一個R3&…

android usb轉串口

Android USB通信&#xff08;host轉串口&#xff09;_android usb 實現串口通信-CSDN博客

Windows內核函數 - 文件的讀操作

DDK提供了文件讀操作的內核函數&#xff0c;其函數聲明如下&#xff1a; NTSTATUS ZwWriteFile(IN HANDLE FileHandle,IN HANDLE Event,IN PIO_APC_ROUTINE ApcRoutine,IN PVOID ApcContext,out PIO_STATUS_BLOCK IoStatusBlock,IN PVOID Buffer,IN ULONG Length,IN PLARGE_IN…

windows 執行node報錯 800A1391

在項目下執行node -v的時候&#xff0c;拋了這個錯誤&#xff0c;一開始沒發現有啥問題 現在一看&#xff0c;這個報錯里的node怎么是個文件... 出現這個問題&#xff0c;是因為項目下&#xff0c;有個同名的文件叫node.js&#xff0c;搞得windows一時不知道是想打開node.js文…

代碼隨想錄算法訓練營Day51 | 300.最長遞增子序列 674. 最長連續遞增序列 718. 最長重復子數組

代碼隨想錄算法訓練營Day51 | 300.最長遞增子序列 674. 最長連續遞增序列 718. 最長重復子數組 LeetCode 300.最長遞增子序列 題目鏈接&#xff1a;LeetCode 300.最長遞增子序列 思路&#xff1a; 選取最長子序列&#xff0c;并收集 class Solution { public:int lengthOfL…

通過提示工程將化學知識整合到大型語言模型中

在當今快速發展的人工智能領域&#xff0c;大型語言模型&#xff08;LLMs&#xff09;正成為科學研究的新興工具。這些模型以其卓越的語言處理能力和零樣本推理而聞名&#xff0c;為解決傳統科學問題提供了全新的途徑。然而&#xff0c;LLMs在特定科學領域的應用面臨挑戰&#…

第四十六天 | 279.完全平方數 139.單詞拆分

題目&#xff1a;279.完全平方數 本題比較簡單&#xff0c;幾天沒做背包但是這道題很快ac了 嘗試解答&#xff1a; 題目類型&#xff1a;給定一個背包容量&#xff0c;求裝滿背包的最少物品數&#xff0c;且每個物品可以放多次&#xff0c;完全背包 1.dp[j]數組含義&#xff…

如何選擇適合自己需求的揚州獨立服務器方案?

在互聯網時代&#xff0c;獨立服務器是網絡建設的重要組成部分。選擇適合自己需求的揚州獨立服務器方案至關重要。下面&#xff0c;我們將介紹如何選擇合適的揚州獨立服務器&#xff0c;并推薦萊卡云&#xff08;Lcayun&#xff09;服務器商。 明確需求 要明確自己的需求是什…

大型央企國企信創化與數字化轉型規劃實施方案(71頁PPT)

方案介紹&#xff1a; 隨著全球信息技術的迅猛發展&#xff0c;數字化轉型已成為企業提升競爭力、實現可持續發展的必經之路。作為國家經濟的重要支柱&#xff0c;大型央企國企在信創化與數字化轉型方面承載著重要的責任和使命。本方案旨在通過系統性的規劃和實施&#xff0c;…

rpc理解

rpc 遠程過程調用 rpc與http的區別 1.性能高 2.使用復雜 3.可擴展性高 4 跨語言支持 5.可以使用服務發現&#xff0c;負載均衡&#xff0c;熔斷降級 rpc遠程調用&#xff0c;必須傳輸數據&#xff0c;需要序列化。 序列化有多種方式&#xff1a; jdk原生序列化&#xff0c…

Discourse 使用 DiscourseConnect 來進行用戶數據同步

我們都知道 Discourse 的用戶管理和設置都高度依賴電子郵件。 如果 Discourse 沒有設置電子郵件 SMTP 的話&#xff0c;作為管理員是沒有辦法對用戶郵箱進行修改并且通過驗證的。 可以采取的辦法是通過 Discourse 的 DiscourseConnect 來進行用戶同步。 根據官方的說法&…

C++語法|虛函數與多態詳細講解(四)|哪些函數不能實現成虛函數和虛析構函數的理解

系列匯總講解&#xff0c;請移步&#xff1a; C語法&#xff5c;虛函數與多態詳細講解系列&#xff08;包含多重繼承內容&#xff09; 文章目錄 哪些函數不能成為虛函數虛析構函數什么時候把基類的析構函數必須是線程虛函數 哪些函數不能成為虛函數 要回答這個問題&#xff0c…

如何取消公眾號的在線客服綁定授權

1&#xff0c;功能設置 2&#xff0c;公眾號設置 3&#xff0c;查看詳情&#xff0c;取消

開發遠程遙控情趣玩具軟件,提供現成程序源碼應具備哪些基礎功能

以“東莞夢情智能”為參考&#xff0c;其提供的現成情趣玩具遙控軟件程序源碼&#xff0c;所具備哪些基礎功能&#xff0c;看看它們如何讓情趣玩具變得更加豐富多彩。 一、設備連接 設備連接是情趣玩具遙控軟件的基礎功能之一。“東莞夢情智能”的現成源碼支持多種連接方式&am…