java中關於散列表的詳細介紹

什麼是散列表

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

線上學習影片推薦：java影片

#散列表的工作原理

#散列表在本質上是一個陣列。我們知道數組可以根據下標來進行隨機訪問，如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语言入门

以上是java中關於散列表的詳細介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！