哈希表也稱為散列表，是用來存儲群體對象的集合類結(jié)構(gòu)。

什么是哈希表

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

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

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

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

哈希表的使用

哈希表類主要有三種形式的構(gòu)造方法：

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

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

哈希表的創(chuàng)建也可以通過 new 操作符實(shí)現(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()));
    }
  }
}

運(yùn)行結(jié)果：

2
1
3
12.3

最新評論