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("");elseH->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;} }

转载于:https://www.cnblogs.com/mtcnn/p/9423656.html

总结

以上是生活随笔为你收集整理的HashTable 解决碰撞（冲突）的方法 —— 分离链接法（separate chaining）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。