残星
0%

数据结构c语言描述七-开放定址散列表

Posted on Edited on In

什么是开放定址法

开放定址法是另一种不用链表解决散列表冲突问题的方法，在开放定址散列算法系统中，如果发生冲突，那么就要尝试选择另外的单元，直到找出空的单元为止

冲突解决的方法

  1. 线性探测法
  2. 平方探测法
  3. 双散列

这里使用平方探测法进行示例，平方探测法在第一次冲突时将第一次哈希值的结果加上 F(i)，如果还是冲突，那么 i 加 1 ,再次使用第一次哈希值加上 F(i) 以此循环; F(i) = i * i(i = 1)

类型声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef unsigned int Index;
typedef Index Position;
struct HashTbl;
typedef struct HashTbl* HashTable;
typedef int ElementType;
HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(ElementType key,HashTable H);
HashTable Insert(ElementType key,HashTable H);
static Index Hash(const int key,int TableSize);

enum KindOfEntry{Legitimate,Empty,Deleted};
struct HashEntry{
	ElementType Element;
	enum KindOfEntry Info;
};
typedef struct HashEntry Cell;
struct HashTbl{
	int TableSize;
	int Capacity;
	Cell* TheCells;
};

在哈希表中，保存有哈希表的表长，当前表的容量，以及存储单元，每个存储单元保存实际存储的值，以及存储单元的信息，包括已经存储，没有存储和原来有存储现在被删除三种信息

哈希表的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
HashTable Insert(ElementType key,HashTable H){
	if(H == NULL) return NULL ;
	int index = Hash(key,H->TableSize);
	int number = 0;
	//检查表容量
	if(H->Capacity >= H->TableSize) {
		return H;
	}
	//查找可以可以插入的点
	while(H->TheCells[index].Info == Legitimate){
		index = index + 2 * (++number) + 1;
		if(index >= H->TableSize)
			index = index - H->TableSize;
	}
	//插入数据，重置单元信息，表容量加1
	H->TheCells[index].Element = key;
	H->TheCells[index].Info = Legitimate;
	H->Capacity++;
	return H;
}

哈希表的查找

查找操作也是和插入操作差不多的，不同的是如果查找的单元为空，则说明查找不成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Position Find(ElementType key,HashTable H){
	if(H == 0) return -1;
	int index = Hash(key,H->TableSize);
	int number = 0;
	while(1){
		if(H->TheCells[index].Info == Empty){
			return -1;
		}
		if(H->TheCells[index].Element == key) return index;
		index += 2 * (++number) + 1;
		if(index >= H->TableSize)
			index = index - H->TableSize;
	}
	return -1;
}

参考源码