散列

散清單的實作常常叫做散列(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;
};