之前已經介紹過Java的另1個容器HashSet.? 其實HashMap的存儲原來跟HashSet區別不大, 可以說是HashSet的1個擴展.

一,預備知識: 哈希表

我們可以把哈希表看做是1個特別的容器.

1.1 哈希表的定義

對于1個一般的容器, 無論是List, Queue, 或者Tree, 如果要放入1個新元素(數據), 一般就會放在上1個元素的后1個位置.

也就是說元素在容器的位置跟這個元素本身是無關的.

這些容器實現起來很簡單, 但是在容器里查找1個元素, 往往需要遍歷容器中的每個位置, 值到找到這個元素.

如果容器的元素足夠多, 查找1個元素往往就是1個很耗費成本的行為.

哈希表(Hash Table) 也叫散列表. 如果要放入1個元素, 哈希表會根據這個元素計算出對應的位置. 然后把這個元素放到那個位置中.

如果要查找1個元素, 也是根據這個元素計算出(也可以叫映射)對應的位置, 就直接找到了, 不須遍歷容器.

也就是說哈希表內的元素的存放位置是由元素本身決定的.

上面的定義只是哈希表的簡單概念. 人類還沒設計出1個完美的哈希表.

1.2 哈希表的優勢

根據定義我們就可以看出, 元素的檢索速度, 也就是查找性能是哈希表的優勢了.

因為哈希表能直接計算出1個元素的位置,? 而不需要逐個位置地遍歷容器.

1.3 哈希表的實現

問題是在編程中如何實現1個哈希表?

首先, 我們需要存放的一個元素提供1個鍵值(Key),? 而且要求兩個元素不能具有1個相同的key.

然后哈希表回用1個算法(哈希算法) 根據key計算出1個位置(index).

然后把這個元素放到那個位置中, 如果那個位置已經存在其他元素, 則會被覆蓋.

而查找1個元素, 也要這個元素提供一個key, 然后根據哈希算法. 算出這個元素應該放的位置, 然后直接去那個位置訪問這個元素.

1.4 哈希算法

根據1.3就可以得知, 所謂哈希算法就是根據1個key計算出的元素(value)在哈希表的位置的算法.

不同的哈希表很可能有不同的哈希算法.

哈希算法的實現并不簡單, 這個算法的實現要考慮如下幾點:

1.計算出的結果(元素存放位置)必須在1個范圍之內(容器所占的內存范圍), 否則 導致超界.

2.根據不同的key(參數)保證得出不同的結果(return value). 這個優先級別比第一點要低.

所以哈希算法的實現是1個相當復雜的行為, 所幸在java中hash容器已經幫我們寫好封裝好了.

1.5 哈希沖突.

一旦哈希算法根據多個不同的key, 返回同1個位置. 這就是哈希沖突了.

有人說這是哈希算法的問題?? 實際上因為哈希表的容量和范圍所限,幾乎所有哈希算法都不能避免哈希沖突.

只能減少哈希沖突發生的幾率.

哈希沖突不能避免, 但是能夠解決.

加入有2個元素, 它們的key都被映射到相同1個位置, 為了避免其中1個元素覆蓋掉另1個元素.

我們可以讓那個位置不放置任何元素, 而是放置1個子鏈表的頭部地址, 然后把那兩個元素放入到那個子鏈表中.

如下圖:

上圖每1個子鏈表里的對象的key都不同, 但是它們的key都映射到同1個位置(哈希沖突).

帶來的缺點就是查找發生哈希沖突的元素還是需要在子鏈表中遍歷.

1.6 哈希因子

假如1個哈希表容器的所占內存(初始容量)是10個單位, 而我們要存放10個元素.

幾乎沒有哈希算法能根據這個10個元素的key分別指向這個容器的10個不同位置.

只能保證映射的位置在這個哈希表的范圍之內. 所以哈希沖突就很可能發生了.

為了盡量減少哈希沖突的幾率. 往往我們需要擴大哈希表的容量.

例如我們安排1個具有100個容量單位的哈希表去存放10個元素.? 哈希沖突的幾率就大大減少了.

假如我們安排1個安排10000個容量單位的哈希表區存放10個元素, 就幾乎不存在哈希沖突了. 哈希算法的實現也容易得多.

所以我們把哈希表需要存放的元素個數, 和哈希表所占內存的單位個數的比成為哈希因子.

哈希因子在0與1之間.

如果哈希因子很小, 則代表哈希沖突幾率小, 但是很耗費內存空間(很多位置不存放數據)

相反, 如果哈希因子接近1, 則代表哈希沖突的幾率很大.

1.7 哈希表的缺點

哈希表性能優點在1.2時提到過了, 缺點也很明顯, 就是我們為了避免哈希沖突, 往往需要比實際存放的數據更大的空間.

1.8 哈希表小結

1.哈希表會根據數據的主鍵(key)算出數據的存放位置.

2.哈希表主要為了提高數據的存儲速度而設計的.

3.哈希表是人類的一種追求, 人類很難設計出完美的哈希表.

4.幾乎所有哈希表都回產生哈希沖突.

5.哈希沖突是可以解決的.

二,Map接口

我們常常見到在Java中見到HashMap這個容器, 往往有人叫它做哈希圖.

實際在編程中, Map不是圖的意思, 而是映射.

所以HashMap的中文翻譯本屌覺得更應該是"哈希映射".? 但是一般叫它左哈希表就ok了.

HashMap和HashTable都實現了Map接口.

又上面架構圖得知, Map也是1個接口, 但是這個接口沒有繼承自Collection接口.

因為Map接口不只是存放數據的本身(value), 還需要存放數據提供的主鍵(Key).

這種key 和 value的組后就是所謂的鍵值對(Key-Value), 而Map接口就是為了實現存放鍵值對的容器而設計的.

定義如下:

Map保存所謂的'鍵值對'(Key - Value)信息, 映射中不能出現重復的鍵(key), 每個鍵最多只能映射一個值.

三,HashMap 和 HashTable簡介.

實際上HashMap和HashTable都繼承了Map接口. 兩者都可以被成為"哈希表"

兩者的用法是基本上一樣的, 只不過HashTable里面的方法是同步的(類似于Vector和ArrayList的區別), 而且HashTable不能存放NULL元素.

3.1 HashSet的內存存儲機制

提到HashMap 不得不提HashSet啊

HashSet可以講也體現了哈希表的原理.

HashSet是根據元素對象的.hashCode()來作為Key值的.

而是根據equals()方法來比較兩個重復的元素. 避免哈希沖突.

如下圖:

所以放入HashSet的對象必須重寫hashCode() 和 equals()方法.

關于HashSet的內存存儲機制.

請參考之前的博文,

http://blog.csdn.net/nvd11/article/details/27716511

3.1 HashMap的內存存儲機制

HashMap的內存機制其實跟HashSet很類似, 可以說HashMap是HashSet的一個擴展.

HashSet: 存儲數據本身, 以數據的hashCode()作為Key

HashCode:. 要求數據提供額外的對象作為Key,? 先存儲Key. 然后再存儲對象, 就是存儲(key-value)了.

也就是說 HashCode本身包含1個只存放key對象的1個HashSet, 這個HashSet內的每個Key再指向1個Value.

我們可以看出.

HashMap是以Key對象的hashCode()來計算存儲位置,? 以key對象的equals()方法來解決哈希沖突.

所以, 對于HashMap, 數據對象提供的key對象必須重寫hashCode()和 equals()方法.

建議利用int變量作為key, 因為int變量會被自動裝箱成interger變量. 而integer類是已經被重寫hashCode()和equals()方法的.

3.1 HashMap的常用方法.

3.1.1 Object put(Object key, Object value)

Map容器是沒有add方法, 相應地提供了put方法來將1個對象放入容器.

1.put方法根據key對象的hashCode()方法計算出存儲位置, 如果該位置已有元素, 則覆蓋它.

2.而且返回被覆蓋的元素對象, 如果之前的位置為空,則返回NULL.

值得記住的就是這個方法的參數, key在前 value在后面.

3.1.2 Object put ALL(Map m)

把Map容器m的所有元素加入到當前容器中, 這個方法可能會覆蓋多個已有元素.

3.1.3 Object get(Object key)

根據提供的key對象返回要獲取的數據對象.? 如果容器不存在key對應的對象, 則返回NULL..

get()方法和Put()方法是最常用的方法.

3.1.4 int size();

當前容器元素個數.

3.1.5 boolean containsKey(Object key);

判斷Map容器內是否存在key對象key.?

3.1.6 boolean containsValue(Object value);

判斷Map容器內是否存在對象value. 注意這個方法沒有提供key, 所以會導致遍歷容器, 不建議使用.

3.1.7 Object remove(Object key);

根據提供的key對象在容器中移除對應的鍵值對, 而且返回被移除的元素對象.

3.1.8 void clear()

清空容器..

3.2 HashMap的遍歷, keySet()方法介紹.

如果想遍歷HashMap容器的所有元素, 利用循環不不可行的.

但是HashMap提供了1個方法keySet()

它返回1個Set(注意不是HashSet), 里面包含了所有key對象的集合.

然后我們利用interator()方法遍歷keySet()中的每個key對象, 則可以遍歷每個對應的元素對象了.

例子:

import java.util.HashMap; import java.util.Set; import java.util.Iterator;class Student{int id;private String name;public Student(int id, String name){this.id = id;this.name = name;}public String toString(){return this.id + ": " + this.name;} }public class HashMap1{public static void f(){HashMap hm = new HashMap();Student st = new Student(1,"Jack");hm.put(st.id, st);st = new Student(2,"Bill");hm.put(st.id, st);st = new Student(3,"Carlos");hm.put(st.id, st);st = new Student(4,"Alice");hm.put(st.id, st);System.out.println(hm.get(4));//get the HashSet of keysSet keyset = hm.keySet();Iterator it = keyset.iterator();while(it.hasNext()){st = (Student)hm.get(it.next()); System.out.println(st);}} }

輸出:

[java] 4: Alice[java] 1: Jack[java] 2: Bill[java] 3: Carlos[java] 4: Alice

總結

以上是生活随笔為你收集整理的Java 里的HashMap(HashTable) 简介.的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。