学步园

    在算法导论中，很多应用中，都要用到一种动态的集合结构，它支持查找，插入，删除等操作。比如，计算机程序设计语言C语言吧，编译器需要维护一个符号表，其中元素的关键字值为任意字符串，与C语言中的标识符意思一样.举个例子，比如，int
iCount  = 100;

当你在编译器上写这条语句时，编译器就会将其存入一个内存空间，在后面你用到100时,编译器直接根据iCount来查找100所在的内存空间,并调用其值..这样一系列由iCount组成的数据结构就是散列表.      散列表中存放的是关键字,计算机再根据关键字得到关键字关联的元素值的内存空间地址,来获取元素值,并调用它. 这样的运算就和数组的直接位调用一样,属于直接寻址,空间复杂度为O(1).

       可能你会说,既然和数组一样,那为什么不用数组，要那么麻烦去做一个散列表。原因很简单，假如你有一百万个元素，存放在数组中，那么当你调用时你还能记得你要调用的元素，是在数组中的哪个位置么？如果我们通过散列表，关键字记录数据在散列表中的地址，我们要调用的时候这样根据关键字来找就可以马上知道要找的数据在哪。可能你还会问，我们用for循环遍历内存空间就行了，那也可以，但是如果数据很多，你要花费多少时间呢？

       散列表是必须是一段连续的内存空间，所以在使用散列表的时候 难免就会浪费空间，但是为了效率，你不得不那么做。

       讲了这么多，可能你还是不知道什么是散列表，那么就用例子来说明吧。

假如你要存放一个数据,0001-10010101.它是John的传真号码,你下次再调用的时候你可能已经忘了你存放的地址,没关系,散列表中，你可以把John当做关键字,通过散列函数（哈希函数）(int)hash(John)将关键字映射后得到比如为145的值,把145当做存储地址，存放散列表中，下次读取的时候仍然是通过hash算法演绎成145直接读取内容。

       对于散列函数（哈希函数）要如何编写，没有特定说明，但是函数要均匀和简单。映射出来的值，应该劲量避免重复。对于散列函数，我个人有两个发现，一个是你给定的关键字字符串的每个字符乘以一个质数，这样得到的值重复性就比较低，为什么是这样呢，那就需要你自己去推导看看或者查看有关数论方面的只是，第二个是如果你的散列表有101个槽，那么你就将前一步字符串得到的值除以100求得的余数就是数据在散列表中的地址了，除以101求余数为了就是做到均匀，这样余数才会从0到100都有。

       讲了这么多，还是放代码吧，其实如果真的性能要求不高的话，就不需要用散列表，毕竟还是浪费空间来提高效率的:

#include <Windows.h>
#include <string.h>
#include <iostream>

using namespace std ;

#define HASHSIZE	101

struct HashInfo
{
	char *key ;
	char *content ;

	struct HashInfo*  next ;
};

static struct HashInfo *HashTable[HASHSIZE] ;

//哈希函数,用于将关键字转换成特殊值
unsigned _Hash(char* key_c)
{
	unsigned Hashval ;
	//一个被除数除以一个除数,其余数可以为0到"除数减一"个.
	for( Hashval = 0 ; *key_c != '\0'; ++key_c )
		Hashval = *key_c + 7*Hashval ;

	return Hashval%HASHSIZE ;
}

struct HashInfo* Search(char *key)
{
	struct HashInfo *p ;
	/*=======================================================
	= 通过直接寻址,找到关键字对应的链表节点,然后可能存在	    =
	= 有相同关键字的值,所以应该还要将该槽的链表找完.		    =	
	= 这样我们散列表的空间复杂度就不能O(1)了,这有时候难以避免	= 
	= 除非,你能设计出一个哈希函数,不论用户输入什么用的关键字你	=
	= 都能将其转换为不重复的关键字.							=
	========================================================*/
	for( p = HashTable[_Hash(key)] ; p != NULL ; p=p->next )
		if( strcmp(key, p->key) == NULL )
			return p ;
	return NULL ;
}

struct HashInfo *Insert(char *key, char *value)
{
  struct HashInfo *p;
  unsigned hashval;

  //如果找不到关键字在结构体链表中
  if ((p = Search(key)) == NULL) {				
	//为其指针申请内存空间,用于指向一个新的结构体
    p = (struct HashInfo *)malloc(sizeof(*p));	

    if ( p == NULL || (p->key = strdup(key)) == NULL)
      return NULL;

	//哈希函数返回映射值.
    hashval = _Hash(key);						
	/*===============================================================
	= 将链表的节点指向散列表的一个槽,作为该槽自己的链表的第一个节点		=
	= 用于如果遇到碰撞(通过哈希函数映射有具有相同的关键字),则在该映射位	=
	= 置重组链表,解决冲撞问题.										=
	================================================================*/
    p->next = HashTable[hashval];		
	//当然,也要把该槽的指针值指向关键字的结构体
    HashTable[hashval] = p;
  } else
	  //若关键字已经存在则,先释放先前的内容.
	  free((void *)p->content);
  //改变关键字关联的元素值.
  if ((p->content = strdup(value)) == NULL)
    return NULL;
  return p;
}

char *GetValue(char *key)
{
  struct HashInfo *p;

  if ((p = Search(key)) == NULL)
    return NULL;
  else 
	  return p->content;
}

int _tmain(int argc, _TCHAR* argv[])
{
	char *value ;

	Insert("address of Limei","北京路");
	Insert("address of Jon", "中山路") ;
	Insert("address of Joy", "胜利路") ;

	value  = GetValue("address of Limei") ;
	cout<<value<<endl ;

	system("pause") ;
	return 0;
}

这里我们将三个人的居住地存入散列表，如果有100人的话，我们只需要记得我们要找谁的居住地，将其载入GetValue函数，就可以通过哈希函数分解成地址值直接获得其居住地。如，GetVlaue("address of Limei") ; 就能找到“北京路”。