哈希表也稱為散列表，是用來存儲群體對象的集合類結構。
什么是哈希表
數組和向量都可以存儲對象，但對象的存儲位置是隨機的，也就是說對象本身與其存儲位置之間沒有必然的聯系。當要查找一個對象時，只能以某種順序（如順序查找或二分查找）與各個元素進行比較，當數組或向量中的元素數量很多時，查找的效率會明顯的降低。
一種有效的存儲方式，是不與其他元素進行比較，一次存取便能得到所需要的記錄。這就需要在對象的存儲位置和對象的關鍵屬性（設為 k）之間建立一個特定的對應關系（設為 f），使每個對象與一個唯一的存儲位置相對應。在查找時，只要根據待查對象的關鍵屬性 k 計算f(k)的值即可。如果此對象在集合中，則必定在存儲位置 f(k)上，因此不需要與集合中的其他元素進行比較。稱這種對應關系 f 為哈希（hash）方法，按照這種思想建立的表為哈希表。
Java 使用哈希表類（Hashtable）來實現哈希表，以下是與哈希表相關的一些概念：
•容量（Capacity）：Hashtable 的容量不是固定的，隨對象的加入其容量也可以自動增長。
•關鍵字（Key）：每個存儲的對象都需要有一個關鍵字，key 可以是對象本身，也可以是對象的一部分（如某個屬性）。要求在一個 Hashtable 中的所有關鍵字都是唯一的。
•哈希碼（Hash Code）：若要將對象存儲到 Hashtable 上，就需要將其關鍵字 key 映射到一個整型數據，成為 key 的哈希碼。
•項（Item）：Hashtable 中的每一項都有兩個域，分別是關鍵字域 key 和值域 value（存儲的對象）。Key 和 value 都可以是任意的 Object 類型的對象，但不能為空。
•裝填因子（Load Factor）：裝填因子表示為哈希表的裝滿程度，其值等于元素數比上哈希表的長度。
哈希表的使用
哈希表類主要有三種形式的構造方法：
Hashtable(); //默認構造函數，初始容量為 101，最大填充因子 0.75
Hashtable(int capacity);
Hashtable(int capacity,float loadFactor)
哈希表類的主要方法如表 8-6 所示。
表 8-6 哈希表定義的常見方法
| 方法 | 功能 |
|---|---|
| void clear() | 重新設置并清空哈希表 |
| boolean contains(Object value) | 確定哈希表內是否包含了給定的對象，若有返回 true，否則返回 false |
| boolean containsKey(Object key) | 確定哈希表內是否包含了給定的關鍵字，若有返回 true，否則返回 false |
| boolean isEmpty() | 確認哈希表是否為空，若是返回 true，否則返回 false |
| Object get(Object key) | 獲取對應關鍵字的對象，若不存在返回 null |
| void rehash() | 再哈希，擴充哈希表使之可以保存更多的元素，當哈希表達到飽和時，系統自動調用此方法 |
| Object put(Object key,Object value) | 用給定的關鍵字把對象保存到哈希表中，此處的關鍵字和元素均不可為空 |
| Object remove(Object key) | 從哈希表中刪除與給定關鍵字相對應的對象，若該對象不存在返回 null |
| int size() | 返回哈希表的大小 |
| String toString() | 將哈希表內容轉換為字符串 |
哈希表的創(chuàng)建也可以通過 new 操作符實現。其語句為：
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())); } }} |
運行結果：
|
1
2
3
4
|
21312.3 |
