java中的散列表是什么

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

創(chuàng)新互聯(lián)建站是一家專注于成都做網(wǎng)站、成都網(wǎng)站建設(shè)與策劃設(shè)計(jì),疏勒網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)建站做網(wǎng)站,專注于網(wǎng)站建設(shè)十余年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:疏勒等地區(qū)。疏勒做網(wǎng)站價(jià)格咨詢:18980820575

什么是散列表

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

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

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

公式如下：

index = HashCode(key) % Array.length

舉個(gè)例子：

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

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

散列表的讀寫操作

1.寫操作

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

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

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

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

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

2.讀操作

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

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

例如，我們要查找Key為002936所對(duì)應(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ù)組的最大長(zhǎng)度時(shí)需要對(duì)數(shù)組擴(kuò)容，那么散列表什么時(shí)候擴(kuò)容呢？

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

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

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

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

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

HashMap.Size >= Capacity X LoadFactor

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

擴(kuò)容的步驟：

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

1.擴(kuò)容，創(chuàng)建一個(gè)新的Entry空數(shù)組，長(zhǎng)度時(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會(huì)把Entry的鏈表轉(zhuǎn)化為紅黑樹這種數(shù)據(jù)結(jié)構(gòu)。

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

網(wǎng)頁(yè)標(biāo)題：java中的散列表是什么
轉(zhuǎn)載注明：http://www.muchs.cn/article36/jpcosg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、用戶體驗(yàn)、網(wǎng)站排名、全網(wǎng)營(yíng)銷推廣、營(yíng)銷型網(wǎng)站建設(shè)、搜索引擎優(yōu)化

廣告

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