什么是分离链接散列表
分离链接散列表是散列表解决冲突的一种方法，其做法是将散列到同一个值的所有元素保留到一个表中。为方便起见，这些表都有表头
分离链接散列表的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| struct ListNode;
typedef struct ListNode* Position;
struct HashTbl;
typedef struct HashTbl* HashTable;
typedef int ElementType;
HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(ElementType key,HashTable H);
void Insert(ElementType key,HashTable H);
ElementType Retrieve(Position P);
static int Hash(const int key,int TableSize);
struct ListNode{
ElementType Element;
Position Next;
};
typedef Position List;
struct HashTbl{
int TableSize;
List* TheList;
};
|
分离链接散列表的初始化
分离链接散列表在数组的每个位置保存有冲突元素组成链表的表头
1
2
3
4
5
6
7
8
9
10
11
12
| HashTable InitializeTable(int TableSize){
HashTable H = NULL;
H = (HashTable)malloc(sizeof(struct HashTbl));
if(H == NULL) return NULL;
H->TableSize = TableSize;
H->TheList = (List*)malloc(sizeof(struct ListNode) * TableSize);
for(int i = 0;i < TableSize;i++){
H->TheList[i] = (List)malloc(sizeof(struct ListNode));
H->TheList[i]->Next = NULL;
}
return H;
}
|
分离链接散列表的插入
插入时先计算Hash值，然后将值作为对应表头的第一个元素，这里就相当与链表的头插法
1
2
3
4
5
6
7
8
9
10
| void Insert(ElementType key,HashTable H){
if(H == NULL) return ;
int index = Hash(key,H->TableSize);
Position ptr = H->TheList[index];
Position temp = (List)malloc(sizeof(struct ListNode));
if(temp == NULL) return ;
temp->Element = key;
temp->Next = ptr->Next;
ptr->Next = temp;
}
|
分离链接散列表的查找
查找时首先计算要查找值的Hash值，然后返回对应的表头，遍历链表，找到就返回
1
2
3
4
5
6
7
8
9
10
11
12
| Position Find(ElementType key,HashTable H){
if(H == NULL) return NULL;
int index = Hash(key,H->TableSize);
Position ptr = H->TheList[index];
ptr = ptr->Next;
while(ptr != NULL){
if(ptr->Element == key)
return ptr;
ptr = ptr->Next;
}
return NULL;
}
|
参考源码