C++哈希表之線性探測(cè)法實(shí)現(xiàn)詳解
更新時(shí)間：2022年05月04日 10:50:24 作者：liufeng2023
線性探測(cè)法的優(yōu)點(diǎn)：只要散列表未滿，總能找到一個(gè)不沖突的散列地址；缺點(diǎn)：每個(gè)產(chǎn)生沖突的記錄被散列到離沖突最近的空地址上，從而又增加了更多的沖突機(jī)會(huì)
1、哈希表-線性探測(cè)法理論
線性探測(cè)法的理論我們?cè)谏弦黄┛鸵呀?jīng)闡述了。
現(xiàn)在我們來(lái)看看線性探測(cè)法的增刪查的代碼思想：
1.1、哈希表的增加元素
注意：
往后遍歷尋找空閑位置的時(shí)候，要注意是環(huán)形遍歷哦！不然訪問(wèn)數(shù)組就越界了。
在添加元素，發(fā)生位置被占用，即發(fā)生哈希沖突后，在向后遍歷尋找空閑位置的時(shí)候，我們要知道，這個(gè)空閑的位置是有兩種情況的：
1、這個(gè)位置一直是空的，沒(méi)放過(guò)元素。
2、這個(gè)位置是空的，以前放過(guò)元素，后來(lái)被刪除了。
1.2、哈希表的查詢操作
- 當(dāng)用哈希函數(shù)計(jì)算得出的下標(biāo)值是3，然后去訪問(wèn)數(shù)組，查詢時(shí)，發(fā)現(xiàn)該值不等于要查詢的元素的值val，說(shuō)明當(dāng)時(shí)放val的時(shí)候發(fā)生了哈希沖突，這時(shí)候就要向后遍歷了；
- 訪問(wèn)4下標(biāo)的時(shí)候發(fā)現(xiàn)這個(gè)位置是空的（空的有兩種情況），如果這個(gè)位置一直是空的，則就不用繼續(xù)向后找了，val不存在！因?yàn)槭蔷€性探測(cè)法，所以當(dāng)時(shí)val如果要放的時(shí)候肯定是要放在這里的。
- 但是如果這個(gè)位置是空的，但是之前放過(guò)元素，后來(lái)被刪除了，這個(gè)位置之前存放了元素，然后val插入的時(shí)候，就插到后面的空閑的位置了，所以此時(shí)我們還要繼續(xù)往后遍歷尋找val值。
所以我們需要定義一個(gè)Bucket節(jié)點(diǎn)來(lái)表示每一個(gè)元素的所有的內(nèi)容。
//桶的狀態(tài)
enum State
{
STATE_UNUSE, //從未使用過(guò)的桶
STATE_USING, //正在使用的桶 放著是一個(gè)有效的元素，沒(méi)有被刪過(guò)
STATE_DEL, //元素被刪除了的桶，認(rèn)為桶里的元素?zé)o效了
};
//我們刪除桶里的元素，并不是真正把值刪除掉，而是把桶的狀態(tài)置為STATE_DEL就認(rèn)為桶里的元素?zé)o效了
//桶的類型
struct Bucket
{
Bucket(int key = 0, State state = STATE_UNUSE)
: key_(key)
, state_(state)
{}
int key_; //存儲(chǔ)的數(shù)據(jù)
State state_; //桶的當(dāng)前狀態(tài)
};
1.3、哈希表的刪除操作
2、哈希表-線性探測(cè)法代碼實(shí)現(xiàn)
2.1、素?cái)?shù)表中的素?cái)?shù)
求素?cái)?shù)的代碼：（用于素?cái)?shù)表中的素?cái)?shù)取值）
int main()
{
int data = 3;
for (int i = data; i < 10000; i++)
{
int j = 2;
for (; j < i; j++)
{
if (i % j == 0)
break;
}
if (j == i)
cout << i << " ";
}
cout << endl;
return 0;
}
到此這篇關(guān)于C++哈希表之線性探測(cè)法詳解使用的文章就介紹到這了,更多相關(guān)C++線性探測(cè)法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在本文中我們給大家分享了C++ 編寫DLL文件給易語(yǔ)言調(diào)用的代碼和方法，需要的朋友們學(xué)習(xí)下。2019-01-01
這里給大家介紹了C++中對(duì)于pthread線程的一個(gè)簡(jiǎn)單應(yīng)用以及使用繼承CDoit，實(shí)現(xiàn)其中的start和end，有需要的小伙伴可以參考下2015-11-11
我最早接觸lambda的概念是在matlab中，那時(shí)候在做數(shù)值模擬的課題，lambda可以快速定義簡(jiǎn)單的函數(shù)，當(dāng)時(shí)覺(jué)得好方便。任何語(yǔ)言都有這個(gè)功能，下面來(lái)看看C++11新引入的lambda是如何使用的吧2023-04-04
在C語(yǔ)言里單引號(hào)和雙引號(hào)的區(qū)別
這篇文章主要介紹了在C語(yǔ)言里單引號(hào)和雙引號(hào)的區(qū)別,本文通過(guò)代碼的實(shí)例和注釋的詳細(xì)的說(shuō)明了單引號(hào)和雙引號(hào)的概念與區(qū)別,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++中實(shí)現(xiàn)線程安全和延遲執(zhí)行詳解
這篇文章主要為大家詳細(xì)介紹了C++中實(shí)現(xiàn)線程安全和延遲執(zhí)行的相關(guān)知識(shí)，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，需要的小伙伴可以了解下2024-01-01
這篇文章主要介紹了C++算法與泛型算法（algorithm、numeric）,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
這篇文章主要為大家詳細(xì)介紹了利用C語(yǔ)言實(shí)現(xiàn)掃雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-02-02
詳解C語(yǔ)言中fseek函數(shù)和ftell函數(shù)的使用方法
這篇文章主要介紹了C語(yǔ)言中fseek函數(shù)和ftell函數(shù)的使用方法,兩個(gè)函數(shù)分別用于設(shè)置和返回文件指針stream的位置,需要的朋友可以參考下2016-03-03
c++ vector模擬實(shí)現(xiàn)的全過(guò)程
這篇文章主要給大家介紹了關(guān)于c++ vector的模擬實(shí)現(xiàn)過(guò)程，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
C++中小數(shù)點(diǎn)輸出格式(實(shí)例代碼)
下面小編就為大家?guī)?lái)一篇C++中小數(shù)點(diǎn)輸出格式(實(shí)例代碼)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-06-06