這篇文章主要介紹“java數(shù)據(jù)結(jié)構(gòu)和算法中哈希表知識(shí)點(diǎn)有哪些”，在日常操作中，相信很多人在java數(shù)據(jù)結(jié)構(gòu)和算法中哈希表知識(shí)點(diǎn)有哪些問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”java數(shù)據(jù)結(jié)構(gòu)和算法中哈希表知識(shí)點(diǎn)有哪些”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！
1.哈希表簡(jiǎn)介
哈希表（hash table）是一種數(shù)據(jù)結(jié)構(gòu)，提供很快速的插入和查找操作（有的時(shí)候甚至刪除操作也是），時(shí)間復(fù)雜度為O(1)，對(duì)比時(shí)間復(fù)雜度就可以知道哈希表比樹的效率快得多，并且哈希表的實(shí)現(xiàn)也相對(duì)容易，然而沒有任何一種數(shù)據(jù)結(jié)構(gòu)是完美的，哈希表也是；哈希表較大的缺陷就是基于數(shù)組，因?yàn)閿?shù)組初始化的時(shí)候大小是確定的，數(shù)組創(chuàng)建后擴(kuò)展起來比較困難；
當(dāng)哈希表裝滿了之后，就要把數(shù)據(jù)轉(zhuǎn)移到一個(gè)更大的哈希表中，這會(huì)很費(fèi)時(shí)間，而且哈希表不支持有順序的遍歷，因?yàn)閺墓１碇斜闅v數(shù)據(jù)是隨機(jī)的；所以我們使用哈希表的前提是：不需要有序的遍歷數(shù)據(jù)，可以大概知道數(shù)據(jù)量的多少；滿足這兩點(diǎn)就可以用哈希表；
那有人就要問了，說得這么厲害，哈希表到底是什么樣子的啊？下面就隨便說兩個(gè)吧。。。
很經(jīng)典的例子就是英語字典，我們查字典的時(shí)候可以根據(jù)這個(gè)單詞就可以找到第xxx頁，在這里該單詞和頁數(shù)就對(duì)應(yīng)起來了，這可以說是一個(gè)哈希表；
再舉個(gè)現(xiàn)實(shí)中的例子，在上學(xué)的時(shí)候每個(gè)人在學(xué)校里都會(huì)有一個(gè)學(xué)號(hào)，你這個(gè)人在學(xué)校中就對(duì)應(yīng)這個(gè)學(xué)號(hào)，假如校長(zhǎng)手上有一個(gè)記錄全校學(xué)生的表，然后根據(jù)學(xué)號(hào)找一個(gè)學(xué)生時(shí)，就能很快鎖定這個(gè)學(xué)生的姓名，性別，班級(jí)等信息；有沒有想過假如沒有學(xué)號(hào)的話，校長(zhǎng)想找一個(gè)學(xué)生就只能根據(jù)姓名去找，可是同名同姓的人這么多，想找到目標(biāo)學(xué)生不是一件容易的事。。。。。
ok，在這里哈希表可以看作是校長(zhǎng)手上的那個(gè)表（其實(shí)就是一個(gè)數(shù)組），我們根據(jù)我們要存的信息生成一個(gè)表中的位置的號(hào)碼（在這里這個(gè)號(hào)碼就是數(shù)組的下標(biāo)），根據(jù)這個(gè)號(hào)碼我們就知道該數(shù)據(jù)存在數(shù)組的哪個(gè)位置，然后將數(shù)據(jù)保存進(jìn)去就可以了；假如有個(gè)大小為20的數(shù)組，我要存“aaa”,我們可以想個(gè)很厲害的辦法將這個(gè)字符串變成一個(gè)比較小的數(shù)字，比如是10，那么就把這個(gè)字符串存到數(shù)組的第10個(gè)位置，這樣做的好處就是下次如果要從哈希表中查詢（或刪除）“aaa”這個(gè)字符串時(shí)，只需要將“aaa”字符串算出那個(gè)號(hào)碼10，然后直接去數(shù)組中第10個(gè)位置找一個(gè)看有沒有這個(gè)字符串，是不是很簡(jiǎn)單?。?/p>
所以現(xiàn)在我們需要解決的就是想個(gè)很厲害的辦法可以將字符串變成一個(gè)比較小的數(shù)字（這個(gè)過程叫做哈?；?，還要保證這個(gè)數(shù)字不能超過數(shù)組的較大邊界！
2 哈?；?/strong>
哈?；褪窍朕k法將我們要保存的數(shù)據(jù)對(duì)應(yīng)一個(gè)數(shù)組下標(biāo)，在數(shù)組的該位置下保存數(shù)據(jù)；我們可以把這個(gè)過程專業(yè)一點(diǎn)的說一下：把要保存的數(shù)據(jù)，通過哈希函數(shù)轉(zhuǎn)化為對(duì)應(yīng)的數(shù)組下標(biāo)；現(xiàn)在我們的目標(biāo)就是怎么編寫一個(gè)哈希函數(shù)可以使得字符串變成數(shù)組下標(biāo)；
這里我們可以假設(shè)一個(gè)字符串t數(shù)組的大小為30，String[] str = new String[30]; 要存“cats”這個(gè)單詞，最容易想到的辦法就是用ASCII碼，但是由于ASCII碼太多了不好記，于是我們可以自己設(shè)置一套規(guī)則，我就假設(shè)a到z分別對(duì)應(yīng)1到26，外加空格對(duì)應(yīng)0，現(xiàn)在一套最簡(jiǎn)陋的規(guī)則就出來了,我那么“cats”這個(gè)單詞：c = 3,a = 1,t = 20,s = 19，現(xiàn)在“cats”有兩種辦法變成數(shù)組的下標(biāo)；
額外補(bǔ)充一下：假如我們要保存的字符串有50個(gè)，那么我們new的數(shù)組大小一定要是它的兩倍大，即new String[100];，后面會(huì)說到這個(gè)原因
2.1哈希函數(shù)實(shí)現(xiàn)一
怎么實(shí)現(xiàn)比較好呢？別想那么多，直接相加就好，3+1+20+19 = 43，這個(gè)時(shí)候就有個(gè)小問題，我們的數(shù)組的大小為30，也就是說數(shù)組下標(biāo)較大值是29，而這里我們的數(shù)字為43，怎么將43變成29以內(nèi)的數(shù)（包括29）呢？因?yàn)槿魏螖?shù)除以30的余數(shù)只都在0-29之間，于是我們用43除以30拿到余數(shù)13，那么我們就把”cats“放到數(shù)組下標(biāo)為13的位置,str[13] = "cats";
這種哈希函數(shù)的實(shí)現(xiàn)很容易，但是往往越容易的東西缺點(diǎn)就越大，較大的缺陷就是有很多單詞變成數(shù)字是相同的，比如was，tin，give等100多個(gè)單詞變成數(shù)字后都是43，然后我們恰巧添加單詞的時(shí)候就是這些單詞，現(xiàn)在問題來了，多個(gè)單詞最后算出來的數(shù)組下標(biāo)很大概率上是一樣的，也就是數(shù)組一個(gè)位置要放多個(gè)數(shù)據(jù)，怎么解決這個(gè)問題呢？我們可以換一種哈希函數(shù)的實(shí)現(xiàn)來降低這個(gè)概率
2.2 哈希函數(shù)實(shí)現(xiàn)二
由2.1可以知道太多的單詞變成數(shù)字的結(jié)果是一樣的，那么我們就要想辦法為每一個(gè)單詞都對(duì)應(yīng)一個(gè)獨(dú)一無二的整數(shù)，然后用這個(gè)整數(shù)除以數(shù)組的大小取余數(shù)，就可以知道該單詞在數(shù)組中的存放位置；
于是啊，我們可以利用冪的連乘來得到這個(gè)獨(dú)一無二的整數(shù)，比如“cats”用這種計(jì)算方法：3*273+1*272+20*271+19*270，有點(diǎn)類似二進(jìn)制變成十進(jìn)制，通過這個(gè)算法，可以得到一個(gè)獨(dú)一無二的整數(shù)，其他的任何單詞通過這種方法算出來的結(jié)果幾乎是不可能相等的，有興趣的可以試試；然后將這個(gè)計(jì)算結(jié)果除以30取余數(shù)，就可以得到一個(gè)數(shù)組的位置，然后將該字符串丟到里面即可；
不知道大家有沒有發(fā)現(xiàn)這種方法的一個(gè)問題，因?yàn)閿?shù)組的大小是一定的，而且我們是通過取余數(shù)來得到數(shù)組的位置，那么問題來了，即使是兩個(gè)不相同的整數(shù)分別除以30，最后的余數(shù)是相等的；
就比如有兩個(gè)字符串通過冪的連乘最后得到32和62（當(dāng)然我們這里肯定不會(huì)得到這兩個(gè)整數(shù)，為了好理解隨便拿兩個(gè)數(shù)），雖然這兩個(gè)數(shù)是獨(dú)一無二的，但是除以30余數(shù)都為2，那么兩個(gè)數(shù)據(jù)要保存到哈希表中肯定會(huì)有沖突，下后面我們來解決一下這個(gè)沖突；
有個(gè)簡(jiǎn)單的哈希函數(shù)實(shí)現(xiàn)看一下（雖然還可以進(jìn)行修改一下，但是這個(gè)已經(jīng)差不多了）；
3.沖突
沖突的原因就是兩個(gè)獨(dú)一無二的整數(shù)除以數(shù)組的大小，取余數(shù)是相等的，而數(shù)組中一個(gè)位置只能存一個(gè)數(shù)據(jù)，這就導(dǎo)致了沖突，解決沖突的辦法有兩種；
3.1 解決方法一（開放地址法）
還記得前面說過數(shù)組的大小要為實(shí)際數(shù)量的兩倍嗎？就是為了這個(gè)時(shí)候用的，假如一個(gè)單詞已經(jīng)放在了數(shù)組的第15個(gè)位置那里，另外一個(gè)單詞本來也要放在第15的位置，由于這個(gè)位置已經(jīng)被別人占了。那就放在數(shù)組的另外一個(gè)位置上，反正還有很多數(shù)組比較大，這種方式叫做------開放地址法
3.2 解決方法二（鏈地址法）
既然有兩個(gè)數(shù)據(jù)都要放在數(shù)組的一個(gè)位置上，那就想辦法把第二個(gè)數(shù)據(jù)連在第一個(gè)數(shù)據(jù)后面，通過第一個(gè)數(shù)據(jù)可以找到第二個(gè)數(shù)據(jù)，而數(shù)組中只保存第一個(gè)數(shù)據(jù)的地址；其實(shí)就是一句話，數(shù)組中每個(gè)位置放一個(gè)鏈表；
這種方法的好處很明顯，完美解決上述沖突，不需要用什么花里胡哨的操作；缺陷就是當(dāng)鏈表太長(zhǎng)了，我們要查詢這個(gè)鏈表的最后面的數(shù)據(jù)，只能慢慢遍歷這個(gè)鏈表，而我們知道，鏈表的優(yōu)勢(shì)是插入和刪除，而對(duì)于查詢這種操作是比較坑爹的，而我們前面用了紅黑樹這樣的結(jié)構(gòu)來完美解決鏈表的缺點(diǎn)；最后，我們就差不多想到了一個(gè)比較實(shí)用的方法：數(shù)組的每個(gè)位置都存放一個(gè)鏈表，當(dāng)鏈表的節(jié)點(diǎn)很少的時(shí)候，那就用鏈表吧！但是當(dāng)鏈表慢慢的變長(zhǎng)，當(dāng)節(jié)點(diǎn)數(shù)目到達(dá)一個(gè)界限的時(shí)候，我們就把這個(gè)鏈表變成一個(gè)紅黑樹，比較完美的方案，這也叫做------鏈地址法
順便一提，jdk7的HashMap就是數(shù)組中放鏈表，即使鏈表很長(zhǎng)也不會(huì)變紅黑樹；jdk8中的HashMap才增加了變紅黑樹這個(gè)操作
4.開放地址法
所謂的開放地址法就是：根據(jù)我們要保存的數(shù)據(jù)計(jì)算出來的數(shù)組下標(biāo)的那個(gè)位置已經(jīng)存放了數(shù)據(jù)，這個(gè)時(shí)候我們就要再找一個(gè)空位置，然后將要保存的數(shù)據(jù)丟進(jìn)去即可，那么怎么找比較好呢？這里提供三種方式，線性探測(cè)，二次探測(cè)和再哈希法，下面就看看這三種方式到底是怎么工作的；
4.1 線程探測(cè)
看名字線性就知道是從前往后尋找空的位置，舉個(gè)很簡(jiǎn)單的例子，當(dāng)一個(gè)字符串經(jīng)過運(yùn)算對(duì)應(yīng)于數(shù)組下標(biāo)為52，然而此時(shí)52這個(gè)位置上已經(jīng)有了數(shù)據(jù)，那么就嘗試放到53的位置，假如53的位置也已經(jīng)放了數(shù)據(jù)，那就放到54位置，就這樣一直往后慢慢找，直到找到一個(gè)空的位置就把數(shù)據(jù)放進(jìn)去；而此時(shí)找的次數(shù)越多，假如已經(jīng)找到56的位置，那么從53到56這么多位置叫做填充序列，當(dāng)填充序列很長(zhǎng)的時(shí)候，我們就稱為原始聚集，下圖所示：
這里填充序列的中有5個(gè)填充單元，我們也可以說步數(shù)為1，每次探測(cè)都是前進(jìn)一步；我們可以知道當(dāng)探測(cè)的次數(shù)越多的時(shí)候，說明聚集越嚴(yán)重，下一次再想添加到這個(gè)位置的數(shù)據(jù)的效率就越低；
還有就是當(dāng)哈希表填充得越滿，效率也就越低，所以當(dāng)哈希表快滿了之后就要擴(kuò)展，而java中數(shù)組是不能直接進(jìn)行擴(kuò)展的，需要再新建一個(gè)數(shù)組，然后想辦法將這個(gè)哈希表中的數(shù)據(jù)復(fù)制到新的數(shù)組中，注意，這里不能直接復(fù)制，因?yàn)樾碌臄?shù)組的容量和原來的數(shù)組不一樣，那么原來哈希表中所有的數(shù)據(jù)必須要重新哈?；缓蠓湃氲叫碌臄?shù)組中，非常耗時(shí)....
4.2 二次探測(cè)
根據(jù)前面我們的線性探測(cè)可以知道，假如經(jīng)過哈希函數(shù)計(jì)算出來的原始數(shù)組下標(biāo)為x，那么線性探測(cè)的位置是x+1，x+2，x+3，x+4.....,；那么 進(jìn)行二次探測(cè)找的位置就是x+12，x+22，x+32，x+42.....其實(shí)就是按照步數(shù)的平方進(jìn)行探測(cè)看里面有沒有數(shù)據(jù)，沒有的話才放進(jìn)去新的數(shù)據(jù)，二次探測(cè)可以防止聚集太長(zhǎng)所導(dǎo)致的效率下降問題；
對(duì)于二次探測(cè)來說，如果當(dāng)前計(jì)算出來的位置為x，首先會(huì)探測(cè)x后面一個(gè)位置，如果這個(gè)位置有數(shù)據(jù)，那就多往后4個(gè)位置看有沒有數(shù)據(jù)，假如還是有數(shù)據(jù)，那么二次探測(cè)可能會(huì)覺得你這個(gè)聚集特別長(zhǎng)，于是這次跳得更遠(yuǎn)的位置，當(dāng)前位置后面的16的位置等等，直到最后跳過整個(gè)數(shù)組， 這樣可以避免一個(gè)一個(gè)的位置慢慢探測(cè)的底下效率，二次探測(cè)下圖所示：
二次探測(cè)也有點(diǎn)問題，會(huì)導(dǎo)致二次聚集，那什么又是二次聚集呢？其實(shí)跟原始聚集差不多吧！比如184，302，420，544這幾個(gè)整數(shù)都要放到哈希表中，而且這幾個(gè)數(shù)經(jīng)過哈希算法算出來的數(shù)組下標(biāo)都為7，302需要以1步長(zhǎng)進(jìn)行探測(cè)，而420要先以1為步長(zhǎng)，然后以4步長(zhǎng)進(jìn)行探測(cè)，而544要先以1為步長(zhǎng)，然后以4為步長(zhǎng)，最后以16步長(zhǎng)進(jìn)行探測(cè)，假如后面還有數(shù)據(jù)對(duì)應(yīng)的數(shù)組下標(biāo)為7，那么還是要重復(fù)這個(gè)步驟，而且是越來越長(zhǎng)....這也是一種聚集，個(gè)人感覺從某種意義來說和原始聚集性質(zhì)差不多吧！
二次探測(cè)不常用，因?yàn)橛懈玫霓k法解決，就是再哈希法；
4.3 再哈希法
用再哈希法可以消除原始聚集和二次聚集，那么什么是再哈希法呢？我們可以知道產(chǎn)生原始聚集和二次聚集的原因其實(shí)差不多，都是由于多個(gè)數(shù)據(jù)添加到哈希表中的同一個(gè)位置，然后根據(jù)步長(zhǎng)一個(gè)一個(gè)位置的探測(cè)，直到找到一個(gè)空的位置，如果需要找的位置特別多，那么這就是聚集，添加的效率的就會(huì)大幅度降低；
那么我們就要想一種方法即使多個(gè)數(shù)據(jù)要放在哈希表的同一個(gè)位置，但是不需要從頭開始一個(gè)一個(gè)位置的探測(cè)，如果每個(gè)數(shù)據(jù)都可以產(chǎn)生一個(gè)獨(dú)一無二的步長(zhǎng)那不就好了么！然后直接根據(jù)這個(gè)步長(zhǎng)探測(cè)該位置將數(shù)據(jù)丟進(jìn)去就ok了；
于是我們準(zhǔn)備了兩個(gè)哈希函數(shù)，一個(gè)哈希函數(shù)就是我們上面說到的可以產(chǎn)生對(duì)應(yīng)的數(shù)組下標(biāo)，另外一個(gè)哈希函數(shù)可以產(chǎn)生步長(zhǎng)，其實(shí)就是多個(gè)數(shù)據(jù)放在同一個(gè)位置產(chǎn)發(fā)生沖突，就用這個(gè)哈希函數(shù)再次哈?；a(chǎn)生一個(gè)步長(zhǎng)，根據(jù)這個(gè)步長(zhǎng)進(jìn)行探測(cè)就可以了，而不用每次都從第一個(gè)步長(zhǎng)開始；比如下面就有一個(gè)產(chǎn)生步長(zhǎng)的哈希函數(shù)，我們可以知道步長(zhǎng)的范圍是1-constant，注意步長(zhǎng)不能為0，否則就原地踏步了。。。
上圖中，假如我們往哈希表中添加的數(shù)據(jù)是數(shù)字，那就直接將數(shù)據(jù)和數(shù)組大小取余得到數(shù)組下標(biāo)，這里的key就是我們的數(shù)據(jù)，constant只要是小于數(shù)組容量的一個(gè)質(zhì)數(shù)，隨便什么都可以
順便一提：再哈希法使用的前提必須保證數(shù)組的容量為一個(gè)質(zhì)數(shù)，因?yàn)檫@樣才能使得所有位置都被探測(cè)到；可以試試假如數(shù)組容量為15，步長(zhǎng)為5，一個(gè)數(shù)據(jù)經(jīng)過計(jì)算得到額數(shù)組下標(biāo)為0，那么探測(cè)的位置應(yīng)該為：（0+5）%15 = 5,、（5+5）%15 = 10，（10+5）%15 = 0，只會(huì)探測(cè)0、5、10這三個(gè)位置；但是如果數(shù)組容量為質(zhì)數(shù)13，步長(zhǎng)為5，第一個(gè)數(shù)據(jù)下標(biāo)還是0，那么探測(cè)位置為：（0+5）%13 = 5,、（5+5）%13 = 10，（10+5）%13 = 2、（2+5）%13 = 7，（7+5）%13 = 12，（12+5）%13 = 4，（4+5）%13 = 9等等，可以看到每次探測(cè)的位置都不一樣，可以探測(cè)到數(shù)組中所有位置只要有空的就把數(shù)據(jù)當(dāng)進(jìn)去即可；
假如使用的是開放地址法，那么探測(cè)序列就用這個(gè)再哈希法生成，其實(shí)很容易！
5.鏈地址法
可以看到上面的開放地址法有點(diǎn)麻煩，需要找到探測(cè)序列真的是日了狗了，麻煩的我都不想看了，如果可以不用這么麻煩那該多好呀，ok，那就用鏈地址法吧！就類似下面這樣的結(jié)構(gòu)，原始的數(shù)組中不直接保存數(shù)據(jù)，每個(gè)位置只是保存第一個(gè)數(shù)據(jù)的引用，通過該位置第一個(gè)引用就可以取到后面所有的數(shù)據(jù)！如果鏈表太長(zhǎng)遍歷起來就比較費(fèi)勁，可以轉(zhuǎn)為紅黑樹效率就高了很多；
這里其實(shí)沒什么好說的，因?yàn)閿?shù)組和鏈表的使用很熟悉了，沒什么特別難的東西，基本邏輯：只需要新建一個(gè)MyHashTable的類，這個(gè)類中有幾個(gè)屬性：一個(gè)數(shù)組，一個(gè)int類型的屬性標(biāo)識(shí)數(shù)組真實(shí)容量的大??；好有個(gè)節(jié)點(diǎn)類為靜態(tài)內(nèi)部類，這個(gè)靜態(tài)內(nèi)部類中實(shí)現(xiàn)了對(duì)鏈表的增刪改查的操作；然后在MyHashTable類中寫一個(gè)哈希函數(shù)的方法，根據(jù)這個(gè)哈希函數(shù)得出來的數(shù)組下標(biāo)，最后對(duì)數(shù)組的增刪改查了！
到此，關(guān)于“java數(shù)據(jù)結(jié)構(gòu)和算法中哈希表知識(shí)點(diǎn)有哪些”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！
重慶分公司
重慶分公司
