HashTable 解决碰撞（冲突）的方法 —— 分离链接法（separate chaining）

1. ListNode 及 HashTable 的类型声明

• 声明

  typedef int ElementType;
  
  typedef unsigned int Index;
  
  struct ListNode;
  
  typedef struct ListNode* Position;
  
  struct HashTbl;
  
  typedef struct HashTbl* HashTable;
  
  HashTable InitHashTable(int TableSize);
  
  void DestroyHashTable(HashTable H);
  
  Position Find(ElementType Element, HashTable H);
  
  void Insert(ElementType Element, HashTable H);;
  
  ElementType Retrieve(Position P);

• 定义

  struct ListNode{
  
      ElementType Element;
  
      Position Next;
  
  };
  
  typedef Position List;
  
  struct HashTbl {
  
      int TableSize;
  
      List* TheLists;
  
  };

2. HashTable 的构建

HashTable InitHashTable(int TableSize){

    HashTable H;

    if (TableSize < MinTableSize){

        Error(" ... ");

        return NULL;

    }

    H = (HashTable)malloc(sizeof(struct HashTbl));

    if (!H)

        FatalError("out of space !!!");

    H->TableSize = NextPrime(TableSize);

    H->TheLists = (List*)malloc(sizeof(struct ListNode)*H->TableSize);

    for (int i = 0; i < H->TableSize; ++i){

        H->TheLists[i] = (List)malloc(sizeof(struct ListNode));

        if (!H->TheLists[i])

            FatalError("");

        else

            H->TheLists[i]->Next = NULL;

    }

}

3. 插入新的结点

void Insert(ElementType Key, HashTable H){

    Position Pos, NewCell;

    List L;

    Pos = Find(key, H);

    if (!Pos){

        NewCell = (Position)malloc(sizeof(struct ListNode));

        if (!NewCell)

            FatalError("");

        L = H->TheLists[Hash(Key, H->TableSize)];

        NewCell->Next = L->Next;

                                    // 插入在首部

        NewCell->Element = Key;

        L->Next = NewCell->Next;

    }

}