前言


????哈希表，又名散列表。是非常常用的一種數(shù)據(jù)結(jié)構(gòu)，C#的Hashtable、字典，Java的HashMap，Redis的Hash，其底層實(shí)現(xiàn)都是散列表。而在一些互聯(lián)網(wǎng)公司的面試中，更是技術(shù)面試官們必問(wèn)的一道題目。本文將簡(jiǎn)單了解哈希表(散列表)這種數(shù)據(jù)結(jié)構(gòu)。

一、散列表

1.1 散列表


????散列表(哈希表)，其思想主要是基于數(shù)組支持按照下標(biāo)隨機(jī)訪問(wèn)數(shù)據(jù)時(shí)間復(fù)雜度為O(1)的特性?？墒钦f(shuō)是數(shù)組的一種擴(kuò)展。假設(shè)，我們?yōu)榱朔奖阌涗浤掣咝?shù)學(xué)專(zhuān)業(yè)的所有學(xué)生的信息。要求可以按照學(xué)號(hào)(學(xué)號(hào)格式為:入學(xué)時(shí)間+年級(jí)+專(zhuān)業(yè)+專(zhuān)業(yè)內(nèi)自增序號(hào)，如2011
1101 0001)能夠快速找到某個(gè)學(xué)生的信息。這個(gè)時(shí)候我們可以取學(xué)號(hào)的自增序號(hào)部分，即后四位作為數(shù)組的索引下標(biāo)，把學(xué)生相應(yīng)的信息存儲(chǔ)到對(duì)應(yīng)的空間內(nèi)即可。




????如上圖所示,我們把學(xué)號(hào)作為key,通過(guò)截取學(xué)號(hào)后四位的函數(shù)后計(jì)算后得到索引下標(biāo)，將數(shù)據(jù)存儲(chǔ)到數(shù)組中。當(dāng)我們按照鍵值(學(xué)號(hào))查找時(shí)，只需要再次計(jì)算出索引下標(biāo)，然后取出相應(yīng)數(shù)據(jù)即可。以上便是散列思想。

1.2 散列函數(shù)

????上面的例子中，截取學(xué)號(hào)后四位的函數(shù)即是一個(gè)簡(jiǎn)單的散列函數(shù)。
//散列函數(shù) 偽代碼 int Hash(string key) { // 獲取后四位字符 string hashValue
=int.parse(key.Substring(key.Length-4, 4)); // 將后兩位字符轉(zhuǎn)換為整數(shù) return hashValue; }

在這里散列函數(shù)的作用就是講key值映射成數(shù)組的索引下標(biāo)。關(guān)于散列函數(shù)的設(shè)計(jì)方法有很多，如:直接尋址法、數(shù)字分析法、隨機(jī)數(shù)法等等。但即使是再優(yōu)秀的設(shè)計(jì)方法也不能避免散列沖突。在散列表中散列函數(shù)不應(yīng)設(shè)計(jì)太復(fù)雜。

1.3 散列沖突



????散列函數(shù)具有確定性和不確定性。

* 確定性:哈希的散列值不同，那么哈希的原始輸入也就不同。即:key1=key2,那么hash(key1)=hash(key2)。
* 不確定性:同一個(gè)散列值很有可能對(duì)應(yīng)多個(gè)不同的原始輸入。即:key1≠key2，hash(key1)=hash(key2)。

散列沖突,即key1≠key2，hash(key1)=hash(key2)的情況。散列沖突是不可避免的，如果我們key的長(zhǎng)度為100，而數(shù)組的索引數(shù)量只有50，那么再優(yōu)秀的算法也無(wú)法避免散列沖突。關(guān)于散列沖突也有很多解決辦法，這里簡(jiǎn)單復(fù)習(xí)兩種：開(kāi)放尋址法和鏈表法。

1.3.1 開(kāi)放尋址法


????開(kāi)放尋址法的核心思想是，如果出現(xiàn)了散列沖突，我們就重新探測(cè)一一個(gè)空閑位置，將其插入。比如，我們可以使用線(xiàn)性探測(cè)法。當(dāng)我們往散列表中插入數(shù)據(jù)時(shí)，如果某個(gè)數(shù)據(jù)經(jīng)過(guò)散列函數(shù)散列之后，存儲(chǔ)位置已經(jīng)被占用了，我們就從當(dāng)前位置開(kāi)始，依次往后查找，看是否有空閑位置，如果遍歷到尾部都沒(méi)有找到空閑的位置，那么我們就再?gòu)谋眍^開(kāi)始找，直到找到為止。




????散列表中查找元素的時(shí)候，我們通過(guò)散列函數(shù)求出要查找元素的鍵值對(duì)應(yīng)的散列值，然后比較數(shù)組中下標(biāo)為散列值的元素和要查找的元素。如果相等，則說(shuō)明就是我們要找的元素；否則就順序往后依次查找。如果遍歷到數(shù)組中的空閑位置還沒(méi)有找到，就說(shuō)明要查找的元素并沒(méi)有在散列表中。


????對(duì)于刪除操作稍微有些特別，不能單純地把要?jiǎng)h除的元素設(shè)置為空。因?yàn)樵诓檎业臅r(shí)候，一旦我們通過(guò)線(xiàn)性探測(cè)方法，找到一個(gè)空閑位置，我們就可以認(rèn)定散列表中不存在這個(gè)數(shù)據(jù)。但是，如果這個(gè)空閑位置是我們后來(lái)刪除的，就會(huì)導(dǎo)致原來(lái)的查找算法失效。這里我們可以將刪除的元素，特殊標(biāo)記為
deleted。當(dāng)線(xiàn)性探測(cè)查找的時(shí)候，遇到標(biāo)記為 deleted 的空間，并不是停下來(lái)，而是繼續(xù)往下探測(cè)。


????線(xiàn)性探測(cè)法存在很大問(wèn)題。當(dāng)散列表中插入的數(shù)據(jù)越來(lái)越多時(shí)，其散列沖突的可能性就越大，極端情況下甚至要探測(cè)整個(gè)散列表,因此最壞時(shí)間復(fù)雜度為O(N)。在開(kāi)放尋址法中，除了線(xiàn)性探測(cè)法，我們還可以二次探測(cè)和雙重散列等方式。

1.3.2 鏈表法(拉鏈法)

????簡(jiǎn)單來(lái)講就是在沖突的位置拉一條鏈表來(lái)存儲(chǔ)數(shù)據(jù)。


????鏈表法是一種比較常用的散列沖突解決辦法,Redis使用的就是鏈表法來(lái)解決散列沖突。鏈表法的原理是:如果遇到?jīng)_突，他就會(huì)在原地址新建一個(gè)空間，然后以鏈表結(jié)點(diǎn)的形式插入到該空間。當(dāng)插入的時(shí)候，我們只需要通過(guò)散列函數(shù)計(jì)算出對(duì)應(yīng)的散列槽位，將其插入到對(duì)應(yīng)鏈表中即可。



1.3.3 負(fù)載因子與rehash

????我們可以使用裝載因子來(lái)衡量散列表的“健康狀況”。
散列表的負(fù)載因子 = 填入表中的元素個(gè)數(shù)/散列表的長(zhǎng)度
散列表負(fù)載因子越大，代表空閑位置越少，沖突也就越多，散列表的性能會(huì)下降。


????對(duì)于散列表來(lái)說(shuō)，負(fù)載因子過(guò)大或過(guò)小都不好，負(fù)載因子過(guò)大，散列表的性能會(huì)下降。而負(fù)載因子過(guò)小，則會(huì)造成內(nèi)存不能合理利用，從而形成內(nèi)存浪費(fèi)。因此我們?yōu)榱吮ＷC負(fù)載因子維持在一個(gè)合理的范圍內(nèi)，要對(duì)散列表的大小進(jìn)行收縮或擴(kuò)展，即rehash。散列表的rehash過(guò)程類(lèi)似于數(shù)組的收縮與擴(kuò)容。

1.3.4 開(kāi)放尋址法與鏈表法比較

????對(duì)于開(kāi)放尋址法解決沖突的散列表，由于數(shù)據(jù)都存儲(chǔ)在數(shù)組中，因此可以有效地利用 CPU
緩存加快查詢(xún)速度(數(shù)組占用一塊連續(xù)的空間)。但是刪除數(shù)據(jù)的時(shí)候比較麻煩，需要特殊標(biāo)記已經(jīng)刪除掉的數(shù)據(jù)。而且，在開(kāi)放尋址法中，所有的數(shù)據(jù)都存儲(chǔ)在一個(gè)數(shù)組中，比起鏈表法來(lái)說(shuō)，沖突的代價(jià)更高。所以，使用開(kāi)放尋址法解決沖突的散列表，負(fù)載因子的上限不能太大。這也導(dǎo)致這種方法比鏈表法更浪費(fèi)內(nèi)存空間。


????對(duì)于鏈表法解決沖突的散列表,對(duì)內(nèi)存的利用率比開(kāi)放尋址法要高。因?yàn)殒湵斫Y(jié)點(diǎn)可以在需要的時(shí)候再創(chuàng)建，并不需要像開(kāi)放尋址法那樣事先申請(qǐng)好。鏈表法比起開(kāi)放尋址法，對(duì)大裝載因子的容忍度更高。開(kāi)放尋址法只能適用裝載因子小于1的情況。接近1時(shí)，就可能會(huì)有大量的散列沖突，性能會(huì)下降很多。但是對(duì)于鏈表法來(lái)說(shuō)，只要散列函數(shù)的值隨機(jī)均勻，即便裝載因子變成10，也就是鏈表的長(zhǎng)度變長(zhǎng)了而已，雖然查找效率有所下降，但是比起順序查找還是快很多。但是，鏈表因?yàn)橐鎯?chǔ)指針，所以對(duì)于比較小的對(duì)象的存儲(chǔ)，是比較消耗內(nèi)存的，而且鏈表中的結(jié)點(diǎn)是零散分布在內(nèi)存中的，不是連續(xù)的，所以對(duì)CPU緩存是不友好的，這對(duì)于執(zhí)行效率有一定的影響。

小結(jié)

????對(duì)于一些一線(xiàn)城市的互聯(lián)網(wǎng)公司，技術(shù)面試官比較喜歡考察一個(gè)人的基礎(chǔ)，像哈希這種經(jīng)典而又應(yīng)用廣泛的數(shù)據(jù)結(jié)構(gòu)更是老生常談之題目。大致提問(wèn)方式無(wú)非以下幾種

* C#字典（java hashmap或者Redis hash）的底層實(shí)現(xiàn)方式
* 說(shuō)一下什么是哈希表(散列表)
* 哈希如何解決碰撞(散列如何解決沖突)
-----END-----

感謝大家閱讀，如有問(wèn)題可在文章下方留言，我會(huì)在第一時(shí)間回復(fù)！

• ? 上一篇：IIS網(wǎng)站服務(wù)器性能優(yōu)化攻略
• ? 下一篇：泥瓦匠 5 年 Java 的成長(zhǎng)感悟（下）