【内附源码和文档】散列表的设计与实现

散列表的设计与实现

一、需求分析

本系统为电话号码查找系统，本系统最频繁的操作为查询功能，查询速度的快慢对此系统有至关重要的影响，因此应该选择合适的数据结构来进行设计。散列表可以实现 O(1)的快速查找，用 Hash 数据结构作为底层存储结构较为合适。本系统应首先实现Hash表的基本结构和操作，在此基础上构建电话号码查找系统。电话号码查找系统包括若干数据项：电话号码、用户名、地址，可以键盘输入或文件批量导入记录，既可以使用电话号码作为索引建立Hash表，也可以使用姓名作为索引建立Hash表，并通过电话号码和姓名进行查找记录。更进一步，在设计Hash数据结构时，可设计不同的Hash函数及采用不同的冲突解决算法，来比较性能的差异。具体功能如下：

1.1 Hash表设计
设计 Hash 表的 ADT，设计 Hash 表的存储结构以及基本操作，设计不同的 Hash函数对字符串进行散列，设计不同的冲突解决策略，如链地址法、线性探测法等。Hash表的结构由key-value组成，基本操作有添加元素、查找元素、删除元素、遍历元素、建表、销毁表等，并且设计可以计算平均查找长度（ASL）的函数，以此来比较不同的Hash函数使用相同的冲突解决算法，以及相同的Hash 函数使用不同的冲突解决算法的优劣。为方便Hash表的使用，Hash表可自动扩容。

1.2 添加与导入记录
系统可采用两种方式导入信息：手动添加与文件批量导入。手动添加方式用户通过交互性界面一步一步输入待添加记录的电话号码、姓名、地址，可连续进行添加。文件批量导入方式，预先将记录以指定格式写入文件，系统再从指定文件中批量导入。

1.3 查询记录
查询记录功能为此系统主要功能，可采用两种查询方式：按电话号码查询与按姓名查询。如果是按照电话号码建立索引，按电话号码查询将迅速完成，如果是按照姓名建立索引，按姓名查询将迅速完成。

1.4 不同Hash函数比较
设计多种 Hash 函数，使用同一冲突解决方法比较其 ASL，研究不同 Hash 函数对于冲突率的影响。

1.5 不同冲突解决方法比较
设计多种冲突解决方法，使用同一 Hash 函数比较其 ASL，研究不同的冲突解决方法对于 ASL 的影响。

二、概要设计

2.1 数据类型的定义
使用链地址法的 Hash ADT 设计

#define MAXCAPACITY 1 << 30 
#define LOADFACTOR 0.75f 
#define MAXKEYLEN 255 
typedef AddList ElemType;
struct Node {
	char key[MAXKEYLEN];
	ElemType value;
	Node *next;
}
;
struct HashTable {
	int capacity;
	int size;
	Node *table;
}
;
int NextPrime(int n);
void InitHashTable(HashTable &hash_table, int init_capacity);
unsigned int SumHash(const char *key, int table_size);
unsigned int ShiftHash(const char *key, int table_size);
unsigned int ELFHash(const char *key, int table_size);
bool Put(HashTable &hash_table, const char *key, ElemType value, ElemType 
&old_value, unsigned int (*Hash)(const char *key, int table_size));
bool Get(HashTable &hash_table, const char *key,  ElemType &value, unsigned int (*Hash)(const char *key, int table_size));
bool Remove(HashTable &hash_table, const char *key, ElemType &value, unsigned int (*Hash)(const char *key, int table_size));
void DelHashTable(HashTable &hash_table);
void TraverseHashTable(HashTable &hash_table, void (*visit)(ElemType v));
double GetASL(HashTable &hash_table, unsigned int (*Hash)(const char *key, int table_size));

使用线性探测法的 Hash ADT 设计

typedef AddList ArrElemType;
// 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素  
typedef enum {
	Legitimate, Empty, Deleted
}
NodeType;
struct HashNode {
	char key[MAXKEYLEN];
	ArrElemType value;
	NodeType type;
}
;
struct ArrayHashTable {
	int size;
	int capacity;
	HashNode *table;
}
;
void InitArrayHashTable(ArrayHashTable &hash_table, int init_capacity);
void DelArrayHashTable(ArrayHashTable &hash_table);
bool IsFull(ArrayHashTable &hash_table);
bool LinearDelete(ArrayHashTable &hash_table, const char *key);
bool LinearGet(ArrayHashTable &hash_table, const char *key, ArrElemType 
&value);
bool 	LinearGetNum(ArrayHashTable 	&hash_table, 	const 	char 	*key, 
ArrElemType &value, int &num);
int LinearPut(ArrayHashTable &hash_table, const char *key, ArrElemType value, ArrElemType &old_value);
电话查找系统数据类型定义

struct AddList {
	char phone_num[MAXPHONENUM];
	char name[MAXNAME];
	char address[MAXADDRESS];
	AddList() {
	}
	AddList(const char *phone_num, const char *name, const char *address) {
		strcpy(this->phone_num, phone_num);
		strcpy(this->name, name);
		strcpy(this->address, address);
	}
}
;

2.2 功能模块结构图

根据需求分析，为了满足用户的功能需求，将系统划分为以下几个模块：Hash 表模块、查询记录模块、添加记录模块、导入记录模块、Hash 函数比较模块、冲突解决办法比较模块。其中 Hash 表模块包括链表实现的 Hash 表  模块和线性探测法实现的 Hash 表  模块，查询记录模块包括电话号码查询子模块和姓名查询子模块。

图 1 模块结构图

三、运行环境

硬件环境：
cpu：Intel® Core™ i7-6500U CPU @ 2.50GHz × 4
内存：8G
软件环境：
OS：Ubuntu 18.04.1 LTS 64位
Linux内核：Linux version 4.4.0-17134-Microsoft

完整的源码和详细的文档，上传到了 【WRITE-BUG数字空间】，需要的请自取：
https://www.writebug.com/code/0c804e39-c792-11ed-a4d9-6479f0e5e323/#