哈希表

哈希是一种用于以常数平均时间执行插入、删除和查找的技术。但是，那些需要元素间任何排序信息的操作将不会得到有效支持。诸如FindMin、FindMax以及以线性时间将排过序的整个表进行打印的操作都是哈希所不支持的；(备注:哈希本身是没有修改的)

/*
 * 哈希表(链接法解决哈希冲突)
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Error( Str )        FatalError( Str )
#define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )
#define MinTableSize (10)
typedef char *ElementType;
typedef unsigned int Index;
struct ListNode;
typedef struct ListNode *Position;
typedef Position List;
struct HashTbl;
typedef struct HashTbl *HashTable;
HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(ElementType Key, HashTable H);
void Insert(ElementType Key, ElementType Value, HashTable H);
ElementType Retrieve(Position P);
Index Hash( ElementType Key, int TableSize);
struct ListNode
{
    ElementType Key;
    ElementType Value;
    Position Next;
};
struct HashTbl
{
    int TableSize;
    List *TheLists;
};
/*
 * 返回离N++最近的质数
 */
static int NextPrime(int N)
{
    int i;
    if(N%2 == 0)
        N++;
    for( ; ; N += 2)
    {
        for(i=3; i*i <= N; i +=2 )
            if(N%i == 0)
                goto ContOuter;
                
        return N;
        ContOuter: ;
    }
}
/*
 * 哈希表初始化
 */
HashTable InitializeTable(int TableSize)
{
    HashTable H;
    int i;
    
    if(TableSize < MinTableSize)
    {
        Error("表的长度太小！！！");
        return NULL;
    }
    
    H = malloc(sizeof(struct HashTbl));
    if(H == NULL)
        FatalError("内存空间分配失败！！！");
        
    H->TableSize = NextPrime( TableSize );
    
    H->TheLists = malloc(sizeof(List) * H->TableSize);
    if(H->TheLists == NULL)
        FatalError("内存分配失败！！！");
        
    for(i=0; i<H->TableSize; i++)
    {
        H->TheLists[i] = malloc(sizeof(struct ListNode));
        if(H->TheLists[i] == NULL)
            FatalError("内存分配失败！！！");
        else
            H->TheLists[i]->Next = NULL;
    }
    
    return H;
}
Position Find(ElementType Key, HashTable H)
{
    Position P;
    List L;
    
    L = H->TheLists[ Hash(Key, H->TableSize)];
    P = L->Next;
    while(P != NULL && (strcmp(P->Key, Key) != 0))
        P = P->Next;
        
    return P;
}
void Insert(ElementType Key, ElementType Value, HashTable H)
{
    List L,NewCell;
    
    L = H->TheLists[ Hash(Key, H->TableSize)];//L为哈希表中存储键、值对的链接表
    if(L->Key == NULL && L->Value == NULL)
    {
        //头结点存储
        L->Key = malloc(sizeof(Key));
        if(L->Key == NULL)
            FatalError("内存分配失败！！！");
        strcpy(L->Key, Key);
        L->Value = malloc(sizeof(Value));
        if(L->Value == NULL)
            FatalError("内存分配失败！！！");
        strcpy(L->Value, Value);
    }
    else
    {
        //哈希冲突后，链式存储
        while(L->Next != NULL)
            L = L->Next;
        NewCell = malloc(sizeof(struct ListNode));    
        if(NewCell == NULL)
            FatalError("内存分配失败！！！");
        NewCell->Key = malloc(sizeof(Key));
        if(NewCell->Key == NULL)
            FatalError("内存分配失败！！！");
        strcpy(NewCell->Key, Key);
        NewCell->Value = malloc(sizeof(Value));
        if(NewCell->Value == NULL)
            FatalError("内存分配失败！！！");
        strcpy(NewCell->Value, Value);
        L->Next = NewCell;
    }
}
//哈希函数
Index Hash( ElementType Key, int TableSize)
{
    unsigned int HashVal = 0;
    
    while( *Key != '\0')
        HashVal = ( HashVal << 5 ) + *Key++;
        
    return HashVal % TableSize;
}
/*
 * 哈希表打印
 */
void Traverse(HashTable H)
{
    int i;
    List L;
    for(i=0; i<H->TableSize; i++)
    {    
        L = H->TheLists[i];    //TheLists里保存的为链表的头结点地址
        if(0 != i)
            printf("\n");
        printf("节点%d:key(%s)---value(%s)", i, L->Key, L->Value);    //头结点打印
        while(L->Next != NULL)
        {
            L = L->Next;
            printf("-key(%s)---value(%s)", L->Key, L->Value);
        }
        if(i == (H->TableSize - 1))
            printf("\n");
    }
}
void main()
{
    HashTable H;
    H = InitializeTable(13);
    char *a="abc", *b="ABC", *c="qwr", *d="abcdefg";
    Insert(a,b,H);
    Insert(a,c,H);
    Insert(d,c,H);
    Traverse(H);
}

1