碰到了个哈希表问题，虽然之前学习过（隔了也有好久了，而且后来我基本没用到过），但突然被问到哈希表算法我还真的是懵了，下来之后去网上搜索相关资料，看已有的代码示例，自己修改然后编译执行（好久没有用C语言写过代码了，各种错误，好不适应o(╯□╰)o），终于想起来其实自己之前在《数据结构》这门课和这本书上学习过，但当时没有实际编写、编译执行过对应的代码，所以印象还是不够深刻，只是简单的记得，下面重新学习/回顾一下哈希表算法：

---

哈希表，也称散列表。

通过散列函数（算法的好坏和散列函数的好坏息息相关，如果散列函数没选好，冲突较多的话，哈希表的效率就无法体现）将数据值和它的存储位置联系起来。即，通过精心地向表插入元素，从而提高访问/查找速度。本例中采取的解决冲突的办法是建立一个小写字母链表（对于默认/没有明显分布规律的英文单词组成的元素集合，这样一种散列函数的思路应该是没什么问题的，虽然没有考虑大写字母的问题），将字符串节点挂在对应位置的后面，根据计算出的散列函数值将元素都添加到这个链表中，可以从头部插入也可以从尾部追加，甚至可以再这个位置后面再挂一个散列表。

代码实现了将文件名按字母a-z分类，不区分大小写。先以数组存储各节点，当扫描发现该元素不存在时即将节点加入链表中（即，通过链接法解决碰撞问题）。然后遍历显示所有的文件名。查找字符串“androi”是否在该散列表中。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASHSIZE 26
#define FILENAMELENGTH 20
#define TRUE 1
#define FALSE 0

struct file{
	char name[FILENAMELENGTH];
	struct file *next;
};
struct file * files[HASHSIZE];

/* 将大写字符转为小写字母，本程序中哈希表不区分大小写 */
char case_insensitive(char ch) {
	if(isupper(ch))
		return ch - 'A' + 'a';
	return ch;
}

/*完成初始化工作*/
void init() {
	int i;
	for(i = 0 ; i < HASHSIZE; i++)
		files[i] = NULL;
}

/*哈希函数，返回在哈希表中的位置，哈希表各项以文件名首字母a-z区分*/
int hash(char *s) {
	return case_insensitive(s[0]) - 'a';
}

/*查询某个文件名在哈希结构中是否已存在*/
int search(char *s) {
	int num = hash(s);
	if(files[num] != NULL) {	//如果哈希表不空，已出现以该文件名首字母开头的文件名
		struct file *p = files[num];	//p指向链表中第一个节点
		while(p != NULL) {
			if(strcmp(p->name, s) == 0)
				return TRUE;
			p = p->next;
		}
	}
	return FALSE;
}

/*如果文件名在哈希结构中不存在，则插入*/
void insert(char *s) {
	if(search(s) == FALSE) {
		int num = hash(s);
		struct file *new_node = (struct file*)malloc(sizeof(struct file));
		strcpy(new_node->name, s);
		if(files[num] == NULL) {	//如果链表为空，将作为第一个节点
			files[num] = new_node;
			files[num]->next = NULL;
		}
		else {	//如果链表不空，将其放在第一个节点位置
			new_node->next = files[num];
			files[num] = new_node;
		}
	}
	// else do nothing;
}

/*显示该哈希结构中存储的所有文件名*/
void show_all() {
	int i;
	struct file *p = NULL;
	for(i = 0 ; i < HASHSIZE ; i++) {
		p = files[i];
		if(p != NULL) {
			printf("For file begins with %c:n", i + 'a');
			while(p != NULL) {
				printf("%sn", p->name);
				p = p->next;
			}
			printf("n");
		}
	}
}

/*释放之前所申请的内存*/
void free_all() {
	int i;
	struct file *p = NULL; struct file *q = NULL;
	for(i = 0 ; i < HASHSIZE ; i++) {
		p = files[i];
		if(p != NULL) {
		//	printf("Free filename begins with %c.n", i + 'a');
			free(p);	p = NULL;
		}
	}
}

int main() {
	char *file_names[] = {"apple","because","song","Dan","discuz","cartoon","nobody","android","information","love","like","No","nothing","like","alone","nothing"};
	int len = sizeof(file_names) / sizeof(char *);	//获得字符串数组的长度
	int i;
	char* search_str = "androi";
	for(i = 0; i < len; i++)
		insert(file_names[i]);
	show_all();
	if( search(search_str) ) {
		printf("the string '%s' exists in this array.n", search_str);
	} else {
		printf("the string '%s' doesn't exist in this array.n", search_str);
	}
	free_all();
	return 0;
}

上面代码中还存在一个问题：释放手动申请的内存时，只是释放了第一个节点的空间，位于其后的节点没有进行手动释放，因为逻辑上我还有点没弄清楚￣□￣｜｜，暂时的想法：

/*释放之前所申请的内存*/
void free_all() {
	int i;
	struct file *p = NULL; struct file *q = NULL;
	for(i = 0 ; i < HASHSIZE ; i++) {
		p = files[i];
		q = files[i]->next;
		if(p != NULL) {
			printf("Free filename begins with %c:n", i + 'a');
			while(p != NULL) {
				free(p);	p = NULL;
				p = q;	q = q->next;
			}
		}
	}
}

思路和show_all()函数很像，通过遍历该hash结构，依次释放遍历到的节点。不过执行起来会出现 Segmentation fault ￣□￣｜｜，我还得再测试测试。

将字符串数组中的元素循环插入哈希表，然后简单测试了一下建立散列表之后的查找功能（代码中查找的是字符串’androi’，当然也可以通过使用命令行参数手动输入或是产生随机字符串进行查找），这里只是为了演示/学习该算法，所以，暂时就先到这了，网上说的虽然也还行，但毕竟不系统，等明天起来再看看书，然后修改修改。

---

今天早晨起来之后又翻了翻书（本想着是找之前的课本《数据结构》来看的，因为我在上面做了很多笔记，后来发现我在将书打包的时候，将那些非常“重要”的书封装了几层，找出来太过麻烦而且灰尘也厚，所以后来看的是《算法导论》，一堆定理和公式，头发晕……），下面是一些概念性的内容：

---

参考地址：

• http://blog.csdn.net/lvsi12/article/details/8266884
• 《算法导论》