java中的散列表是什么

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

什么是散列表

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

散列表的工作原理

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

不同的語言中，哈希函數的實現方式是不同的。Java中使用的是HashMap。

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

公式如下：

index = HashCode(key) % Array.length

舉個例子：

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

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

散列表的讀寫操作

1.寫操作

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

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

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

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

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

2.讀操作

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

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

例如，我們要查找Key為002936所對應的value時，先將Key轉化為數組下標，得到下標為2，檢查該元素，發現該元素的Key為002947，不是我們要查詢的Key，那么繼續沿著鏈表往下查找。

3.擴容

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

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

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

Capacity，即HashMap的當前長度

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

擴容需要滿足的條件：

HashMap.Size >= Capacity X LoadFactor

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

擴容的步驟：

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

1.擴容，創建一個新的Entry空數組，長度時原數組的2倍；

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

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

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