Java采用Map和Hash Map實作哈希表以及對哈希表的了解

在實作快速查詢上，哈希表是經常使用的一種資料結構，是根據關鍵碼值(Key value)而直接進行通路的資料結構。也就是說，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散清單。(底層為資料和連結清單的結合體)

給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數後若能得到包含該關鍵字的記錄在表中的位址(HashCode)，則稱表M為哈希(Hash）表，函數f(key)為哈希(Hash) 函數。

Map和HashMap

Map<K, V>是一個以 鍵值(Key)-數值(Value) 對應形式存儲資料的接口。 在數組中我們是通過數組下标來對其内容索引的，而在Map中我們通過對象來對對象進行索引，用來索引的對象叫做key，其對應的對象叫做value。

實作首先要導入類：

import java.util.Map;
import java.util.HashMap;
           

Key定義為String，Value定義為Integer。

這樣就用接口實作了定義哈希表。但是哈希表内部又是如何實作成了一個問題，下面說一下對哈希表的了解。

哈希表

哈希表如何實作直接查找的呢，舉一個例子，假如我的數組A中，第i個元素裡面裝的key就是i，那麼數字3肯定是在第3個位置，數字10肯定是在第10個位置。哈希表就是利用這種基本的思想，建立一個從key到位置的函數，然後進行直接計算查找。而查找時使用的哈希值使用哈希(Hash)算法算出，Hash主要用于資訊安全領域中加密算法，它把一些不同長度的資訊轉化成雜亂的128位的編碼,這些編碼值叫做Hash值. 也可以說，Hash就是找到一種Key值和資料存放位址之間的映射關系。

整體方法就是将元素的特征變為數組的下标的方法，哈希表的每一個入口都由一個連結清單實作，在需要儲存全部的字元串當存儲記錄時，通過Hash計算出記錄的哈希值，當查找記錄時，我們通過同樣的是Hash計算記錄的哈希值，并按此哈希值通路該記錄。

雖然哈希表擁有近乎**O(1)**的時間複雜度但是，在存儲大量的資料時，由于數組存儲的限制會導緻性能快速下降，并且還會出現不同的關鍵字經過散列函數的計算得到了相同的散列位址(哈希沖突)。

哈希沖突

在解決哈希沖突方面有多種方法：

一、 開放定址法

一旦發生沖突，就去尋找新的空的位址或者找到了相同的給定關鍵字，若未找到，則會失敗。

二、雙哈希法

使用多個Hash算法，在發生沖突後，使用後面的第二個，第三個…直到無沖突。

三、 鍊位址法

每個哈希表節點都有一個next指針，多個哈希表節點可以用next指針構成一個單向連結清單，被配置設定到同一個索引上的多個節點可以用這個單向 連結清單連接配接起來。此時即使産生沖突，但是可以通道next指針将沖突所在所在的節點連接配接起來，這樣就解決了哈希的沖突問題。

四、 建立公共溢出區

即建立一個緩沖區，将沖突的放在緩沖區中，在查找不到時在緩沖區中查找。

哈希值

哈希值即通過Hash算法得到的哈希表的”位址值“，HashCode(哈希值)是所有Java對象的固有方法，如果不重載的話，傳回的實際上是該對象在jvm的堆上的記憶體位址，而不同對象的記憶體位址肯定不同，是以這個HashCode也就肯定不同了。如果重載了的話，由于采用的算法的問題，有可能導緻兩個不同對象的HashCode相同。對于string類，隻要字元串内容相同，傳回的哈希碼也相同。規範要求若重寫equals(Object obj)方法，有必要重寫hashcode()方法，確定通過equals(Object obj)方法判斷結果為true的兩個對象具備相等的hashcode()傳回值，這樣就确定了相同的值的對象的hashcode相同。但是，即使equals(Object obj)傳回false，即兩個對象不相同，也不要求調用hashcode()方法必須要得到兩個不同的數。

是以得到如下推論：

1、如果兩個對象equals，Java運作時環境會認為他們的hashcode一定相等。

2、如果兩個對象不equals，他們的hashcode有可能相等。

3、如果兩個對象hashcode相等，他們不一定equals。

4、如果兩個對象hashcode不相等，他們一定不equals。

引用連結：

哈希沖突

HashCode