欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++數(shù)據(jù)結(jié)構(gòu)哈希表詳解

 更新時間:2022年07月19日 15:00:34   作者:一起摸摸魚  
C++標(biāo)準(zhǔn)庫中使用的unordered_map底層實現(xiàn)是哈希表,下面這篇文章主要給大家介紹了關(guān)于C++中使用哈希表(unordered_map)的一些常用操作方法,需要的朋友可以參考下

實現(xiàn)

哈希表,即散列表,可以快速地存儲和查詢記錄。理想哈希表的存儲和查詢時間都是 O(1)。

本《資料》中哈希表分以下幾部分:散列函數(shù)、存儲和查找時的元素定位、存儲、查找。刪除操作因為不常用,所以只給出思想,不給出代碼。

根據(jù)實際情況,可選擇不同的散列方法。

以下代碼假設(shè)哈希表不會溢出。

// N表示哈希表長度,是一個素數(shù),M表示額外空間的大小,empty代表“沒有元素”。
const int N=9997, M=10000, empty=-1;
int a[N];
void init() // 初始化哈希表
{
memset(a,empty,sizeof(a)); // 注意,只有empty等于0或-1時才可以這樣做!
memset(bucket,empty,sizeof(bucket));
memset(first,0,sizeof(first));
}
inline int h(int); // 散列函數(shù)
int *locate(int, bool); // 用于存儲和查找的定位函數(shù),并返回對應(yīng)位置。
// 如果用于存儲,則第二個參數(shù)為true,否則為false①。
void save(int x) // 存儲數(shù)據(jù)
{
int *p = locate(x, true);
if (p!=NULL) *p=x;
}
bool isexist(int x) // 查找數(shù)據(jù)
{
int *p = locate(x,false);
return (p!=NULL && *p==x);
}

散列函數(shù)

為了達到快速存儲和查找的目的,就必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系 h。

這個關(guān)系 h 叫做哈希函數(shù)。

哈希表存取方便但存儲時容易沖突:即不同的關(guān)鍵字可以對應(yīng)同一哈希地址。如何確定哈希函數(shù)和解決沖突是關(guān)鍵。以下是幾種常見的哈希函數(shù)的構(gòu)造方法:

1. 取余數(shù)法:h(x) = x%p(p≤N,且最好是素數(shù))

2. 直接定址法:h(x)=x 或 h(x)=a*x+b

3. 數(shù)字分析法:取關(guān)鍵字的若干數(shù)位(如中間兩位數(shù))組成哈希地址。

4. 平方取中法:關(guān)鍵字平方后取中間幾位數(shù)組成哈希地址。

5. 折疊法:將關(guān)鍵數(shù)字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)然后取幾部分的疊加和(舍去進位)作為哈希地址。

6. 偽隨機數(shù)法:事先產(chǎn)生一個隨機數(shù)序列 r[],然后令 h(x)=r[x]。

設(shè)計哈希函數(shù)時,要注意

對關(guān)鍵碼值的分布并不了解——希望選擇的散列函數(shù)在關(guān)鍵碼范圍內(nèi)能夠產(chǎn)生一個大致平均的關(guān)鍵碼值隨機分布,同時避免明顯的聚集可能性,如對關(guān)鍵碼值的高位或低位敏感的散列函數(shù)。

對關(guān)鍵碼值的分布有所了解——應(yīng)該使用一個依賴于分布的散列函數(shù),避免把一組相關(guān)的關(guān)鍵碼值映射到散列表的同一個槽中。

開散列方法

哈希表中難免會發(fā)生沖突。使用開散列方法可以解決這個問題。常用操作方法是“拉鏈法”,即相同的地址的關(guān)鍵字值均鏈入對應(yīng)的鏈表中。

如果散列函數(shù)很差,就容易形成長長的鏈表,從而影響查找的效率。

下面是用“拉鏈法”處理沖突時的定位函數(shù):

int size=-1;
struct node {int v; node * next;} *first[N], mem[M];
#define NEW(p) p=&mem[++size]; p->next=NULL
int * locate(int x, bool ins=false)
{
int p=h(x);
if (a[p]==x && !ins) return &a[p];
// 處理沖突
node *q = first[p];
if (ins)
if (q==NULL)
{
NEW(q);
first[p]=q;
return &q->v;
}
else
{
while (q->next!=NULL) q=q->next;
node *r; NEW(r);
q->next=r;
return &r->v;
}
else
while (q!=NULL)
{
if (q->v == x) return &q->v;
q=q->next;
}
return NULL;
}

閉散列方法(開地址方法)

處理沖突的另一種方法是為該關(guān)鍵字的記錄找到另一個“空”的哈希地址。在處理中可能得到一個地址序列 g(i)(i=1,2,…,k;0≤g(i)≤n-1),即在處理沖突時若得到的另一個哈希地址 g(1)仍發(fā)生沖突,再

求下一地址 g(2),若仍沖突,再求 g(3)……怎樣得到 g(i)呢?

溢出桶法:設(shè)一個溢出桶,不管得到的哈希地址如何,一旦發(fā)生沖突,都填入溢出桶。

再哈希法:使用另外一種哈希函數(shù)來定位。

線性探查:g(i)=(h(x)+di) % N,其中 h(x)為哈希函數(shù),N 為哈希表長,di 為增量序列。

1. 線性探測再散列:di=1,2,3,…,m-1

2. 二次探測再散列:

3. 偽隨機探測序列:事先產(chǎn)生一個隨機數(shù)序列 random[],令 di=random[i]。

下面是用溢出桶處理沖突時的定位函數(shù):

int bucket[M], top=-1; // 用于閉散列方法(溢出桶)
int * locate(int x, bool ins=false)
{
int p=h(x);
if (a[p]==x && !ins) // 在查找模式下碰到了所需的元素
return &a[p];
else if (ins)
{
if (a[p]==empty) // 可以插入
return &a[p];
else // 處理沖突
return &bucket[++top];
}
else // 到溢出桶中尋找元素
for (int i=0; i<=top; i++)
if (bucket[i]==x) return &bucket[i];
return NULL;
}

下面是用線性探查處理沖突的定位函數(shù),當(dāng)然,它也可以用于再哈希法處理沖突

inline int g(int p, int i) {return (p+i)%N;} // 根據(jù)需要來設(shè)計
int * locate(int x, bool ins=false)
{
int p=h(x);
int p2, c=0;
if (a[p]==x && !ins)
return &a[p];
else if (ins)
{
do
{
p2 = g(p, c++);
} while (a[p2]!=empty);
return &a[p2];
} else {
do
{
p2 = g(p, c++);
} while (a[p2]!=x && a[p2]!=empty);
if (a[p2]==x) return &a[p2];
}
return NULL;
}

閉散列方法的優(yōu)點是節(jié)省空間。不過,無論是溢出桶,還是線性探查,都會在尋址過程中浪費時間。線性

探查的探查序列如果太長,就會使一些其他元素被迫散列在其他位置,從而影響了其他元素的查找效率。

刪除*

如果使用開散列方法,那么可以直接刪除元素。然而,使用閉散列方法,是不可以直接刪除元素的。假如

直接刪除,很有可能會影響其他元素的查找。

在這種情況下,有兩種刪除方法:一種是交換法,另一種是標(biāo)記法。

交換法:在刪除某元素時,不要立刻把它清除。按照線性探查函數(shù)繼續(xù)尋找,直到?jīng)]有數(shù)值為止。將遇到

的最后一個數(shù)值與它交換。當(dāng)然,交換之前還要進行類似的操作,可謂“牽一發(fā)而動全身”。

標(biāo)記法:開一個標(biāo)記數(shù)組 flag[]。如果第 i 個元素被刪除了,就將 flag[i]設(shè)為 true。

1. 插入元素時,如果所在位置有標(biāo)記,就把元素放到這里,并把標(biāo)記清除。

2. 查找元素時,如果經(jīng)過標(biāo)記,就跳過去繼續(xù)查找。

3. 為了哈希表的效率,應(yīng)該定期清理表中的標(biāo)記(或重新散列所有元素)。

到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)哈希表詳解的文章就介紹到這了,更多相關(guān)C++哈希表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語言字符串函數(shù)模擬實現(xiàn)流程介紹

    C語言字符串函數(shù)模擬實現(xiàn)流程介紹

    字符串函數(shù)(String processing function)也叫字符串處理函數(shù),指的是編程語言中用來進行字符串處理的函數(shù),如C,pascal,Visual以及LotusScript中進行字符串拷貝,計算長度,字符查找等的函數(shù)
    2022-09-09
  • 非常漂亮的新年祝福!C語言實現(xiàn)漂亮的煙花效果

    非常漂亮的新年祝福!C語言實現(xiàn)漂亮的煙花效果

    非常漂亮的新年祝福!這篇文章主要介紹了C語言實現(xiàn)漂亮的煙花效果,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-02-02
  • C語言實現(xiàn)圖片放大縮小

    C語言實現(xiàn)圖片放大縮小

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)圖片放大縮小,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-05-05
  • C++實現(xiàn)LeetCode(63.不同的路徑之二)

    C++實現(xiàn)LeetCode(63.不同的路徑之二)

    這篇文章主要介紹了C++實現(xiàn)LeetCode(63.不同的路徑之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C語言之單向鏈表詳解及實例代碼

    C語言之單向鏈表詳解及實例代碼

    這篇文章主要介紹了C語言之單向鏈表的相關(guān)資料,及實例代碼,幫助大家學(xué)習(xí)參考,,需要的朋友可以參考下
    2016-09-09
  • C++使用VLD檢測內(nèi)存泄漏

    C++使用VLD檢測內(nèi)存泄漏

    本文主要介紹了C++使用VLD檢測內(nèi)存泄漏,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • C語言標(biāo)準(zhǔn)時間與秒單位相互轉(zhuǎn)換

    C語言標(biāo)準(zhǔn)時間與秒單位相互轉(zhuǎn)換

    這篇文章主要介紹了C語言標(biāo)準(zhǔn)時間與秒單位相互轉(zhuǎn)換,秒單位與標(biāo)準(zhǔn)時間的轉(zhuǎn)換方式,這份代碼一般用在嵌入式單片機里比較多,比如:設(shè)置RTC時鐘的時間,從RTC里讀取秒單位時間后,需要轉(zhuǎn)換成標(biāo)準(zhǔn)時間顯示。下文分享需要的小伙伴可以參考一下
    2022-05-05
  • opencv3/C++ 直方圖反向投影實例

    opencv3/C++ 直方圖反向投影實例

    今天小編就為大家分享一篇opencv3/C++ 直方圖反向投影實例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-12-12
  • 詳解c++中的異常

    詳解c++中的異常

    程序在運行過程中,有對也就有錯,正確那么就不用說了,但是如果錯誤,那么我們?nèi)绾慰焖俚亩ㄎ坏藉e誤的位置,以及知道發(fā)生了什么錯誤。當(dāng)一個函數(shù)發(fā)現(xiàn)自己無法處理的異常,就會拋出一個異常,讓函數(shù)調(diào)用者直接或者間接的處理這個錯誤。本文將詳解介紹c++中的異常
    2021-06-06
  • C/C++使用Zlib實現(xiàn)文件的壓縮與解壓

    C/C++使用Zlib實現(xiàn)文件的壓縮與解壓

    zlib 是一個開源的數(shù)據(jù)壓縮庫,旨在提供高效、輕量級的壓縮和解壓縮算法,本文將介紹如何使用 zlib 庫進行數(shù)據(jù)的壓縮和解壓縮,以及如何保存和讀取壓縮后的文件,感興趣的可以了解下
    2023-11-11

最新評論