C++哈希表之線性探測法實現(xiàn)詳解
更新時間：2022年05月04日 10:50:24 作者：liufeng2023
線性探測法的優(yōu)點：只要散列表未滿，總能找到一個不沖突的散列地址；缺點：每個產(chǎn)生沖突的記錄被散列到離沖突最近的空地址上，從而又增加了更多的沖突機會
1、哈希表-線性探測法理論
線性探測法的理論我們在上一篇博客已經(jīng)闡述了。
現(xiàn)在我們來看看線性探測法的增刪查的代碼思想：
1.1、哈希表的增加元素
注意：
往后遍歷尋找空閑位置的時候，要注意是環(huán)形遍歷哦！不然訪問數(shù)組就越界了。
在添加元素，發(fā)生位置被占用，即發(fā)生哈希沖突后，在向后遍歷尋找空閑位置的時候，我們要知道，這個空閑的位置是有兩種情況的：
1、這個位置一直是空的，沒放過元素。
2、這個位置是空的，以前放過元素，后來被刪除了。
1.2、哈希表的查詢操作
- 當用哈希函數(shù)計算得出的下標值是3，然后去訪問數(shù)組，查詢時，發(fā)現(xiàn)該值不等于要查詢的元素的值val，說明當時放val的時候發(fā)生了哈希沖突，這時候就要向后遍歷了；
- 訪問4下標的時候發(fā)現(xiàn)這個位置是空的（空的有兩種情況），如果這個位置一直是空的，則就不用繼續(xù)向后找了，val不存在！因為是線性探測法，所以當時val如果要放的時候肯定是要放在這里的。
- 但是如果這個位置是空的，但是之前放過元素，后來被刪除了，這個位置之前存放了元素，然后val插入的時候，就插到后面的空閑的位置了，所以此時我們還要繼續(xù)往后遍歷尋找val值。
所以我們需要定義一個Bucket節(jié)點來表示每一個元素的所有的內(nèi)容。
//桶的狀態(tài)
enum State
{
STATE_UNUSE, //從未使用過的桶
STATE_USING, //正在使用的桶 放著是一個有效的元素，沒有被刪過
STATE_DEL, //元素被刪除了的桶，認為桶里的元素無效了
};
//我們刪除桶里的元素，并不是真正把值刪除掉，而是把桶的狀態(tài)置為STATE_DEL就認為桶里的元素無效了
//桶的類型
struct Bucket
{
Bucket(int key = 0, State state = STATE_UNUSE)
: key_(key)
, state_(state)
{}
int key_; //存儲的數(shù)據(jù)
State state_; //桶的當前狀態(tài)
};
1.3、哈希表的刪除操作
2、哈希表-線性探測法代碼實現(xiàn)
2.1、素數(shù)表中的素數(shù)
求素數(shù)的代碼：（用于素數(shù)表中的素數(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;
}
到此這篇關于C++哈希表之線性探測法詳解使用的文章就介紹到這了,更多相關C++線性探測法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
C語言庫函數(shù)是把自定義函數(shù)放到庫里，是別人把一些常用到的函數(shù)編完放到一個文件里，供程序員使用，下面讓我們一起來詳細了解它2022-07-07
這篇文章主要為大家介紹了C++遞歸與分治算法的策略原理示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2021-11-11
C語言FlappyBird飛揚的小鳥實現(xiàn)開發(fā)流程
因為在家宅了好多天，隨手玩了下自己以前做的一些小游戲，說真的，有幾個游戲做的是真的劣質(zhì)，譬如 flappybird 真的讓我難以忍受，于是重做了一波分享給大家2022-11-11
C++11中的時間庫std::chrono（引發(fā)關于時間的思考）
這篇文章主要介紹了C++11中的時間庫std::chrono（引發(fā)關于時間的思考）,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-04-04
這篇文章主要介紹了C++編程指向成員的指針以及this指針的基本使用指南,與C語言一樣,存儲的數(shù)值被解釋成為內(nèi)存里的一個地址,需要的朋友可以參考下2016-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單的推箱子游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
C語言實現(xiàn)字符串轉(zhuǎn)浮點函數(shù)的示例
字符串不僅可以轉(zhuǎn)換為整數(shù)，也可以轉(zhuǎn)換為浮點數(shù)，本文主要介紹了C語言實現(xiàn)字符串轉(zhuǎn)浮點函數(shù)的示例，具有一定的參考價值，感興趣的可以了解一下2022-02-02
大家好，本篇文章主要講的是c語言static關鍵字用法詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
這篇文章主要為大家介紹了C++ LeetCode300最長遞增子序列示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12
本文主要介紹了Qt自制一個小鬧鐘的實現(xiàn)示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-09-09