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

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

什么是散列表

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

散列表的工作原理

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

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

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

公式如下：

index = HashCode(key) % Array.length

舉個例子：

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

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

散列表的讀寫操作

1.寫操作

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

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

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

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

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

2.讀操作

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

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

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

3.擴容

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

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

影響散列表擴容的因素為：

Capacity，即HashMap的當前長度

LoadFactor，即HashMap的負載因子，默認值為0.75

擴容需要滿足的條件：

HashMap.Size >= Capacity X LoadFactor

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

擴容的步驟：

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

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

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

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

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

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

網(wǎng)頁標題：java中的散列表是什么-創(chuàng)新互聯(lián)
URL標題：http://weahome.cn/article/dcepec.html