java中哈希表及其應用詳解

更新時間：2015年06月10日 10:58:48 投稿：hebedich

Java中哈希表(Hashtable)是如何實現(xiàn)的呢？Hashtable中有一個內(nèi)部類Entry，用來保存單元數(shù)據(jù)，我們用來構建哈希表的每一個數(shù)據(jù)是Entry的一個實例。假設我們保存下面一組數(shù)據(jù)，第一列作為key, 第二列作為value。

哈希表也稱為散列表，是用來存儲群體對象的集合類結構。

什么是哈希表

數(shù)組和向量都可以存儲對象，但對象的存儲位置是隨機的，也就是說對象本身與其存儲位置之間沒有必然的聯(lián)系。當要查找一個對象時，只能以某種順序（如順序查找或二分查找）與各個元素進行比較，當數(shù)組或向量中的元素數(shù)量很多時，查找的效率會明顯的降低。

一種有效的存儲方式，是不與其他元素進行比較，一次存取便能得到所需要的記錄。這就需要在對象的存儲位置和對象的關鍵屬性（設為 k）之間建立一個特定的對應關系（設為 f），使每個對象與一個唯一的存儲位置相對應。在查找時，只要根據(jù)待查對象的關鍵屬性 k 計算f(k)的值即可。如果此對象在集合中，則必定在存儲位置 f(k)上，因此不需要與集合中的其他元素進行比較。稱這種對應關系 f 為哈希（hash）方法，按照這種思想建立的表為哈希表。

Java 使用哈希表類（Hashtable）來實現(xiàn)哈希表，以下是與哈希表相關的一些概念：

•容量（Capacity）：Hashtable 的容量不是固定的，隨對象的加入其容量也可以自動增長。
•關鍵字（Key）：每個存儲的對象都需要有一個關鍵字，key 可以是對象本身，也可以是對象的一部分（如某個屬性）。要求在一個 Hashtable 中的所有關鍵字都是唯一的。
•哈希碼（Hash Code）：若要將對象存儲到 Hashtable 上，就需要將其關鍵字 key 映射到一個整型數(shù)據(jù)，成為 key 的哈希碼。
•項（Item）：Hashtable 中的每一項都有兩個域，分別是關鍵字域 key 和值域 value（存儲的對象）。Key 和 value 都可以是任意的 Object 類型的對象，但不能為空。
•裝填因子（Load Factor）：裝填因子表示為哈希表的裝滿程度，其值等于元素數(shù)比上哈希表的長度。

哈希表的使用

哈希表類主要有三種形式的構造方法：

    Hashtable(); //默認構造函數(shù)，初始容量為 101，最大填充因子 0.75
    Hashtable(int capacity);
    Hashtable(int capacity,float loadFactor)
哈希表類的主要方法如表 8-6 所示。

表 8-6 哈希表定義的常見方法

方法	功能
void clear()	重新設置并清空哈希表
boolean contains(Object value)	確定哈希表內(nèi)是否包含了給定的對象，若有返回 true，否則返回 false
boolean containsKey(Object key)	確定哈希表內(nèi)是否包含了給定的關鍵字，若有返回 true，否則返回 false
boolean isEmpty()	確認哈希表是否為空，若是返回 true，否則返回 false
Object get(Object key)	獲取對應關鍵字的對象，若不存在返回 null
void rehash()	再哈希，擴充哈希表使之可以保存更多的元素，當哈希表達到飽和時，系統(tǒng)自動調(diào)用此方法
Object put(Object key,Object value)	用給定的關鍵字把對象保存到哈希表中，此處的關鍵字和元素均不可為空
Object remove(Object key)	從哈希表中刪除與給定關鍵字相對應的對象，若該對象不存在返回 null
int size()	返回哈希表的大小
String toString()	將哈希表內(nèi)容轉換為字符串

哈希表的創(chuàng)建也可以通過 new 操作符實現(xiàn)。其語句為：

HashTable has=new HashTable();

例子：

【例 8-12】哈希表的遍歷。

//********** 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()));
    }
  }
}

運行結果：