哈希表(Hashtable)

lihonghao_shzh 2008-03-19

展開全文

1.哈希表(Hashtable)是什么

在.NET Framework中，Hashtable是System.Collections命名空間提供的一個容器，用于處理和表現(xiàn)類似 key/value的鍵值對，其中key通?？捎脕砜焖俨檎?，同時key是區(qū)分大小寫；value用于存儲對應(yīng)于key的值。Hashtable中 key/value鍵值對均為object類型，所以Hashtable可以支持任何類型的key/value鍵值對.

2.哈希表(Hashtable)的簡單操作代碼

在哈希表中添加一個key/value鍵值對：HashtableObject.Add(key,value);
在哈希表中去除某個key/value鍵值對：HashtableObject.Remove(key);
從哈希表中移除所有元素： HashtableObject.Clear();
判斷哈希表是否包含特定鍵key： HashtableObject.Contains(key);
下面控制臺程序?qū)陨纤胁僮鳎?nbsp;
using System;
using System.Collections; //使用Hashtable時，必須引入這個命名空間
class hashtable
{
public static void Main()
{
Hashtable ht=new Hashtable(); //創(chuàng)建一個Hashtable實例
ht.Add("E","e");//添加key/value鍵值對
ht.Add("A","a");
ht.Add("C","c");
ht.Add("B","b");

string s=(string)ht["A"];
if(ht.Contains("E")) //判斷哈希表是否包含特定鍵,其返回值為true或false
Console.WriteLine("the E key:exist");
ht.Remove("C");//移除一個key/value鍵值對
Console.WriteLine(ht["A"]);//此處輸出a
ht.Clear();//移除所有元素
Console.WriteLine(ht["A"]); //此處將不會有任何輸出
}
}

3.遍歷哈希表(Hashtable)方法

遍歷哈希表需要用到DictionaryEntry Object，代碼如下：
for(DictionaryEntry de in ht) //ht為一個Hashtable實例
{
Console.WriteLine(de.Key);//de.Key對應(yīng)于key/value鍵值對key
Console.WriteLine(de.Value);//de.Key對應(yīng)于key/value鍵值對value
}

4.對哈希表(Hashtable)進行排序

對哈希表進行排序在這里的定義是對key/value鍵值對中的key按一定規(guī)則重新排列，但是實際上這個定義是不能實現(xiàn)的，因為我們無法直接在Hashtable進行對key進行重新排列，如果需要Hashtable提供某種規(guī)則的輸出，可以采用一種變通的做法：
ArrayList akeys=new ArrayList(ht.Keys); //別忘了導入System.Collections
akeys.Sort(); //按字母順序進行排序
for(string skey in akeys)
{
Console.Write(skey + ":");
Console.WriteLine(ht[skey]);//排序后輸出
}

5.哈希表(hashtable)原理及特點

我們使用一個下標范圍比較大的數(shù)組來存儲元素。可以設(shè)計一個函數(shù)（哈希函數(shù)，也叫做散列函數(shù)），使得每個元素的關(guān)鍵字都與一個函數(shù)值（即數(shù)組下標）相對應(yīng)，于是用這個數(shù)組單元來存儲這個元素；也可以簡單的理解為，按照關(guān)鍵字為每一個元素"分類"，然后將這個元素存儲在相應(yīng)"類"所對應(yīng)的地方。

但是，不能夠保證每個元素的關(guān)鍵字與函數(shù)值是一一對應(yīng)的，因此極有可能出現(xiàn)對于不同的元素，卻計算出了相同的函數(shù)值，這樣就產(chǎn)生了"沖突"，換句話說，就是把不同的元素分在了相同的"類"之中。后面我們將看到一種解決"沖突"的簡便做法。

總的來說，"直接定址"與"解決沖突"是哈希表的兩大特點。

6.哈希表(hashtable)函數(shù)構(gòu)造的2種方法

哈希表(hashtable)構(gòu)造函數(shù)的常用方法（下面為了敘述簡潔，設(shè) h(k) 表示關(guān)鍵字為 k 的元素所對應(yīng)的函數(shù)值）：

a) 除余法：

選擇一個適當?shù)恼麛?shù) p ，令 h(k ) = k mod p
這里， p 如果選取的是比較大的素數(shù)，效果比較好。而且此法非常容易實現(xiàn)，因此是最常用的方法。

b) 數(shù)字選擇法：

如果關(guān)鍵字的位數(shù)比較多，超過長整型范圍而無法直接運算，可以選擇其中數(shù)字分布比較均勻的若干位，所組成的新的值作為關(guān)鍵字或者直接作為函數(shù)值。

7.哈希表(hashtable)沖突處理方法及常用基本運算

沖突處理

線性重新散列技術(shù)易于實現(xiàn)且可以較好的達到目的。令數(shù)組元素個數(shù)為 S ，則當 h (k) 已經(jīng)存儲了元素的時候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲單元為止（或者從頭到尾掃描一圈仍未發(fā)現(xiàn)空單元，這就是哈希表已經(jīng)滿了，發(fā)生了錯誤。當然這是可以通過擴大數(shù)組范圍避免的）。

支持運算

哈希表支持的運算主要有：初始化(makenull)、哈希函數(shù)值的運算(h(x))、插入元素(insert)、查找元素(member)。
設(shè)插入的元素的關(guān)鍵字為 x ，A 為存儲的數(shù)組。
初始化比較容易，例如
const empty=maxlongint; // 用非常大的整數(shù)代表這個位置沒有存儲元素
p=9997; // 表的大小
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;

哈希函數(shù)值的運算根據(jù)函數(shù)的不同而變化，例如除余法的一個例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;

我們注意到，插入和查找首先都需要對這個元素定位，即如果這個元素若存在，它應(yīng)該存儲在什么位置，因此加入一個定位的函數(shù) locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//當這個循環(huán)停下來時，要么找到一個空的存儲單元，要么找到這個元
//素存儲的單元，要么表已經(jīng)滿了
locate:=(orig+i) mod S;
end;
插入元素
procedure insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函數(shù)的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即為發(fā)生了錯誤，當然這是可以避免的
end;

查找元素是否已經(jīng)在表中
procedure member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;

這些就是建立在哈希表上的常用基本運算。

8.OVER