數據結構——哈希詳解

數據結構——哈希詳解

目錄

一、哈希的定義

二、六種哈希函數的構造方法

2.1 除留取余法

2.2 平方取中法

2.3 隨機數法

2.4 折疊法

2.5 數字分析法

2.6 直接定值法

三、四種解決哈希沖突的方法

3.1 開放地址法

3.1.1 線性探測法

3.1.2 二次探測法

3.2 鏈地址法

3.3 再散列函數法

3.4 公共區溢出法

四、用代碼解決鏈地址法

一、哈希的定義

順序表/鏈表有一個共同特征，數據值本身和其存儲位置之間是沒有關系的，所以我們要查找/搜索一個值，只能一個一個的去比較，時間復雜度是O(n),

我們想把時間復雜度降下來，提供一種技術讓我們數據值本身和存儲關系之前有映射關系，這時我們查找值是否存在則直接根據這種映射關系計算得出其存儲位置，這時只去要去計算得出的存儲位置查看即可——這種技術就是散列技術也就是哈希，映射關系就是哈希函數f???

f(關鍵字key)=存儲位置

哈希即是一種存儲方法也是一種查找方法

哈希沖突定義：倆個或多個關鍵碼Key1!=Key2但是通過哈希函數的計算得出的結果卻相等，這種現象就是發生了哈希沖突

二、六種哈希函數的構造方法

2.1 除留取余法

原理：

  • 哈希函數 h(k)=k mod m，其中 k 是鍵值，m 是哈希表的大小。

  • 通過取鍵值 k 除以 m 的余數來確定哈希值。

優點：

  • 實現簡單，計算速度快。

缺點：

  • 如果鍵值分布不均勻，容易導致沖突。例如，當鍵值都是偶數時，若 m 是偶數，那么所有哈希值也都是偶數，會浪費一半的哈希表空間。

  • 對 m 的選擇敏感，通常 m 選擇為質數可以減少沖突。

應用場景：

  • 適用于鍵值范圍較大且分布較為均勻的場景，如簡單的哈希表設計。

2.2 平方取中法

原理：

  • 將鍵值 k 平方，然后從平方后的結果中取出中間幾位數字作為哈希值。

  • 例如，鍵值 k=1234，平方后為 1522756，取中間幾位（如 2275）作為哈希值。

優點：

  • 能夠較好地打亂鍵值的分布，減少沖突。

缺點：

  • 如果鍵值較小，平方后的數字位數不夠，可能需要補零，導致哈希值不夠隨機。

  • 計算平方操作相對耗時。

應用場景：

  • 適用于對哈希值隨機性要求較高的場景，但計算資源允許的情況下。

2.3 隨機數法

原理：

  • 使用偽隨機數生成器（PRNG）根據鍵值生成隨機數作為哈希值。

  • 通常需要一個種子值，種子值可以根據鍵值計算得到。

優點：

  • 哈希值的隨機性高，沖突概率低。

缺點：

  • 隨機數生成器的實現復雜，且需要保證每次計算結果一致（即相同的鍵值產生相同的哈希值）。

  • 如果隨機數生成器質量不高，可能會導致哈希值分布不均勻。

應用場景：

  • 適用于對哈希值隨機性要求極高的場景，如密碼學中的哈希函數。

2.4 折疊法

原理：

  • 將鍵值分成若干部分，然后將這些部分進行折疊（相加、相減或按位運算）以生成哈希值。

  • 例如，鍵值 k=12345678，可以分成 1234 和 5678，然后相加得到 6912，再取模或者直接取后三位得到最終哈希值。

優點：

  • 簡單易實現，能夠較好地處理較長的鍵值。

缺點：

  • 如果鍵值的某些部分分布不均勻，可能會影響哈希值的分布。

  • 對折疊操作的選擇敏感，不同的折疊方式可能導致不同的效果。

應用場景：

  • 適用于鍵值較長且分布不均勻的場景，如字符串哈希。

2.5 數字分析法

原理：

  • 分析鍵值的每一位數字（或字符），根據某種規則選擇部分數字組合成哈希值。

  • 例如，鍵值 k=12345678，可以選擇第 2、4、6 位數字（2、4、6），然后組合成 246 作為哈希值。

優點：

  • 能夠根據鍵值的分布特點進行優化，減少沖突。

缺點：

  • 實現復雜，需要對鍵值的分布有先驗知識。

  • 如果鍵值的分布變化較大，可能需要重新調整規則。

應用場景：

  • 適用于對鍵值分布有明確了解的場景，如特定的數據庫索引設計。

2.6 直接定值法

原理：

  • 取關鍵字的線性函數值作為散列地址 f(key)=axkey+b?

  • 通常用于鍵值范圍較小且連續的情況。

優點：

  • 實現極其簡單，沒有沖突。

缺點：

  • 如果鍵值范圍較大，會浪費大量空間。

  • 不適用于鍵值范圍較大的場景。

應用場景：

  • 適用于鍵值范圍較小且連續的場景，如小型數據庫索引。

三、四種解決哈希沖突的方法

哈希沖突定義：倆個或多個關鍵碼Key1!=Key2但是通過哈希函數的計算得出的結果卻相等，這種現象就是發生了哈希沖突

3.1 開放地址法

3.1.1 線性探測法

原理：當發生哈希沖突時，從沖突位置開始，按照線性順序依次探測下一個位置，向右探測，直到找到空閑位置為止。即若哈希地址為?h(key)?的位置已被占用，則依次探測?h(key)+1、h(key)+2、h(key)+3…… 直到找到空閑位置。

優點：實現簡單，容易理解和編程實現。

缺點：容易出現 “聚集” 現象，即連續的多個空閑位置被占用，形成一個聚集區，導致后續元素查找和插入時需要探測更多的位置，效率降低。

公式：f(key)=(f(key)+d)mod m????? d=1，2，3，4，5…

3.1.2 二次探測法

使用線性探測法會發生堆積，我們想要探測的時候即向左也向右探測并且每次探測幅度盡可能變化，呈指數變化 eg：1，-1，4，-4，9，-9

增加平方運算是為了不讓關鍵字都聚集在某一個區域

優點：能有效減少聚集現象，提高哈希表的性能。

缺點：不能探測到哈希表中的所有位置，可能會出現無法找到空閑位置的情況，特別是當哈希表大小不是合適的數值時。

3.2 鏈地址法

其核心思想是將所有哈希地址相同的元素都鏈接到同一個鏈表中。在哈希表中，每個位置對應一個鏈表，當發生哈希沖突（即不同的關鍵字通過哈希函數計算得到相同的哈希地址）時，將這些沖突的元素依次插入到對應的鏈表中

優點：

  • 處理沖突簡單，不需要探測。

  • 刪除元素容易，只需從鏈表中移除即可。

缺點：

  • 需要額外的空間來存儲鏈表。

  • 當一個槽位的鏈表很長時，搜索效率會降低。

3.3 再散列函數法

再散列函數法使用兩個不同的哈希函數。第一個哈希函數?h1(key)?用于計算元素的初始哈希地址。當該地址發生沖突時，使用第二個哈希函數?h2(key)?來確定下一個探測位置的步長，從而在哈希表中尋找下一個可用的位置。

通過這種方式，不斷嘗試新的位置，直到找到一個空槽來插入元素，或者確定該元素不存在于哈希表中。

3.4 公共區溢出法

不沖突放到基本表中，沖突就放到溢出表中，基本表中都沒有數據為空說明溢出表中肯定沒有，基本表由哈希函數構成，溢出表由順序存儲構成先來先到，

適用于哈希沖突相對較少的場景

四、用代碼解決鏈地址法

.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "hash_List_address.h"
#include <stdlib.h>//0.哈希函數
int Hash(ELEM_TYPE val)
{return val % INITSIZE;
}//1.初始化
void Init_List_Address(List_address* pla)
{for (int i = 0; i < INITSIZE; i++){Init_List(&pla->arr[i]);}
}//2.插入值(頭插)
bool Insert(List_address* pla, ELEM_TYPE val)
{//assertint index = Hash(val);struct Node* pnewnode = (Node*)malloc(sizeof(Node));if (pnewnode == NULL){return false;}pnewnode->data = val;pnewnode->next = pla->arr[index].next;pla->arr[index].next = pnewnode;return true;
}//3.刪除值
bool Del(List_address* pla, ELEM_TYPE val)
{struct Node* q = Search(pla, val);if (q == NULL)return false;//此時，代碼執行到這里，證明val值節點存在在index下標里面的單鏈表上int index = Hash(val);struct Node* p = &pla->arr[index];for (; p->next != q; p = p->next);//此時，代碼執行到這里，證明p和q都就位p->next = q->next;free(q);q = NULL;return true;
}//4.查找值
struct Node* Search(List_address* pla, ELEM_TYPE val)
{//assertint index = Hash(val);struct Node* q = pla->arr[index].next;for (; q != NULL; q = q->next){if (q->data == val){break;}}return q;}//5.打印
void Show(List_address* pla)
{for (int i = 0; i < INITSIZE; i++){printf("第%d行：", i);struct Node* p = pla->arr[i].next;for (; p != NULL; p=p->next){printf("%d->", p->data);}printf("\n");}
}int main()
{List_address head;Init_List_Address(&head);Insert(&head, 12);Insert(&head, 67);Insert(&head, 56);Insert(&head, 16);Insert(&head, 25);Insert(&head, 37);Insert(&head, 22);Insert(&head, 29);Insert(&head, 15);Insert(&head, 47);Insert(&head, 48);Insert(&head, 34);Show(&head);Del(&head, 25);Del(&head, 12345);Show(&head);return 0;
}

.h?

#pragma oncetypedef int ELEM_TYPE;
//鏈地址法有效節點結構體設計：
typedef struct List_Node
{ELEM_TYPE data;struct List_Node* next;
}List_Node;#include "list.h"//鏈地址法整個的輔助節點結構體設計：
#define INITSIZE 12
typedef struct List_address
{struct Node arr[INITSIZE];
}List_address;//0.哈希函數
int Hash(ELEM_TYPE val);//1.初始化
void Init_List_Address(List_address* pla);//2.插入值
bool Insert(List_address* pla, ELEM_TYPE val);//3.刪除值
bool Del(List_address* pla, ELEM_TYPE val);//4.查找值
struct Node* Search(List_address* pla, ELEM_TYPE val);//5.打印
void Show(List_address* pla);

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

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

相關文章

使用U盤安裝 ubuntu 系統

使用U盤安裝 ubuntu 系統

1. 準備U 盤制作鏡像 1.1 下載 ubuntu iso https://ubuntu.com/download/ 這里有多個版本以供下載&#xff0c;本文選擇桌面版。 1.2 下載rufus https://rufus.ie/downloads/ 1.3 以管理員身份運行 rufus 設備選擇你用來制作啟動項的U盤&#xff0c;不能選錯了&#xff1b;點…
閱讀更多...
RadioMaster POCKET遙控器進入ExpressLRS界面一直顯示Loading的問題解決方法

RadioMaster POCKET遙控器進入ExpressLRS界面一直顯示Loading的問題解決方法

RadioMaster POCKET遙控器進入ExpressLRS界面一直顯示Loading的問題解決方法 問題描述解決方法 問題描述 有一天我發現我的 RadioMaster POCKET 遙控器進入 ExpressLRS 設置界面時&#xff0c;界面卻一直停留在 “Loading” 狀態&#xff0c;完全無法進入設置界面。 我并沒有…
閱讀更多...
計算機網絡 - 三次握手相關問題

計算機網絡 - 三次握手相關問題

通過一些問題來討論 TCP 協議中的三次握手機制 說一下三次握手的大致過程&#xff1f;為什么需要三次握手&#xff1f;2 次不可以嗎&#xff1f;第三次握手&#xff0c;可以攜帶數據嗎&#xff1f;第二次呢&#xff1f;三次握手連接階段&#xff0c;最后一次ACK包丟失&#xf…
閱讀更多...
【RabbitMQ】核心概念和工作流程

【RabbitMQ】核心概念和工作流程

文章目錄 RabbitMQ 工作流程流程圖 Producer 和 ConsumerConnecting 和 ChannelVirtual hostQueueExchangeRabbitMQ 工作流程 RabbitMQ 工作流程 流程圖 RabbitMQ 就是一個生產者/消費者模型 Producer 就是生產者、Consumer 就是消費者Broker 是 RabbitMQ 服務器生產者和消費…
閱讀更多...
龍虎榜——20250414

龍虎榜——20250414

今天縮量上漲有些乏力&#xff0c;壓力位還在~ 2025年4月14日龍虎榜行業方向分析 一、核心主線方向 黃金與貴金屬&#xff08;避險邏輯強化&#xff09; ? 驅動邏輯&#xff1a;國際地緣沖突持續升溫&#xff08;如中東局勢、臺海動態&#xff09;&#xff0c;疊加美國特朗普…
閱讀更多...
蔚來汽車智能座艙接入通義大模型，并使用通義靈碼全面提效

蔚來汽車智能座艙接入通義大模型，并使用通義靈碼全面提效

為加速AI應用在企業市場落地&#xff0c;4月9日&#xff0c;阿里云在北京召開AI勢能大會。阿里云智能集團資深副總裁、公共云事業部總裁劉偉光發表主題演講&#xff0c;大模型的社會價值正在企業市場釋放&#xff0c;阿里云將堅定投入&#xff0c;打造全棧領先的技術&#xff0…
閱讀更多...
探索 Go 與 Python：性能、適用場景與開發效率對比

探索 Go 與 Python：性能、適用場景與開發效率對比

1 性能對比&#xff1a;執行速度與資源占用 1.1 Go 的性能優勢 Go 語言被設計為具有高效的執行速度和低資源占用。它編譯后生成的是機器碼&#xff0c;能夠直接在硬件上運行&#xff0c;避免了 Python 解釋執行的開銷。 以下是一個用 Go 實現的簡單循環計算代碼&#xff1a; …
閱讀更多...
虛幻引擎 Anim To Tex| RVT | RT

虛幻引擎 Anim To Tex| RVT | RT

本文上篇分為4個部分&#xff1a;動畫驅動材質&#xff0c;虛擬紋理&#xff0c;Rendertarget&#xff0c;以及其他雜項的地編ta干貨整理。&#xff08;其中RT部分基本為UOD重要截圖摘錄&#xff09; 本文下篇為&#xff1a;skylight和directional light的區別&#xff0c;未完…
閱讀更多...
kingbase權限管理

kingbase權限管理

1. kingbase模式權限管理 1.1授予用戶對模式的權限 以具有足夠權限的用戶登錄后&#xff0c;執行以下 SQL 語句來授予用戶對模式的相應權限。假設你要授予用戶 your_user 對模式 your_schema 的使用權限&#xff1a; sql -- 授予用戶使用模式的權限 GRANT USAGE ON SCHEMA …
閱讀更多...
9.thinkphp的請求

9.thinkphp的請求

請求對象 當前的請求對象由think\Request類負責&#xff0c;該類不需要單獨實例化調用&#xff0c;通常使用依賴注入即可。在其它場合則可以使用think\facade\Request靜態類操作。 項目里面應該使用app\Request對象&#xff0c;該對象繼承了系統的think\Request對象&#xff…
閱讀更多...
Java從入門到“放棄”（精通）之旅——方法的使用⑤

Java從入門到“放棄”（精通）之旅——方法的使用⑤

Java從入門到“放棄”&#xff08;精通&#xff09;之旅&#x1f680;——方法的使用⑤ &#x1f4d6;引言&#xff1a; 在編程領域&#xff0c;代碼如同精密的齒輪相互咬合驅動程序運轉。隨著項目規模漸長&#xff0c;重復的代碼片段如同冗余的齒輪&#xff0c;不僅增加負重…
閱讀更多...
鴻蒙NEXT開發格式化工具類（ArkTs）

鴻蒙NEXT開發格式化工具類（ArkTs）

import { i18n } from kit.LocalizationKit;/*** 格式化工具類* 提供電話號碼格式化、歸屬地查詢、字符轉換等功能。* author: 鴻蒙布道師* since: 2025/04/14*/ export class FormatUtil {/*** 判斷傳入的電話號碼格式是否正確。* param phone - 待驗證的電話號碼* param coun…
閱讀更多...
[Python基礎速成]2-模塊與包與OOP

[Python基礎速成]2-模塊與包與OOP

上篇??[Python基礎速成]1-Python規范與核心語法 目錄 Python模塊創建模塊與導入屬性__name__dir()函數標準模塊 Python包類類的專有方法 對象繼承多態 Python模塊 Python 中的模塊&#xff08;Module&#xff09;是一個包含 Python 定義和語句的文件&#xff0c;文件名就是模…
閱讀更多...
OSI參考模型和TCP/IP模型

OSI參考模型和TCP/IP模型

1.OSI參考模型 OSI模型&#xff1a; OSI參考模型有7層&#xff0c;自下而上依次為物理層&#xff0c;數據鏈路層&#xff0c;網絡層&#xff0c;傳輸層&#xff0c;會話層&#xff0c;表示層&#xff0c;應用層。&#xff08;記憶口訣&#xff1a;物聯網叔會用&#xff09;。低…
閱讀更多...
linux Shell編程之循環語句（三）

linux Shell編程之循環語句（三）

目錄 一. for 循環語句 1. for語句的結構 2. for 語句應用示例 (1) 根據姓名列表批量添加用戶 (2) 根據 IP 地址列表檢查主機狀態 二. 使用 while 循環語句 1. while 語句的結構 2. while 語句應用示例 (1) 批量添加規律編號的用戶 (2) 猜價格游戲 三. until 循環語…
閱讀更多...
最新扣子實戰教程，利用扣子平臺通過在線表格記錄，批量生圖，再也不要一條條的粘貼提示詞了

最新扣子實戰教程，利用扣子平臺通過在線表格記錄，批量生圖，再也不要一條條的粘貼提示詞了

1、功能描述 大家好&#xff0c;我是濤濤。今天我要給大家講解如何在扣子平臺上對接飛書電子表格。由于多維表格相對復雜&#xff0c;而很多業務場景其實只需要電子表格就能滿足&#xff0c;因此今天我們將演示如何在扣子平臺上讀取飛書電子表格并批量生成圖片。 先看效果&am…
閱讀更多...
java -jar指定類加載

java -jar指定類加載

在 Java 中&#xff0c;使用 java -jar 命令運行 JAR 文件時&#xff0c;默認會加載 JAR 文件的 MANIFEST.MF 文件中指定的 Main-Class。如果你想在運行時指定一個類來加載&#xff0c;可以通過以下方式實現&#xff1a; 方法 1&#xff1a;直接指定類路徑和類名 如果你不想使用…
閱讀更多...
多模態思維鏈（Multimodal Chain of Thought, MCoT）六大技術支柱在醫療領域的應用

多模態思維鏈（Multimodal Chain of Thought, MCoT）六大技術支柱在醫療領域的應用

多模態思維鏈（Multimodal Chain of Thought, MCoT）通過整合文本、圖像、視頻等多模態數據，結合邏輯推理與深度學習技術，在醫療領域展現出強大的應用潛力。其六大技術支柱在醫療場景中的具體應用如下： 一、推理構建視角：醫學診斷的流程優化 MCoT通過多模態推理鏈生成技術…
閱讀更多...
從文本到視頻：基于擴散模型的AI生成系統全解析（附PyTorch實現）

從文本到視頻：基于擴散模型的AI生成系統全解析（附PyTorch實現）

當語言遇見動態視覺 "用文字生成電影場景"曾是科幻作品中的幻想&#xff0c;如今借助擴散模型&#xff08;Diffusion Models&#xff09;正逐步成為現實。本文將手把手帶你實現一個創新的文本到視頻生成系統&#xff0c;通過深度解析擴散模型原理&#xff0c;結合獨…
閱讀更多...
科普：如何通過ROC曲線，確定二分類的“理論閾值”

科普：如何通過ROC曲線，確定二分類的“理論閾值”

在二分類問題中&#xff0c;已知預測概率&#xff08;如邏輯回歸、神經網絡輸出的概率值&#xff09;時&#xff0c;閾值的選擇直接影響分類結果&#xff08;正/負樣本判定&#xff09;。 一、實踐中的閾值選擇方法 1. 基于業務目標的調整 最大化準確率&#xff1a;適用于樣…
閱讀更多...
最新文章

Copyright @ 2022~2023