哈希表也稱為散列表，是用來存儲群體對象的集合類結(jié)構(gòu)。
什么是哈希表
數(shù)組和向量都可以存儲對象，但對象的存儲位置是隨機(jī)的，也就是說對象本身與其存儲位置之間沒有必然的聯(lián)系。當(dāng)要查找一個對象時，只能以某種順序（如順序查找或二分查找）與各個元素進(jìn)行比較，當(dāng)數(shù)組或向量中的元素數(shù)量很多時，查找的效率會明顯的降低。
一種有效的存儲方式，是不與其他元素進(jìn)行比較，一次存取便能得到所需要的記錄。這就需要在對象的存儲位置和對象的關(guān)鍵屬性（設(shè)為 k）之間建立一個特定的對應(yīng)關(guān)系（設(shè)為 f），使每個對象與一個唯一的存儲位置相對應(yīng)。在查找時，只要根據(jù)待查對象的關(guān)鍵屬性 k 計算f(k)的值即可。如果此對象在集合中，則必定在存儲位置 f(k)上，因此不需要與集合中的其他元素進(jìn)行比較。稱這種對應(yīng)關(guān)系 f 為哈希（hash）方法，按照這種思想建立的表為哈希表。
Java 使用哈希表類（Hashtable）來實現(xiàn)哈希表，以下是與哈希表相關(guān)的一些概念：
•容量（Capacity）：Hashtable 的容量不是固定的，隨對象的加入其容量也可以自動增長。
•關(guān)鍵字（Key）：每個存儲的對象都需要有一個關(guān)鍵字，key 可以是對象本身，也可以是對象的一部分（如某個屬性）。要求在一個 Hashtable 中的所有關(guān)鍵字都是唯一的。
•哈希碼（Hash Code）：若要將對象存儲到 Hashtable 上，就需要將其關(guān)鍵字 key 映射到一個整型數(shù)據(jù)，成為 key 的哈希碼。
•項（Item）：Hashtable 中的每一項都有兩個域，分別是關(guān)鍵字域 key 和值域 value（存儲的對象）。Key 和 value 都可以是任意的 Object 類型的對象，但不能為空。
•裝填因子（Load Factor）：裝填因子表示為哈希表的裝滿程度，其值等于元素數(shù)比上哈希表的長度。
哈希表的使用
哈希表類主要有三種形式的構(gòu)造方法：
Hashtable(); //默認(rèn)構(gòu)造函數(shù)，初始容量為 101，最大填充因子 0.75
Hashtable(int capacity);
Hashtable(int capacity,float loadFactor)
哈希表類的主要方法如表 8-6 所示。
表 8-6 哈希表定義的常見方法
| 方法 | 功能 |
|---|---|
| void clear() | 重新設(shè)置并清空哈希表 |
| boolean contains(Object value) | 確定哈希表內(nèi)是否包含了給定的對象，若有返回 true，否則返回 false |
| boolean containsKey(Object key) | 確定哈希表內(nèi)是否包含了給定的關(guān)鍵字，若有返回 true，否則返回 false |
| boolean isEmpty() | 確認(rèn)哈希表是否為空，若是返回 true，否則返回 false |
| Object get(Object key) | 獲取對應(yīng)關(guān)鍵字的對象，若不存在返回 null |
| void rehash() | 再哈希，擴(kuò)充哈希表使之可以保存更多的元素，當(dāng)哈希表達(dá)到飽和時，系統(tǒng)自動調(diào)用此方法 |
| Object put(Object key,Object value) | 用給定的關(guān)鍵字把對象保存到哈希表中，此處的關(guān)鍵字和元素均不可為空 |
| Object remove(Object key) | 從哈希表中刪除與給定關(guān)鍵字相對應(yīng)的對象，若該對象不存在返回 null |
| int size() | 返回哈希表的大小 |
| String toString() | 將哈希表內(nèi)容轉(zhuǎn)換為字符串 |
哈希表的創(chuàng)建也可以通過 new 操作符實現(xiàn)。其語句為：
HashTable has=new HashTable();
例子：
【例 8-12】哈希表的遍歷。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
//********** ep8_12.java **********import java.util.*;class ep8_12{ public static void main(String args[]){ Hashtable has=new Hashtable(); has.put("one",new Integer(1)); has.put("two",new Integer(2)); has.put("three",new Integer(3)); has.put("four",new Double(12.3)); Set s=has.keySet(); for(Iterator<String> i=s.iterator();i.hasNext();){ System.out.println(has.get(i.next())); } }} |
運行結(jié)果：
|
1
2
3
4
|
21312.3 |
