一、散列表為什么可以在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)度