散列表的实现常常叫做散列(hashing)。散列是一种用于以常数平均时间执行插入、删除和查找的技术。但是，那些需要元素间任何排序信息的操作将不会得到有效的支持。


理想的散列表数据结构只不过是一个包含有关键字的具有固定大小的数组。


每个关键字被映射到从0到TableSize-1这个范围中的某个数，并且被放到适当的单元中。这个映射就叫做散列函数(hash function)。


两个关键字散列到同一个值(称为冲突(collision))。


好的办法通常是保证表的大小是素数。


关键字通常是字符串。

散列函数1：把字符串中字符的ASCII码加起来：

typedef unsigned int Index;
Index Hash(const char *Key ,int TableSize)
{
    unsigned int HashVal=0;
    while(*Key !='\0')
        HashVal+=*Key++;
    return HashVal % TableSize ;
}


散列函数2(不太好)：这个散列函数假设Key至少有两个字符外加NULL结束符。值27表示英文字母表的字母个数外加一个空格，而272=729。

Index Hash( const char* Key, int TableSize)
{
    return ( Key[0]+27*Key[1]+729*Key[2] )% TableSize ;
}


散列函数3(好的散列函数)：根据Horner法则扩展。

Index Hash( const char* Key,int TableSize)
{
    unsigned int HashVal=0;
    while(*Key !='\0')
        HashVal=(HashVal<<5 )* *Key++;
    return (HashVal % TableSize) ;
 }


解决冲突的方法：分离链接法和开放定址法

分离链接法：一个指针数组，每个元素都指向一个链表，这个链表中的节点的元素都有相同的个位数值。

#ifndef _HashSep_H

struct ListNode;
typedef struct ListNode *Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitializeTable(int TableSize);
void DestoryTable(HashTable H);
Position Find(ElementType key,HashTable H);
void Insert(ElementType key,HashTable H);
ElementType Retrieve(Position P);

#endif

struct ListNode
{
    ElementType Element;
    Position Next;
};

typedef Position List;
struct HashTbl
{
    int TableSize;
    List *TheLists;
};