再散列和可扩散列

再散列：

当使用开放定址法时，所有的关键字都存在数组中，但是数组的大小是固定的，而数据量可能会逐渐增加，当数组中存放的关键字大于一半时，即λ>0.5时，对其进行插入、查找等 *** 作的耗时就会增加，这会降低程序的性能。那么这时候，我们建立一个新的大小是原表大小两倍（大小为素数）的散列表，将原表中的数据重新散列到新表中，并继续使用新表。但是由于再散列需要开辟新的空间，这是一个耗时的 *** 作，所以只有当再散列只是程序的一小部分时，才不会对程序的性能造成太大影响。当再散列应用在交互中时，新空间的开辟以及原数据的转移可能会使用户感到明显的延迟。

再散列有三种方式：

1.当装填因子0.5" src="https://latex.codecogs.com/gif.latex?%5Clambda%20%3E0.5" />时再散列

2.当一次插入失败时再散列

3.在超过指定的装填因子时再散列

在一次插入失败之前，表的装填因子就有可能过大，以至于前面的一些 *** 作已经变得非常低效，并且在之前的分析中，当时，散列表还有着很好的性能，所以使用方式1或是3是比较好的。

//散列：再散列
//再散列即当需要的时候，重新建立一个散列表，并将原来的散列表数据拷贝过来
#include 
#include 
#include 

#define empty -1

typedef struct hashlist {
	int size;
	int* val;
}hl;

int nextprime(int doublesize) {
	int flag = 1;
	for (int i = doublesize + 1;; i++) {
		flag = 1;
		for (int j = 2; j <= sqrt(i); j++) {
			if (i % j == 0) {
				flag = 0;
				break;
			}
		}
		if (flag == 1) {
			return i;
		}
	}
}

hl* CreatHashlist() {
	hl* p = (hl*)malloc(sizeof(hl));
	if (p == NULL) {
		printf("内存不足\n");
		return NULL;
	}
	int sizet = 10;
	p->size = sizet;
	p->val = (int*)malloc(sizeof(int) * p->size);
	for (int i = 0; i < p->size; i++) {
		p->val[i] = empty;
	}
	return p;
}

hl* rehash(hl* p) {//再散列，实际上就是重新建立一个二倍大小的散列表，并将数据拷贝过来，只是需要重新设置散列函数，在这里使用了相同的散列函数
	int oldsize = p->size;
	int* olddata = p->val;
	int newsize = nextprime(2 * oldsize);
	p->size = newsize;
	p->val = (int*)malloc(sizeof(int) * p->size);
	for (int i = 0; i < oldsize; i++) {
		p->val[i] = olddata[i];
	}
	for (int i = oldsize; i < newsize; i++) {
		p->val[i] = empty;
	}
	return p;
}

int hash(hl* p, int i) {//
	return i % p->size;
}

int hash1(hl* p, int i, int j) {
	return hash(p, i) + (j * (i+1)) % p->size;
}

void insert(hl* p, int x) {
	for (int j = 0;; j++) {
		int index = hash1(p, x, j);
		if (p->val[index] == empty) {
			p->val[index] = x;
			break;
		}
	}
}

int* find(hl* p,int x) {//找到x第一次出现的地址
	for (int j = 0;; j++) {
		int index = hash1(p, x, j);
		if (p->val[index] == empty || p->val[index] == x) {
			return p->val+index;
		}
	}
}

void delete(hl* p, int x) {
	//对于开放定址法，删除最好使用懒惰删除，只需要给要删除元素做一个记号
	//这只需要使用find找到该元素即可，正常的删除会使表中出现空位置，可能会导致find失败
}

int main() {
	hl* phl = CreatHashlist();
	for (int i = 0; i < 10; i++) {//插入0-10
		insert(phl, i);
	}

	phl = rehash(phl);

	for (int i = 43; i <= 53; i++) {
		insert(phl, i);
	}

	printf("%d\n", *find(phl, 45));

	return 0;
}

可扩散列：

在数据量过大以至于无法放入主存中时，数据就需要存储在外存中（硬盘等）。如果使用之前的方式来实现散列，假设一次find需要探测散列中的三个元素，那么当数据放入外存中时，一次find就需要访问3次硬盘，但访问硬盘是一个开销很大的 *** 作，这时候为了提高程序的性能，借鉴了B树的结构，定义了可扩散列。可扩散列允许使用两次硬盘访问来执行find *** 作。除叶子节点外的节点都用来存放索引信息，当目录较小时，可以直接放在主存中，那么只需要根据目录找到相应位置，只需要一次硬盘访问就能找到对应元素，当目录过大不能放入主存时，就需要将一部分目录放入外存中，这时候就需要两次访问来执行find。