2010数据结构实验指导书48

实验五 散列表

【实验目的】

1 掌握散列表的构造方法； 2 观察冲突现象及其解决； 3 掌握使用散列法进行查找的方法。

【实验原理】

散列（hashing）的基本思想是：通过一个确定的散列函数关系H，把数据对象的关键字K映射到相应

的散列值H (K)，这个值就是该对象在散列表中的存储位置，又称散列地址。查找时根据要查找的关键字k用同样的散列函数计算地址H（k），然后在散列表相应的单元取要找的对象。对于散列表，最重要的是构造散列函数和对冲突的处理。影响散列表查找效率的因素是装填因子（load factor）。

【实验要求】

实验课题：做这个实验时采用Open Addressing框架，也可加做Separate Chaining以形成比较。 1 构造散列表，把字符串数组中的各项加入到散列表中

string MyBirds[13] = { "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay", "owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" }; 用C表示，可以是

char * MyBirds[13] = { "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay", "owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" };

为便于观察冲突现象，初始构造散列表时，表的容量不要过大，对Open Addressing，装载因子为0.5左右，对于Separate Chaining，装载因子为1左右即可。也不要做rehash（应该改源代码的哪里，如何改）。

建议对源代码做些改动、增加一些输出（建议用条件编译控制这些输出），以便于观察冲突的发生和解决；

对于Open Addressing，参考代码的冲突解决方案是用的平方探测（quadratic probing），如果用线性探测（linear probing）的策略，应该对函数findPos做什么修改（冲突解决的策略都集中在那里）？

2 观察不同的散列函数产生冲突散列地址的情况

教科书上给了3个以字符串作输入的散列函数（两教科书第3个不一样），观察记录它们产生冲突散列地址的情况，写入你的实验报告。还可对下列散列函数（所谓ELF hash，Unix System V用的）作观察