?1.先說結(jié)論

在使用哈希表時，往往會出現(xiàn)哈希沖突，此時就會通過鏈表/紅黑樹的方法來解決沖突，此時引入鏈表/紅黑樹那么時間復(fù)雜度就不是嚴格的O（1)。
我們首先要明白N代表什么，N是指問題的規(guī)模大小。
在使用哈希表時，所有的數(shù)據(jù)個數(shù)為N，鏈表的長度肯定不是N，（因為存在著很多鏈表，理論上時存在著所有的數(shù)據(jù)都在一個鏈表上，但在實際的開發(fā)中，是不會出現(xiàn)的），此外，在哈希表的插入中，當負載因子過大時，哈希表會進行擴容，數(shù)據(jù)會重新哈希，重新分配到鏈表上，確保每個鏈表上的元素不會過多，就近似會認為是O（1）了。

?2.哈希表的概念

順序結(jié)構(gòu)以及平衡樹中，元素關(guān)鍵碼與其存儲位置之間沒有對應(yīng)的關(guān)系，因此在查找一個元素時，必須要經(jīng)過關(guān)鍵碼的多次比較。順序查找時間復(fù)雜度為O(N)，平衡樹中為樹的高度，即O( )，搜索的效率取決于搜索過程中元素的比較次數(shù)。

理想的搜索方法：可以不經(jīng)過任何比較，一次直接從表中得到要搜索的元素。 如果構(gòu)造一種存儲結(jié)構(gòu)，通過某種函數(shù)(hashFunc)使元素的存儲位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，那么在查找時通過該函數(shù)可以很快找到該元素。

當向該結(jié)構(gòu)中：

• 插入元素
  根據(jù)待插入元素的關(guān)鍵碼，以此函數(shù)計算出該元素的存儲位置并按此位置進行存放
• 搜索元素
  對元素的關(guān)鍵碼進行同樣的計算，把求得的函數(shù)值當做元素的存儲位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜索成功。
  該方式即為哈希(散列)方法，哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希(散列)函數(shù)，構(gòu)造出來的結(jié)構(gòu)稱為哈希表(HashTable)(或者稱散列表)

?3.哈希沖突

了解哈希表中數(shù)據(jù)發(fā)生沖突時的處理方法，也就是了解哈希表的底層原理。

3.1閉散列

閉散列：也叫開放定址法，當發(fā)生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把key存放到?jīng)_突位置中的“下一個” 空位置中去。

• 通過哈希函數(shù)獲取待插入元素在哈希表中的位置
• 如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發(fā)生哈希沖突，使用線性探測找到下一個空位置，插入新元素
• 采用閉散列處理哈希沖突時，不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會影響其他元素的搜索。比如刪除元素4，如果直接刪除掉，44查找起來可能會受影響。因此線性探測采用標記的偽刪除法來刪除一個元素。
  

二次探測

線性探測的缺陷是產(chǎn)生沖突的數(shù)據(jù)堆積在一塊，這與其找下一個空位置有關(guān)系，因為找空位置的方式就是挨著往后逐個去找，因此二次探測為了避免該問題，找下一個空位置的方法為： = ( + )% m, 或者：= ( - )% m。其中：i = 1,2,3…， 是通過散列函數(shù)Hash(x)對元素的關(guān)鍵碼 key 進行計算得到的位置，m是表的大小。 對于2.1中如果要插入44，產(chǎn)生沖突，使用解決后的情況為：

3.2開散列/哈希桶

開散列法又叫鏈地址法(開鏈法)，首先對關(guān)鍵碼集合用散列函數(shù)計算散列地址，具有相同地址的關(guān)鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結(jié)點存儲在哈希表中。

1. 每個桶的背后是另一個哈希表
2. 每個桶的背后是一棵搜索樹

以上就是本文所有內(nèi)容，如果對你有幫助的話，點贊收藏支持一下吧！文章來源地址http://www.zghlxwxcb.cn/news/detail-842018.html

到了這里，關(guān)于【哈希表】為什么哈希表的插入/刪除/查找時間復(fù)雜度為O（1）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！