這篇文章將為大家詳細(xì)講解有關(guān)java中的散列表，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括清江浦網(wǎng)站建設(shè)、清江浦網(wǎng)站制作、清江浦網(wǎng)頁制作以及清江浦網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，清江浦網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到清江浦省份的部分城市，未來相信會繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

什么是散列表

散列表，也叫作哈希表（Hash Table），是一種提供鍵（Key）和值（Value）的映射關(guān)系的數(shù)據(jù)結(jié)構(gòu)，只要給出一個(gè)Key，就可以高效查找到它所匹配的Value，時(shí)間復(fù)雜度接近于O(1)。

散列表的工作原理

散列表在本質(zhì)上是一個(gè)數(shù)組。我們知道數(shù)組可以根據(jù)下標(biāo)來進(jìn)行隨機(jī)訪問，如a[0], a[1], a[2], a[3], a[4]，通過這樣來訪問，因此其查詢效率非常高。而在散列表中，當(dāng)我們給出一個(gè)key的時(shí)候，也能立即查詢到對應(yīng)的value。這時(shí)我們就需要一個(gè)“中轉(zhuǎn)站”，通過某種方式，把Key和數(shù)組下標(biāo)進(jìn)行轉(zhuǎn)換，而這個(gè)中轉(zhuǎn)站就是哈希函數(shù)。

不同的語言中，哈希函數(shù)的實(shí)現(xiàn)方式是不同的。Java中使用的是HashMap。

在Java及大多數(shù)的面向?qū)ο蟮恼Z言中，每個(gè)對象都有屬于自己的hashcode，用以區(qū)分不同的對象，而這個(gè)hashcode是一個(gè)整形變量。此時(shí)我們就需要將這個(gè)整形變量轉(zhuǎn)化成數(shù)組的下標(biāo)，最簡單的轉(zhuǎn)化方式是對數(shù)組長度進(jìn)行取模。

公式如下：

index = HashCode(key) % Array.length

舉個(gè)例子：

給出一個(gè)長度為8的數(shù)組，我們要查找key為"001121"所對應(yīng)的Vaule，而"001121"的hashcode為1420036703，那么就可通過下面的計(jì)算先得到數(shù)組下標(biāo)：

index = HashCode("001121")%Array.length = 1420036703 % 8 = 7

散列表的讀寫操作

1.寫操作

寫操作就是在散列表中插入新的鍵值對（jdk中叫做Entry）。

具體的做法是：通過哈希函數(shù)將key值轉(zhuǎn)化為數(shù)組下標(biāo)，然后在數(shù)組的該位置處插入Entry（注意是Entry鍵值對Key+Value，而不僅僅是Value）?？上攵煌膋ey值可能會轉(zhuǎn)化為相同的下標(biāo)，那么此時(shí)就成為哈希沖突。

解決哈希沖突常用的方法是開放尋址法和鏈表法。

開放尋址法的基本思路是：當(dāng)發(fā)生哈希沖突時(shí)，就把Entry放到下一個(gè)數(shù)組中為空的位置，也就是逐個(gè)往后移動。

鏈表法（應(yīng)用在Java的HashMap集合類中）的基本思想是：數(shù)組中的每個(gè)元素不僅是一個(gè)Entry對象，同時(shí)也是一個(gè)鏈表的頭節(jié)點(diǎn)。每個(gè)Entry對象通過next指針指向它的下一個(gè)Entry節(jié)點(diǎn)。當(dāng)新來的Entry對象映射到與之沖突的數(shù)組位置時(shí)，只需要插入到對應(yīng)的鏈表中即可。

2.讀操作

讀操作與寫操作對應(yīng) ，只需特別處理沖突情況即可。

具體的思路為：通過哈希函數(shù)，將待查找的Key值轉(zhuǎn)化為數(shù)組下標(biāo)，然后檢查數(shù)組中該位置的Key值是否為我們要找的Key，若是，則找到，可以返回該Entry的Value值；否則，沿著鏈表繼續(xù)往下查找，看有沒有對應(yīng)的Key值。

例如，我們要查找Key為002936所對應(yīng)的value時(shí)，先將Key轉(zhuǎn)化為數(shù)組下標(biāo)，得到下標(biāo)為2，檢查該元素，發(fā)現(xiàn)該元素的Key為002947，不是我們要查詢的Key，那么繼續(xù)沿著鏈表往下查找。

3.擴(kuò)容

我們知道數(shù)組擴(kuò)容，是當(dāng)數(shù)組中的元素個(gè)數(shù)達(dá)到數(shù)組的大長度時(shí)需要對數(shù)組擴(kuò)容，那么散列表什么時(shí)候擴(kuò)容呢？

當(dāng)經(jīng)過多次元素插入，散列表達(dá)到一定的飽和度時(shí)，發(fā)生哈希沖突的概率會變大，此時(shí)大量的元素?fù)頂D在相同的數(shù)組下標(biāo)位置，這對后序的插入和查詢操作的性能產(chǎn)生很大的影響，此時(shí)就需要對散列表擴(kuò)容。

影響散列表擴(kuò)容的因素為：

Capacity，即HashMap的當(dāng)前長度

LoadFactor，即HashMap的負(fù)載因子，默認(rèn)值為0.75

擴(kuò)容需要滿足的條件：

HashMap.Size >= Capacity X LoadFactor

簡單解釋為：當(dāng)哈希表中的條目數(shù)超出了當(dāng)前容量與其加載因子的乘積時(shí)，并且要存放的位置已經(jīng)有元素了（哈希碰撞），這兩個(gè)條件滿足時(shí)，需要進(jìn)項(xiàng)擴(kuò)容，會將容量擴(kuò)大為原來的兩倍。加載因子默認(rèn)值0.75，是在空間和時(shí)間上的一個(gè)折中，加載因子過高（發(fā)生沖突可多存放在鏈表），雖然減少了空間成本，但也增加了查詢成本。

擴(kuò)容的步驟：

擴(kuò)容不是簡單地把散列表的長度擴(kuò)大，而是經(jīng)歷了下面兩個(gè)步驟：

1.擴(kuò)容，創(chuàng)建一個(gè)新的Entry空數(shù)組，長度時(shí)原數(shù)組的2倍；

2.重新Hash，遍歷原Entry數(shù)組，所有的Entry重新Hash到新數(shù)組中。

經(jīng)過擴(kuò)容，原本擁擠的散列表重新變得稀疏，原有的Entry也重新得到了盡可能均勻的分配。需要注意的是，關(guān)于HashMap的實(shí)現(xiàn)，JDK8和以前的版本有著很大的不同。當(dāng)多個(gè)Entry被Hash到同一個(gè)數(shù)組下標(biāo)位置時(shí)，為了提高插入和查找的效率，HashMap會把Entry的鏈表轉(zhuǎn)化為紅黑樹這種數(shù)據(jù)結(jié)構(gòu)。

關(guān)于java中的散列表就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

當(dāng)前標(biāo)題：java中的散列表是什么-創(chuàng)新互聯(lián)
標(biāo)題URL：http://www.rwnh.cn/article42/dcepec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、做網(wǎng)站、定制網(wǎng)站、定制開發(fā)、微信小程序、商城網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)