哈希表也稱(chēng)為散列表，是用來(lái)存儲(chǔ)群體對(duì)象的集合類(lèi)結(jié)構(gòu)。

什么是哈希表

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

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

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

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

哈希表的使用

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

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

表 8-6 哈希表定義的常見(jiàn)方法

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

    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

最新評(píng)論