哈希表
一、实验目的
学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。
二、实验内容
说明以下概念
1、哈希函数
在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。
1) 哈希函数是一个映象，即：
将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；
2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1¹ key2，而 f(key1) = f(key2)。
2、哈希表
根据设定的哈希函数f(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。
3、冲突及处理
1)冲突：对不同的关键字可能得到同意哈希地址，即key1¹ key2，而 f(key1) = f(key2)，这种现象称冲突(collision)。
2)处理方法：开放地址法。
4、哈希表的查找分析
从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。
决定哈希表查找的ASL的因素：
1) 选用的哈希函数；
2) 选用的处理冲突的方法；
3) 哈希表饱和的程度，装载因子 α=n/m 值的大小（n—记录数，m—表的长度）
一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，哈希表的ASL是处理冲突方法和装载因子的函数。
可以证明：
查找成功时有下列结果：
线性探测再散列
随机探测再散列
从以上结果可见
哈希表的平均查找长度是a的函数，而不是n的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子a，使得平均查找长度限定在某个范围内。
5、哈希函数C语言代码
/*计算哈希地址，插入哈希表*/
int InsertHash(HashTable *H,int e,int d[]){
int k,i=1;
k=e%P;
while(H->data[k].flag==TRUE||k<0){
k=(e%P+d[i])%MAXSIZE;i++;
if(i>=15)
return ERROR;
}
H->data[k].key=e;
H->data[k].flag=TRUE;
H->count++;
return OK;
}
/*构造哈希表*/
int CreateHash(HashTable *H,int ds[],int len,int d[]){
int i;
for(i=0;i<len;i++){
if(SearchHash(H,ds[i],d)!=-1)
return DUPLICATE;
InsertHash(H,ds[i],d);
if(H->count>=MAXSIZE)
return ERROR;
}
return OK;
}
/*初始化哈希表*/
void InitHash(HashTable *H){
int i;
for(i=0;i<MAXSIZE;i++){
H->data[i].key=0;
H->data[i].flag=FALSE;
}
}
/*在哈希表中查找*/
int SearchHash(HashTable *H, int e,int d[]){
int k,i=1;
k=e%P;
while(H->data[k].key!=e){
k=(e%P+d[i])%MAXSIZE;i++;
if(i>=15)
return -1;
}
return k;
}
运行结果：
第二篇：C#实验5实验报告
安徽机电职业技术学院实验报告
一、实验目的
1、进一步掌握类和对象的基本概念，掌握类字段和属性的使用；
2、掌握类的索引器的用途和使用；
3、了解类的静态成员用其作用；
4、掌握使用类来构造应用程序。
二、实验内容
使用Visual Studio .NET 2005，完成以下程序：
程序1、完成“使用索引器”的课堂示例(CSharp示例\第5课\Country)；
程序2、“使用类的静态成员”的课堂练习(CSharp示例\第5课\Static)；
程序3、使用贷款类完成“贷款计算器” (CSharp示例\第5课\Loan)；
三、实验步骤
1、将服务器上“面向对象”课件的文件夹中的“Csharp示例\第5课\ Country”文件夹复制到本地磁盘上。打开其中的“Country.sln
”，完成其中的2个任务。将这两个任务的代码写在下面。
// TODO 1: 完成下面的索引器，该索引器可以返回peoples数组中index下标的人口数量
public double this[int index]
{
get
{
return this.peoples[index];
}
// TODO 2: 书写第2个索引器，该索引器接收一个字符串格式的国家名称，可以返回对应的peoples数组中的国家人口数量
public class CountryPeoples
{
private string[] country = { "中国", "美国", "法国", "日本", "韩国", "印度" };
private double[] peoples = { 1.306e+10, 2.5e+9, 6.09e+8, 1.274e+9, 4.829e+8, 1.027e+10 };
public double this[string index]
{
get
{
int i=0;
foreach (string c in country )
{
if ( c ==index ) break;
i++;
}
if (i>=peoples.Length) return 2;
else return peoples[i];
}
}
}
}
CountryPeoples c1 = new CountryPeoples();
Output("韩国的人口数量是：" + c1["韩国"]);
Output("法国的人口数量是：" + c1["法国"]);
Output("美国的人口数量是：" + c1["美国"]);
Output("日本的人口数量是：" + c1["日本"]);
Output("印度的人口数量是：" + c1["印度"]);
2、将服务器上“面向对象”课件的文件夹中的“Csharp示例\第5课\Static”文件夹复制到本地磁盘上。打开其中的“StaticExample.sln”，完成其中的3个任务。
// TODO 1: 添加一个公共的静态的整型成员numberOfAntelopes
public class NumberOfAntelopes
{
private static int numberofantelopes = 0;
// TODO 2: 将numberOfAntelopes成员变量值加1
numberOfAntelopes++;
// TODO 3: 显示已经创建的羚羊(Antelope)的数量
Output("羚羊的数量: " + Antelope.numberOfAntelopes);
// TODO 4: 如果可能，将TODO 1中的numberOfAntelopes设成私有的，
// 然后通过公共的属性或方法对外公开。并在TODO 3中调用这个属性或方法
public static int numberOfAntelopes = 1;
3、将服务器上“面向对象”课件的文件夹中的“Csharp示例\第5课\MyLoan”文件夹复制到本地磁盘上。打开其中的“MyLoan.sln”，设计Form1窗体如下图所示：
并在“计算”按钮的Click事件中，实例化Loan类的对象来完成贷款计算器的功能。
// “计算”按钮Click事件中的代码
decimal a;
double b;
int c;
a = x.Value;
b = (double)y.Value;
c = (int)z.Value;
Loan l = new Loan (a,b,c);
string output = String.Empty;
output += String.Format("本金:{0:C}\n",l.Principal);
output += String.Format("月数: {0}\n",l.Months);
output += String.Format("月利率:{0:p}\n",l.MonthlyInterestRate);
output += String.Format("月付款:{0:C}\n",l.Payment);
for (int month=0;month <=l.Months; month++)
{
output +=String.Format("{0月余额:1,-10:C}\n", month , l[month]);
}
Txtoutput.Text = output ;
}
5、将完成的源程序压缩后，连同本实验报告，一同交给指导教师。
四、程序运行结果截图
程序1的运行结果截图：
程序2的运行结果截图：
程序3的运行结果截图：
五、思考题
1、请举例说明值类型与引用类型的区别。
2、重载方法的基本要求是什么？C#中的静态方法应该怎么调用(通过类名还是通过对象名)？
3、你认为索引器的使用，可以为我们编程人员带来哪些方便？
六、程序源代码(用Winrar压缩后用附件提交，源代码中要有比较完备的注释)
七、收获，体会及问题(写得越详细、越个性化、越真实越好，否则我不知道你做这个实验的心路历程，也就无法充分地判断你是否是独立完成的这个实验、你是否在做这个实验时进行了认真仔细地思考、通过这个实验你是否在实践能力上得到了提高)