国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機(jī)構(gòu)

手機(jī)站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時(shí)隨地免費(fèi)學(xué)

千鋒教育

掃一掃進(jìn)入千鋒手機(jī)站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時(shí)隨地免費(fèi)學(xué)習(xí)課程

當(dāng)前位置:首頁(yè)  >  技術(shù)干貨  > 散列表為什么可以在O(1)時(shí)間復(fù)雜度內(nèi)查找散列值?

散列表為什么可以在O(1)時(shí)間復(fù)雜度內(nèi)查找散列值?

來(lái)源:千鋒教育
發(fā)布人:xqq
時(shí)間: 2023-10-11 06:26:10 1696976770

一、散列表為什么可以在O(1)時(shí)間復(fù)雜度內(nèi)查找散列值

因?yàn)楣:瘮?shù)的功能就是完成鍵到哈希值的映射,映射到的哈希值就是一個(gè)數(shù)字,被用來(lái)當(dāng)作數(shù)組的下標(biāo),這個(gè)元素就是存儲(chǔ)在數(shù)組的這個(gè)下標(biāo)內(nèi)。散列表用的其實(shí)是數(shù)組隨機(jī)存取的特性。數(shù)組隨機(jī)存取的復(fù)雜度就是O(1),所以散列表的查找效率就是O(1)。

什么是散列表

散列表(hash table),我們平時(shí)叫它哈希表或者Hash 表,你肯定經(jīng)常聽(tīng)到它。

散列表是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō),它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄,以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù),存放記錄的數(shù)組叫做散列表。

由定義我們可以知道,散列表用的是數(shù)組支持下標(biāo)訪問(wèn)數(shù)據(jù)的特性,所以散列表是數(shù)組的一種擴(kuò)展,有數(shù)組演化而來(lái)。

延伸閱讀:

二、開(kāi)放尋址法

開(kāi)發(fā)尋址法就是但我們遇到了哈希沖突,我們就重新探索一個(gè)空閑位置,然后插入。

我們探索空閑位置有以下幾種方法。

線(xiàn)性探測(cè)

當(dāng)我們往散列表中插入數(shù)據(jù)時(shí),經(jīng)過(guò)散列函數(shù)發(fā)現(xiàn)位置已經(jīng)被占用了,我們就從當(dāng)前位置開(kāi)始,依次往后查找,直到找到空閑位置為止。

比如一個(gè)散列表的大小為 10,一個(gè)數(shù)據(jù)經(jīng)過(guò)散列函數(shù)之后,到了下標(biāo)為 8 的位置,但是發(fā)現(xiàn)這個(gè)位置已經(jīng)有數(shù)據(jù)了,那么就依次往后遍歷,如果到了尾部,還是沒(méi)有找到空閑位置,那么就再?gòu)念^開(kāi)始找,直到找到空閑位置。

查找元素和插入類(lèi)似,通過(guò)散列函數(shù)計(jì)算出哈希值,然后找到對(duì)應(yīng)位置數(shù)據(jù),然后與查找的元素進(jìn)行比較,如果相等,則它就是我們要找的數(shù)據(jù),如果不相等,就依次往后遍歷,如果遍歷到空閑位置還沒(méi)找到,就說(shuō)明元素不在散列表中。

但是刪除的時(shí)候稍微有點(diǎn)特別,我們不能直接刪除數(shù)據(jù),因?yàn)槲覀冊(cè)诓檎业臅r(shí)候,如果找到一個(gè)空閑位置,就說(shuō)元素不在散列表中,如果我們直接刪除了之后可能會(huì)導(dǎo)致某些元素找不到。所以我們將要?jiǎng)h除的元素,標(biāo)記為 deleted,當(dāng)我們查找的時(shí)候,遇到標(biāo)記為 deleted 的元素,繼續(xù)往下遍歷。

線(xiàn)性探測(cè)法存在很大的問(wèn)題,當(dāng)散列表中插入的元素越來(lái)越多時(shí),發(fā)生散列沖突的概率就越來(lái)越大,空閑的位置就越來(lái)越少,先行探索的時(shí)間就會(huì)越來(lái)越長(zhǎng),甚至在極端情況下,我們需要遍歷整個(gè)散列表。

二次探索

二次探索,和線(xiàn)性探索原理一樣,先行探索每次的步長(zhǎng)為 1 ,探索的下標(biāo)依次為 hash(key)+0,hash(key)+1,hash(key)+2…,二次探索每次的步長(zhǎng)變?yōu)樵瓉?lái)的二次方,所以每次探索的下邊為 hash(key)+0,hash(key)+1^2,hash(key)+2^2。

雙重散列

原來(lái)我們使用一個(gè)散列函數(shù),雙重散列,我們使用多個(gè)散列函數(shù),我們先用名列前茅個(gè)散列函數(shù),如果計(jì)算得到的位置已經(jīng)被占用,就使用第二個(gè)散列函數(shù),以此類(lèi)推,直到找到空閑時(shí)的位置。

不管用哪個(gè)探索方法,當(dāng)空閑位置變少的時(shí)候,散列沖突的概率會(huì)變得很高。為了盡可能保證散列表的操作效率,一般情況下,我們會(huì)盡可能保證散列表中有一定比例的空閑槽位。我們用裝載因子來(lái)表示空位的多少。 裝載因子 = 填入散列表的元素個(gè)數(shù) / 散列表的長(zhǎng)度

聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強(qiáng)師集結(jié),手把手帶你蛻變精英
請(qǐng)您保持通訊暢通,專(zhuān)屬學(xué)習(xí)老師24小時(shí)內(nèi)將與您1V1溝通
免費(fèi)領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學(xué) 138****2860 剛剛成功領(lǐng)取
王同學(xué) 131****2015 剛剛成功領(lǐng)取
張同學(xué) 133****4652 剛剛成功領(lǐng)取
李同學(xué) 135****8607 剛剛成功領(lǐng)取
楊同學(xué) 132****5667 剛剛成功領(lǐng)取
岳同學(xué) 134****6652 剛剛成功領(lǐng)取
梁同學(xué) 157****2950 剛剛成功領(lǐng)取
劉同學(xué) 189****1015 剛剛成功領(lǐng)取
張同學(xué) 155****4678 剛剛成功領(lǐng)取
鄒同學(xué) 139****2907 剛剛成功領(lǐng)取
董同學(xué) 138****2867 剛剛成功領(lǐng)取
周同學(xué) 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT
數(shù)據(jù)結(jié)構(gòu)里的逐點(diǎn)插入法、排序二叉樹(shù)是什么?

一、數(shù)據(jù)結(jié)構(gòu)里的逐點(diǎn)插入法、排序二叉樹(shù)逐點(diǎn)插入法三角剖分是一種研究方法。三角剖分≠TIN三角剖分是代數(shù)拓?fù)鋵W(xué)里最基本的研究方法。 以曲面為...詳情>>

2023-10-11 08:08:01
在數(shù)據(jù)結(jié)構(gòu)中i=L->length是什么意思?

一、在數(shù)據(jù)結(jié)構(gòu)中i=L->length是什么意思在數(shù)據(jù)結(jié)構(gòu)中,i=L->length通常表示一個(gè)線(xiàn)性表L的長(zhǎng)度,即L中元素的個(gè)數(shù)。線(xiàn)性表是一種數(shù)據(jù)結(jié)構(gòu),它由n...詳情>>

2023-10-11 07:54:48
Treewidth比較小的圖有什么應(yīng)用?

一、Treewidth比較小的圖的應(yīng)用1、圖分解 Treewidth可以用于將復(fù)雜的圖分解成若干個(gè)簡(jiǎn)單的子圖,從而簡(jiǎn)化圖的處理。具體來(lái)說(shuō),對(duì)于一個(gè)具有較小...詳情>>

2023-10-11 07:51:56
結(jié)構(gòu)體變量做函數(shù)參數(shù),使用引用和不用引用有什么區(qū)別?

一、結(jié)構(gòu)體變量做函數(shù)參數(shù),使用引用和不用引用的區(qū)別引用實(shí)際上是變量別名。效果等同于操作原對(duì)象。不傳引用新建了一個(gè)Stack副本,副本指針的...詳情>>

2023-10-11 07:36:27
定義數(shù)據(jù)結(jié)構(gòu)中重復(fù)定義結(jié)構(gòu)體類(lèi)型的作用是什么?

一、定義數(shù)據(jù)結(jié)構(gòu)中重復(fù)定義結(jié)構(gòu)體類(lèi)型的作用定義數(shù)據(jù)結(jié)構(gòu)中重復(fù)定義結(jié)構(gòu)體類(lèi)型的作用是為了更加直觀的表達(dá)數(shù)據(jù)類(lèi)型。比如Position FindMin(Sea...詳情>>

2023-10-11 07:34:37
快速通道