哈希表(Hashtable)

1.哈希表(Hashtable)是什么

在.NET Framework中，Hashtable是System.Collections命名空间提供的一个容器，用于处理和表现类似 key/value的键值对，其中key通常可用来快速查找，同时key是区分大小写；value用于存储对应于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);  
下面控制台程序将包含以上所有操作：  
using System;  
using System.Collections; //使用Hashtable时，必须引入这个命名空间  
class hashtable  
{  
public static void Main()  
{  
Hashtable ht=new Hashtable(); //创建一个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对应于key/value键值对key  
Console.WriteLine(de.Value);//de.Key对应于key/value键值对value  
}

4.对哈希表(Hashtable)进行排序

对哈希表进行排序在这里的定义是对key/value键值对中的key按一定规则重新排列，但是实际上这个定义是不能实现的，因为我们无法直接在Hashtable进行对key进行重新排列，如果需要Hashtable提供某种规则的输出，可以采用一种变通的做法：  
ArrayList akeys=new ArrayList(ht.Keys); //别忘了导入System.Collections  
akeys.Sort(); //按字母顺序进行排序  
for(string skey in akeys)  
{  
Console.Write(skey + ":");  
Console.WriteLine(ht[skey]);//排序后输出  
} 

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

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对 应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。  

但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。  

总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。

6.哈希表(hashtable)函数构造的2种方法

哈希表(hashtable)构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：  

a) 除余法：  

选择一个适当的正整数 p ，令 h(k ) = k mod p  
这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。  

b) 数字选择法：  

如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。

7.哈希表(hashtable)冲突处理方法及常用基本运算

冲突处理  

线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h (k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍 未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。

支持运算  

哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。  
设插入的元素的关键字为 x ，A 为存储的数组。  
初始化比较容易，例如  
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素  
p=9997; // 表的大小  
procedure makenull;  
var i:integer;  
begin  
for i:=0 to p-1 do  
A[i]:=empty;  
End;  

哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：  
function h(x:longint):Integer;  
begin  
h:= x mod p;  
end;  

我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 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);  
//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元  
//素存储的单元，要么表已经满了  
locate:=(orig+i) mod S;  
end;  
插入元素  
procedure insert(x:longint);  
var posi:integer;  
begin  
posi:=locate(x); //定位函数的返回值  
if A[posi]=empty then A[posi]:=x  
else error; //error 即为发生了错误，当然这是可以避免的  
end;  

查找元素是否已经在表中  
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