哈希表Hash table也稱(chēng)為散列表

它可以根據(jù)關(guān)鍵字的值直接進(jìn)行查詢與訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。

我們通常通過(guò)映射函數(shù)將關(guān)鍵字直接對(duì)應(yīng)到表中的某個(gè)位置，從而加快查找速度。

這個(gè)映射函數(shù)叫做哈希函數(shù)，存放記錄的數(shù)組叫做哈希表。

數(shù)組A中有N個(gè)整數(shù)從中查找整數(shù)key,確定key是否在其中，

用最樸素的方法是通過(guò)循環(huán)將key和每個(gè)整數(shù)按順序?qū)Ρ?，如果相等返?循環(huán)結(jié)束后返回0（但是這種方法的效率很低。

比如要查找1-10是否在A當(dāng)中，則要調(diào)用find-key需要對(duì)掃描10次。每次都要比較n次。所以要查詢的時(shí)間發(fā)雜度是大on，如果查詢次數(shù)為n，那么整體的復(fù)雜度就是大on的平方。

如果通過(guò)哈希表我們可以將整體的效率優(yōu)化到線性的大on。

哈希表的特例情況

加入數(shù)據(jù)的范圍是0-99并且類(lèi)型是整型，這種情況可以直接使用數(shù)組下標(biāo)來(lái)記錄元素是否出現(xiàn)。這個(gè)就是最簡(jiǎn)單的哈希思想。

具體來(lái)看

先設(shè)置一個(gè)長(zhǎng)度是100的數(shù)組table.初始化所有的元素為0

然后調(diào)用create_hash創(chuàng)建哈希表。在函數(shù)中使用i遍歷數(shù)組a中的全部n個(gè)元素，通過(guò)table 【i】加加，用table的下標(biāo)記記錄a[i出現(xiàn)的次數(shù)。

例如i等于0時(shí)，a[0]等于table [7加加

a[1]等于17table [17]

a[2]等于15table [5]加加

完成了遍歷之后table就記錄了a中的全部元素個(gè)數(shù)。從0到MAX_TABLE_LEN遍歷table，如果說(shuō)table [i]大于0打印i值出i現(xiàn)的次數(shù)table [i],這樣我們就得到了a中全部元素出現(xiàn)的個(gè)數(shù)。

在查找哈希表中是否存在key值時(shí)，如果table[key]bushi 0fanhui 否則返回0，測(cè)試1到10調(diào)用find_key得到查找結(jié)果2 3 5 7 8 9對(duì)應(yīng)的tabl值都不為0，所以這些數(shù)字都在數(shù)組a中出現(xiàn)了。

通過(guò)上面這種方法不僅可以用來(lái)查找，還可以用來(lái)排序。我們一起來(lái)想象一下，如果數(shù)組a中有n個(gè)元素。

非常大，不如達(dá)到100W，但a中數(shù)據(jù)的取值范圍非常小，比如從0到99，那么通過(guò)0到99長(zhǎng)度的table。

由于table[i]代表了數(shù)據(jù)I出現(xiàn)的次數(shù)。在排序時(shí)從0到MAX_TABLE_LEN循環(huán)i。再將table[i]個(gè)i添加到a中就可以了。

eg:使用table將a的每個(gè)元素個(gè)數(shù)統(tǒng)計(jì)后，從0到99遍歷出現(xiàn)了2次2個(gè)2被添加a，然后是3.........，這樣就完成了a的排序

當(dāng)n遠(yuǎn)大于表長(zhǎng)時(shí)，這種方法的復(fù)雜度就大On,優(yōu)于一般的排序算啊n倍的logn

如果數(shù)組a中的數(shù)據(jù)范圍不是0到99，而是int型的2的31次方?；蛘呤歉↑c(diǎn)數(shù)，字符串，甚至是數(shù)組、對(duì)象......

如何處理？

要使用哈希函數(shù)，我們將待存儲(chǔ)的數(shù)據(jù)轉(zhuǎn)換為表長(zhǎng)范圍內(nèi)額整數(shù)。然后再使用數(shù)組小標(biāo)進(jìn)行訪問(wèn)。對(duì)于整數(shù)數(shù)據(jù)可以直接取余表長(zhǎng)。對(duì)應(yīng)的哈希值。如果是字符串，需要專(zhuān)門(mén)的設(shè)計(jì)哈希函數(shù)。最簡(jiǎn)單的比如遍歷字符串中的字符。將它們中的ASC2碼相加得到整數(shù)。再取余表長(zhǎng)得到哈希值。

e如果要將523插入到長(zhǎng)度為100的table中。令523取余100得23在將table【23】加1.table的下表23就記錄了這個(gè)523的數(shù)字。字符串a(chǎn)b的ASC2碼分別是97 98 99，將它們相加得294取余100是94，那么table [94]就記錄了ab是否出現(xiàn)。

哈希函數(shù)可能將不同的數(shù)據(jù)映射到，同一個(gè)數(shù)組下標(biāo)上這樣就發(fā)生了沖突。

eg:按照上面的方法，523和23會(huì)映射到table[23] ,abc和cba會(huì)映射到table[94]打印哈希表發(fā)現(xiàn)table [23]和table{94]等于2.

并且123 223 323 acb cab bc等等。都會(huì)發(fā)生同樣的沖突問(wèn)題。

當(dāng)沖突發(fā)生時(shí)就導(dǎo)致查詢時(shí)出現(xiàn)錯(cuò)誤。

eg，如果數(shù)組a中包括3table[5]映射為1，當(dāng)查詢103時(shí)，也會(huì)返回1.

但其實(shí)a中并不包括103.

如何解決哈希表的沖突問(wèn)題呢？

很多經(jīng)典的方法。

eg線性探測(cè)，拉鏈法。