我們知道，通過(guò)對(duì)數(shù)組進(jìn)行直接尋址（Direct Addressing），可以在 O(1) 時(shí)間內(nèi)訪問(wèn)數(shù)組中的任意元素。所以，如果存儲(chǔ)空間允許，可以提供一個(gè)數(shù)組，為每個(gè)可能的關(guān)鍵字保留一個(gè)位置，就可以應(yīng)用直接尋址技術(shù)。

hash 算法能以空間換時(shí)間。通過(guò) hash，生成不可逆的信息摘要

哈希表（Hash Table）是普通數(shù)組概念的推廣。當(dāng)實(shí)際存儲(chǔ)的的關(guān)鍵字?jǐn)?shù)比可能的關(guān)鍵字總數(shù)較小時(shí)，這時(shí)采用哈希表就會(huì)比使用直接數(shù)組尋址更為有效。因?yàn)楣１硗ǔ２捎玫臄?shù)組尺寸與所要存儲(chǔ)的關(guān)鍵字?jǐn)?shù)是成比例的。

哈希表是一種動(dòng)態(tài)集合數(shù)據(jù)結(jié)構(gòu)，在一些合理的假設(shè)下，在哈希表中查找一個(gè)元素的期望時(shí)間是 O(1) 。

什么是哈希表？

哈希表（Hash table，也叫散列表），是根據(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í)很簡(jiǎn)單，就是把Key通過(guò)一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字，然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里。

什么是Hash
Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長(zhǎng)度的輸入（又叫做預(yù)映射， pre-image），通過(guò)散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，而不可能從散列值來(lái)唯一的確定輸入值。簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)。

HASH主要用于信息安全領(lǐng)域中加密算法，它把一些不同長(zhǎng)度的信息轉(zhuǎn)化成雜亂的128位的編碼,這些編碼值叫做HASH值. 也可以說(shuō)，hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系。

數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；
鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。

那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實(shí)現(xiàn)方法，我接下來(lái)解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數(shù)組”，如圖：

hash表，有時(shí)候也被稱為散列表。個(gè)人認(rèn)為，hash表是介于鏈表和二叉樹(shù)之間的一種中間結(jié)構(gòu)。鏈表使用十分方便，但是數(shù)據(jù)查找十分麻煩；二叉樹(shù)中的數(shù)據(jù)嚴(yán)格有序，但是這是以多一個(gè)指針作為代價(jià)的結(jié)果。hash表既滿足了數(shù)據(jù)的查找方便，同時(shí)不占用太多的內(nèi)容空間，使用也十分方便。

打個(gè)比方來(lái)說(shuō)，所有的數(shù)據(jù)就好像許許多多的書本。如果這些書本是一本一本堆起來(lái)的，就好像鏈表或者線性表一樣，整個(gè)數(shù)據(jù)會(huì)顯得非常的無(wú)序和凌亂，在你找到自己需要的書之前，你要經(jīng)歷許多的查詢過(guò)程；而如果你對(duì)所有的書本進(jìn)行編號(hào)，并且把這些書本按次序進(jìn)行排列的話，那么如果你要尋找的書本編號(hào)是n，那么經(jīng)過(guò)二分查找，你很快就會(huì)找到自己需要的書本；但是如果你每一個(gè)種類的書本都不是很多，那么你就可以對(duì)這些書本進(jìn)行歸類，哪些是文學(xué)類，哪些是藝術(shù)類，哪些是工科的，哪些是理科的，你只要對(duì)這些書本進(jìn)行簡(jiǎn)單的歸類，那么尋找一本書也會(huì)變得非常簡(jiǎn)單，比如說(shuō)如果你要找的書是計(jì)算機(jī)方面的書，那么你就會(huì)到工科一類當(dāng)中去尋找，這樣查找起來(lái)也會(huì)顯得麻煩。

不知道這樣舉例你清楚了沒(méi)有，上面提到的歸類方法其實(shí)就是hash表的本質(zhì)。

哈希表（Hash table，也叫散列表），是根據(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ù)組叫做散列表。

記錄的存儲(chǔ)位置=f(關(guān)鍵字)

這里的對(duì)應(yīng)關(guān)系f稱為散列函數(shù)，又稱為哈希（Hash函數(shù)），采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)存儲(chǔ)空間稱為散列表或哈希表（Hash table）。

哈希表hashtable(key，value) 就是把Key通過(guò)一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字，然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里。（或者：把任意長(zhǎng)度的輸入（又叫做預(yù)映射， pre-image），通過(guò)散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，而不可能從散列值來(lái)唯一的確定輸入值。簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)。）

而當(dāng)使用哈希表進(jìn)行查詢的時(shí)候，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對(duì)應(yīng)的數(shù)組下標(biāo)，并定位到該空間獲取value，如此一來(lái)，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位。

總結(jié)

以上是生活随笔為你收集整理的Hash-哈希/散列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。