1.基本思想:

有冲突时就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将元素存入.

2.开放地址法的常用方法:

(1) 线性探测法:

Hi=(Hash(key)+di)%m (1<=i<m),其中:m为哈希表长度,di为增量序列1,2,……m-1,且di=i;
其实就是一旦有冲突,就找下一个空地址存入.
线性探测法例题:
关键码集为{47,7,29,11,16,92,22,8,3},散列表长为m=11,散列函数为Hash(key)=key mod 11;拟用线性探测法解决哈希冲突,建立散列表如下:

解释:(1)47 7均是由散列函数得到的没有冲突的散列地址;
(2)Hash(29)=7,散列地址有冲突,需寻找下一个空的散列地址;
由H=(Hash(29)+1)%11=8,散列地址8为空,因此将29存入.
(3)11,16,92均是由散列函数得到的没有冲突的散列地址
(4)22,8,3同样在散列地址上有冲突,也是用线性探测法找到空的散列地址,这里不再赘述.

(2)二次探测法:

Hi=(Hash(key)+di)%m,**其中:m为散列表长度,di为增量序列1^2,-1^2,2^2,-2^2,……q^2**
如下例子:关键码集为{47,7,29,11,16,92,22,8,3},设散列函数为Hash(key)=key%11,
那么以此哈希函数建立的哈希表如下:

其实主要是最后一个3,di=1时有数字,然后di=-1,,这个时候-2地址没有数字,直接存入.

(3) 伪随机探测法:

Hi=(Hash(key)+di)%m (1<=i<m),其中:m为散列表的长度,di为伪随机数.
如何查找?因为是随机存放的,所以查找的时候只能从头开始依次查找.

3.方法总结

1.di是1,2,……m的线性序列就是线性探测法;
di是12,-12,22,-22,32,-32……q^2的二次序列就是二次探测法
di是伪随机序列就是伪随机探测法;

2.开地址法就是这些地址是开放的,都可以用.
那么接下来我们就要依据我们的散列函数来建立我们的哈希表,那么我们开始写代码,主要是先设计结构,然后建立哈希表和查找哈希表.

4.代码实现

#include  <stdio.h>
}

//计算key的哈希值,哈希函数为H(key)=key%p
static   int  H(int key)
{
	return key % p;
}

//将key插入到哈希表ht中,成功返回true,失败返回false
bool  Insert(HashTable ht, int key)
{
	int hi = H(key);//得到key的哈希值;
	if (ht[hi].key == NONE)//当前哈希表没有被使用,将key直接存储
	{
		ht[hi].key = key;
		return true;
	}
	else//在其他位置找合适的位置
	{
		for (int d = 1; d < m; d++)//利用线性探测找位置
		{
			int  newHi = (hi + d) % m;//新的位置
			if (ht[newHi].key == key)//key已经存在,不再另外存储
			{
				return  true;
			}
			else  if (ht[newHi].key == NONE)
			{
				ht[newHi].key = key;
				return true;
			}
		}

		return  false;//存满,没有空位
	}
}


//在哈希表中查找key,找到返回下标,失败返回-1
int  Search(const  HashTable ht, int key)
{
	int hi = H(key);
	for (int i = 0; i < m; i++)
	{
		int newHi = (hi + i) % m;
		if (ht[newHi].key == key)
		{
			return newHi;
		}
		else if (ht[newHi].key == NONE)//没有找到
		{
			break;
		}
	}
	return -1;//失败
}

//从头到尾输出ht的所有值
void   Show(HashTable ht)
{
	for (int i = 0; i < m; i++)
	{
		printf("%d   ", ht[i].key);
	}
	printf("\n");
}

int  main()
{
	HashTable ht;
	InitHashTable(ht);

	int arr[16] = { 3,5,7,1,2,9,28,25,6,11,10,15,17,23,34,19 };
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		Insert(ht, arr[i]);
	}
	Show(ht);

	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d:%d   ", arr[i], Search(ht, arr[i]));
	}

	printf("\n");

	printf("%d  ", Search(ht, 100));
	return 0;
}