残星
0%

数据结构c语言描述八-再散列

Posted on Edited on In

什么是再散列

再散列也是散列表的一种，不同的是再散列可以动态的扩充表长，再搭配好的散列函数解决冲突

再散列在散列表到达某一临界点时扩充原来表长的容量，再将原来散列表中的数据重新散列移动到新的散列表的过程

类型声明

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

enum KindOfEntry{Legitimate,Emtry,Deleted};
struct HashEntry{
	ElementType Element;
	enum KindOfEntry Info;
};
typedef struct HashEntry Cell;
struct HashTbl{
	int TableSize;
	int Capacity;
	float LocalFacotr;//装填因子
	int MaxCapacity;//散列表所能容纳的最大容量，超过该容量后就要扩容
	Cell* TheCells;
};

这里采用当散列表容量达到指定的装填因子时进行再散列，采用的默认散列因子是 0.75，TableSize 表示散列表的长度，Capacity 表示散列表容乃数据的大小，MaxCapacity 表示散列表可以容纳的最大容量，由 TableSize × LocalFacotr 得出

散列表的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
HashTable Insert(ElementType key,HashTable H){
	if(H == NULL) return NULL ;
	if(H->Capacity >= H->MaxCapacity){
		H = Rehash(H);
	}
	int index = Hash(key,H->TableSize);
	//如果已经在相同下标的散列表上有值，那就不管了
	if(H->TheCells[index].Info != Emtry){
		return H;
	}
	H->Capacity++;
	H->TheCells[index].Element = key;
	H->TheCells[index].Info = Legitimate;
	return H;
}

当散列表的容量超过最大容量是就要使用再散列方法

1
2
3
4
5
6
7
8
9
10
HashTable Rehash(HashTable H){
	if(H == NULL) return NULL;
	HashTable T = InitializeTable(H->TableSize << 1,H->LocalFacotr);
	for(int i = 0;i < H->TableSize;i++){
		if(H->TheCells[i].Element != 0)
			Insert(H->TheCells[i].Element,T);
	}
	DestroyTable(H);
	return T;
}

参考源码