哈希

  • 哈希概念

  • 顺序搜索以及二叉树搜索树中,元素存储位置和元素各关键码之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的 多次比较。搜索的效率取决于搜索过程中元素的比较次数。

  • 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。

  • 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通
    过该函数可以很快找到该元素。

  • 当向该结构中:

    • 插入元素时:根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
    • 搜索元素时:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键 码相等,则搜索成功
  • 该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者
    称散列表)

例如:数据集合{180,750,600,430,541,900,460}
数据结构---哈希表的认识-LMLPHP

  • 用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快
  • 问题:按照上述哈希方式,向集合中插入元素443,会出现什么问题?

哈希冲突

  • 对于两个数据元素的关键字 和 (i != j),有Ki != Kj,但有: HashFun(Ki) == HashFun(Kj)
  • 即不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地 址的数据元素称为“同义词”。

发生哈希冲突该如何处理呢?

哈希函数

  • 引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 哈希函数设计原则:
    • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
    • 哈希函数计算出来的地址能均匀分布在整个空间中
    • 哈希函数应该比较简单

【常见哈希函数】

  • 直接定制法
  • 取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
  • 优点:简单、均匀
  • 缺点:需要事先知道关键字的分布情况
  • 适合查找比较小且连续的情况
  • 面试题:找出一个字符串中第一个只出现一次的字符,要求:时间复杂度O(N),空间复杂度O(1)
  • 除留余数法
  • 设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key %
    p(p<=m),将关键码转换成哈希地址
  • 平方取中法
  • 假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址;
  • 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址
  • 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况
  • 折叠法
  • 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表 长,取后几位作为散列地址
  • 折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况
  • 随机数法
  • 选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数
  • 通常应用于关键字长度不等时采用此法
  • 数学分析法
  • 设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。例如:
    数据结构---哈希表的认识-LMLPHP
  • 假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前7位都是 相同的,那么我们可以选择后面的四位作为散列地址,如果这样的抽取工作还容易出现 冲突,还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法
  • 数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

处理哈希冲突

  • 解决哈希冲突两种常见的方法是:闭散列和开散列
  • 闭散列
  • 闭散列:也叫开放地址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到表中 “下一个”空位中去

那如何寻找下一个空余位置?

  • 线性探测

  • 设关键码集合为{37, 25, 14, 36, 49, 68, 57, 11},散列表为HT[12],表的大小m =
    12,假设哈希函数为:Hash(x) = x % p(p = 11,是最接近m的质数),就有:

  • Hash(37) = 4

  • Hash(25) = 3

  • Hash(14) = 3

  • Hash(36) = 3

  • Hash(49) = 5

  • Hash(68) = 2

  • Hash(57) = 2

  • Hash(11) = 0

  • 其中25,14,36以及68,57发生哈希冲突,一旦冲突必须要找出下一个空余位置

  • 线性探测找的处理为:从发生冲突的位置开始,依次继续向后探测,直到找到空位置为止

  • 【插入】

  • 1、使用哈希函数找到待插入元素在哈希表中的位置

  • 2、如果该位置中没有元素则直接插入新元素;如果该位置中有元素且和待插入元素相同,则不用插入;如果该位置中有元素但不是待插入元素则发生哈希冲突,使用线性探测找到下一个空位置,插入新元素;

  • 采用线性探测处理哈希冲突:
    数据结构---哈希表的认识-LMLPHP

  • 采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。为什么?那该 怎么来删除?

  • 采用线性探测,实现起来非常简单,缺陷是:

  • 一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即:不同关键码占据了可利用的空位置,使得寻找某关键
    码的位置需要许多次比较,导致搜索效率降低。

  • 如何缓解呢?

  • 负载因子
    数据结构---哈希表的认识-LMLPHP

  • 二次探测

  • 发生哈希冲突时,二次探查法在表中寻找“下一个”空位置的公式为:Hi = ( H0 + i^2 ) % m , Hi = (H0 - i ^2 ) % m, i = 1,2,3…, (m-1) / 2H0 是通过散列函数Hash(x)对元素的关键码 key 进行计算得 到的位置,m是表的大小

  • 假设数组的关键码为37, 25, 14, 36, 49, 68, 57, 11,取m =
    19,这样可设定为HT[19],采用散列函数Hash(x) = x % 19,则:

    • Hash(37)=18
    • Hash(25)=6
    • Hash(14)=14
    • Hash(36)=17
    • Hash(49)=11
    • Hash(68)=11
    • Hash(57)=0
    • Hash(11)=11
  • 采用二次探测处理哈希冲突:
    数据结构---哈希表的认识-LMLPHP

  • 研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只
    要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过
    0.5;如果超出必须考虑增容

  • 开散列

  • 开散列法又叫链地址法(开链法)。

  • 开散列法:首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个
    桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。

  • 设元素的关键码为37, 25, 14, 36, 49, 68, 57, 11,
    散列表为HT[12],表的大小为12,散列函数为Hash(x) = x % 11
    - Hash(37)=4
    - Hash(25)=3
    - Hash(14)=3
    - Hash(36)=3
    - Hash(49)=5
    - Hash(68)=2
    - Hash(57)=2
    - Hash(11)=0

  • 使用哈希函数计算出每个元素所在的桶号,同一个桶的链表中存放哈希冲突的元素。
    数据结构---哈希表的认识-LMLPHP

  • 通常,每个桶对应的链表结点都很少,将n个关键码通过某一个散列函数,存放到散列表中的m个桶中,那么每一个桶中链表的平均 长度为 n/m 。以搜索平均长度为 n/m 的链表代替了搜索长度为 n 的顺序表,搜索效率快的多。

  • 应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。事实上:

  • 由于开地址法必须保持大量的空闲空间以确保搜索效率,如二次探查法要求装载因子a <= 0.7,而表项所占空间又比指针大的多,

  • 所以使用链地址法反而比开地址法节省存储空间

好了,废话了这么多,接下来该代码了,我实现了哈希的一个闭散列和一个开散列。

  • 多废话一句,哈希这块代码特别简单,主要是对于哈希的理解和自我的认识挺重要的。

  • 闭散列的代码实现

  • 首先是我定义的闭散列的结构体:由于我在哈希中存的是字符串,所以讲 char* 重定义成 HTDataType;对于存的所有元素还必须标明他的状态,所以我用枚举类型,分别定义,EMPTY为空,EXIST为存在,DELETE为删除。还有我们约定哈希表中所存元素都是唯一的。至于PDTInt 这个函数指针则是为了输出字符串在哈希表中所存的位置,到时候会在哈希函数中用到。结构体中 capacity 代表我的哈希表当前的容量,size 代表哈希表中有效的元素个数,也就是存在的元素,而 total 则代表的是哈希表中存在的元素和被删除的元素之和。注意:每个元素不仅仅要存元素,还要存这个元素的状态,因此我们用一个结构体来定义。

typedef char* HTDataType;
typedef int(*PDTInt)(HTDataType data);

typedef enum
{
	EMPTY,
	EXIST,
	DELETE
}State;

typedef struct HTElem
{
	HTDataType _data;
	State _state;
}HTElem;

// 约定:哈希表格中的元素是唯一的
typedef struct HashTable
{
	HTElem* _ht;
	int _capacity;
	int _size;  // 哈希表中有效元素的个数
	int _total; // EXIST 和 DELETE
	PDTInt _PDTInt;

}HashTable, HT;
  • 初始化哈希表:没什么说的,日常操作
void InitHashTable(HT* pHT, int capacity, PDTInt pDTInt)
{
	assert(pHT);
	capacity = GetNextPrime(capacity);
	pHT->_ht = (HTElem*)malloc(capacity*sizeof(HTElem));
	if (!pHT->_ht)
	{
		assert(0);
		return;
	}
	for (int i = 0; i < capacity; i++)
		pHT->_ht[i]._state = EMPTY;

	pHT->_capacity = capacity;
	pHT->_PDTInt = pDTInt;
	pHT->_size = 0;
	pHT->_total = 0;
}
  • 检查哈希容量:由于闭散列中加入了负载因子,因此如果所存元素个数除以容量大于负载因子的话,就加大空间。否则就不动。如果开辟的话,那么原来空间的元素就需要插入到新的哈希表,其中只插入存在的元素即可。我说的重新插入可不是搬移,需要向哈希表中插元素一样,一个一个插,因为容量变化的话,不同的哈希表所对应的哈希函数所求的地址就会变。
  • 还有一点就是,我这儿用到线性探测和二次探测。总体来说,二次探测更好一些,因为线性探测如果一个位置发生“堵车”,那么接下来会越来越堵,时间复杂度会提高很多。
  • 还有别忘了,先释放旧空间,然后在将新开辟的空间赋过去。
void _CheckCapacity(HashTable* pHT)
{
	int hashAddr = 0;
	assert(pHT);
	if (pHT->_total / pHT->_capacity > 7)
	{
		int old_capacity = pHT->_capacity;
		int new_capacity = GetNextPrime(old_capacity * 2);
		HTElem* new_ht = (HTElem*)malloc(new_capacity*sizeof(HTElem));
		if (!new_ht)
		{
			assert(0);
			return;
		}

		for (int i = 0; i < new_capacity; i++)
			new_ht[i]._state = EMPTY;

		for (int i = 0; i < old_capacity; i++)
		{
			if (EXIST != pHT->_ht[i]._state)
				continue;

			hashAddr = HashFunc(pHT, pHT->_ht[i]._data);
#if 0
			if (EMPTY != pHT->_ht[i]._state)
			{
				//线性探测
				hashAddr++;
#else

				//二次探测
				hashAddr = hashAddr + 2 * i + 1;
				if (hashAddr == new_capacity)
					hashAddr = 0;
#endif
			}
			new_ht[hashAddr]._data = pHT->_ht[i]._data;
			new_ht[hashAddr]._state = EXIST;
		}
		// 3. 释放就空间
		free(pHT->_ht);
		pHT->_ht = new_ht;
		pHT->_total = pHT->_size;
	}
}

  • 向哈希表中插入元素:这个函数最重要的是寻找要插入的位置,根据我们的约定,哈希表中不能出现重复元素,那么如果表中元素和插入元素有相同,就不插入。还有一点,插入之前应该先检查容量是否足够。

int InsertHashTable(HT* pHT, HTDataType data)
{
	assert(pHT);
	_CheckCapacity(pHT);
	int hasAddr = HashFunc(pHT, data);

	while (EXIST == pHT->_ht[hasAddr]._state)
	{
		if (EXIST == pHT->_ht[hasAddr]._state && data == pHT->_ht[hasAddr]._data)
			return 0;
#if 0
		//线性探测
		hasAddr++;
		if (hasAddr == pHT->_capacity)
			hasAddr = 0;
#else
		//二次探测
		int i = 0;
		hasAddr = hasAddr + 2*i + 1;
		hasAddr %= pHT->_capacity;
#endif
	}
	pHT->_ht[hasAddr]._data = data;
	pHT->_ht[hasAddr]._state = EXIST;
	pHT->_size++;
	pHT->_total++;
	return 1;
}
  • 删除表中元素:实现这个功能我们可以用寻找表中元素这个函数,如果找不到那么就不删除,找到了就删除。
int DeleteHashTAble(HT* pHT, HTDataType data)
{
	int hasAddr = FindHashTable(pHT, data);
	if (-1 != hasAddr)
	{
		pHT->_ht[hasAddr]._state = DELETE;
		pHT->_size -= 1;
		return 1;
	}
	return 0;
}
  • 寻找一个表中元素:思路是利用哈希函数还有二次探测法找元素,找元素必须满足元素相等并且这个元素的状态必须是存在的。
int FindHashTable(HT* pHT, HTDataType data)
{
	int hasAddr = HashFunc(pHT, data);
	int i = 0;
	while (pHT->_ht[hasAddr]._state != EMPTY)
	{
		if (pHT->_ht[hasAddr]._state == EXIST && pHT->_ht[hasAddr]._data == data)
			return hasAddr;

#if 0
		//线性探测
		hasAddr++;
		if (hasAddr == pHT->_capacity)
			hasAddr = 0;
#else
		//二次探测
		hasAddr = hasAddr + 2 * i + 1;
		hasAddr %= pHT->_capacity;
#endif
	}
	return -1;
}
  • 哈希函数
int HashFunc(HashTable* pHT, HTDataType data)
{
	assert(pHT);
	return pHT->_PDTInt(data) % pHT->_capacity;
}
  • 下面的几个函数比较简单,我就不一一解释了,有判空函数;获取哈希表中元素个数;删除这个哈希表。
int EmptyHashTable(HT* pHT)
{
	assert(pHT);
	return 0 == pHT->_size;
}


int SizeHashTAble(HT* pHT)
{
	assert(pHT);
	return pHT->_size;
}

void DestroyHashTable(HashTable* pHT)
{
	free(pHT->_ht);
	pHT->_ht = NULL;
	pHT->_capacity = 0;
	pHT->_size = 0;
	pHT->_total = 0;
}
  • 经过研究发现,使用素数当做容量,可以有效的降低哈希冲突。那么我的容量就是用这个函数获取的。
unsigned long GetNextPrime(unsigned long prime)
{
	static unsigned long _PrimeList[PRIME_SIZE] =
	{
		53ul, 97ul, 193ul, 389ul, 769ul,
		1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
		49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
		1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
		50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
		1610612741ul, 3221225473ul, 4294967291ul
	};

	int i = 0;
	for (; i < PRIME_SIZE; ++i)
	{
		if (_PrimeList[i] > prime)
			return _PrimeList[i];
	}

	return _PrimeList[PRIME_SIZE - 1];
}

  • 这个函数是将传进来的字符串转换成数字。用途就是讲存入哈希表中的字符串通过哈希函数变成在哈希表的位置。
unsigned long StrToINT(const char * str)
{
	unsigned int seed = 131; // 31 131 1313 13131 131313
	unsigned int hash = 0;
	while (*str)
	{
		hash = hash * seed + (*str++);
	}
	return (hash & 0x7FFFFFFF);
}
  • 我的测试函数

void TestHashTable()
{
	HashTable ht;
	InitHashTable(&ht, 10, StrToINT);
	InsertHashTable(&ht, "9527");
	InsertHashTable(&ht, "秋香");
	InsertHashTable(&ht, "石榴姐");
	InsertHashTable(&ht, "管家");

	printf("%d\n", SizeHashTAble(&ht));

	if (-1 != FindHashTable(&ht, "石榴姐"))
		printf("是 唐伯虎点秋香中的人物\n");
	else
		printf("不是 唐伯虎点秋香中的人物\n");

	if (-1 != FindHashTable(&ht, "轮轮"))
		printf("是 唐伯虎点秋香中的人物\n");
	else
		printf("不是 唐伯虎点秋香中的人物\n");

	DestroyHashTable(&ht);
}

开散列(也叫哈希桶)

  • 定义的结构体:用到链表就先封装一个链表。然后哈希表中存的是链表的头结点的地址。

typedef int HBDataType;

typedef struct HashBucketNode
{
	struct HashBucketNode* _pNext;
	HBDataType _data;
}Node, *PNode;


typedef struct HashBucket
{
	PNode* _table;
	int _capacity;
	int _size;
}HashBucket;
  • 初始化哈希桶:容量还是由获取素数函数决定,有一点就是,哈希桶放的元素是链表的头结点,那么刚开始的时候我们需要把头结点置为空。
void InitHashBucket(HashBucket* pHB, int capacity)
{
	assert(pHB);
	capacity = GetNextPrime(capacity);
	pHB->_table = (PNode*)malloc(capacity*sizeof(PNode));
	if (!pHB->_table)
	{
		assert(0);
		return;
	}

	for (int i = 0; i < capacity; i++)
		pHB->_table[i] = NULL;

	pHB->_size = 0;
	pHB->_capacity = capacity;
}
  • 向哈希表中插入元素:为元素在哈希桶找到位置后,我们采用链表的头插法来插入元素。注意一点就是插入时如果有相同元素就不插入,如果那个位置为空,就是那里还没有元素话,一定区别对待。
PNode BuyHashBucketNode(HBDataType data)
{
	PNode new_node = (PNode)malloc(sizeof(Node));
	if (!new_node)
	{
		assert(0);
		return;
	}
	new_node->_data = data;
	new_node->_pNext = NULL;

}

int InsertHashBucket(HashBucket* pHB, HBDataType data)
{
	assert(pHB);
	int bucketNo = HashFuncBucket(pHB, data);
	PNode pCur = pHB->_table[bucketNo];

	while (pCur != NULL)
	{
		if (data == pCur->_data)
			return 0;
		pCur = pCur->_pNext;
	}

	//头插法
	pCur = BuyHashBucketNode(data);
	pCur->_pNext = pHB->_table[bucketNo];
	pHB->_table[bucketNo] = pCur;
	pHB->_size++;
	return 1;
}
  • 删除哈希桶的一个节点:删除时一定要注意这个元素在哈希表中是否存在,还有就是被删除元素是头节点和其他节点需要区别对待。

int DeleteHashBucket(HashBucket* pHB, HBDataType data)
{
	int bucketNo = HashFuncBucket(pHB, data);
	PNode pCur = NULL;
	PNode pPrev = NULL;
	assert(pHB);

	pCur = pHB->_table[bucketNo];

	if (pCur == NULL)
		return 0;

	//删除头结点
	if (pCur->_data == data)
	{
		pHB->_table[bucketNo] = pCur->_pNext;
		free(pCur);
		pCur = NULL;
		pHB->_size--;
		return 1;
	}

	while (pCur != NULL)
	{
		if (data == pCur->_data)
			break;
		pPrev = pCur;
		pCur = pCur->_pNext;
	}

	if (pCur == NULL)
		return 0;

	pPrev->_pNext = pCur->_pNext;
	free(pCur);
	pCur = NULL;
	pHB->_size--;
	return 1;
}
  • 在哈希表找一个元素:底层也就是链表的代码,没有什么说的。
int FindHashBucket(HashBucket* pHB, HBDataType data)
{
	assert(pHB);
	int bucketNo = HashFuncBucket(pHB, data);
	PNode pCur = NULL;

	pCur = pHB->_table[bucketNo];
	while (pCur != NULL)
	{
		if (data == pCur->_data)
			return 1;
		pCur = pCur->_pNext;
	}
	return 0;
}
  • 销毁整个哈希表:在销毁整个哈希表时我们需要注意,每一个桶中都是一条链表,因此需要我们注意,销毁完每一条链表后,在来销毁所有桶。
void MoveLinkList(PNode* pHead)
{
	PNode pCur = NULL;
	PNode pPrev = NULL;
	pCur = *pHead;
	while (pCur != NULL)
	{
		pPrev = pCur->_pNext;
		free(pCur);
		pCur = NULL;
		pCur = pPrev;
	}
}

int DestroyHashBucket(HashBucket* pHB, HBDataType data)
{
	assert(pHB);
	for (int i = 0; i < pHB->_capacity; i++)
	{
		MoveLinkList(&pHB->_table[i]);
	}
	free(pHB->_table);
	pHB->_table = NULL;
	pHB->_capacity = 0;
	pHB->_size = 0;
}
  • 哈希函数
int HashFuncBucket(HashBucket* pHB, HBDataType data)
{
	assert(pHB);
	return data %= pHB->_capacity;
}
  • 下面的两个小函数比较简单:一个判空函数和一个求哈希表中元素个数。
int EmptyHashBucket(HashBucket* pHB)
{
	assert(pHB);
	return 0 == pHB->_size;
}

int SizeHashBucket(HashBucket* pHB)
{
	assert(pHB);
	return pHB->_size;
}

 - 我的检测函数

void TestHashBucket()
{
HashBucket pHB;
InitHashBucket(&pHB, 10);

printf("哈希表%s空\n", EmptyHashBucket(&pHB) == 1 ? "为" : "不为");

printf("%s\n", InsertHashBucket(&pHB, 35) ? "插入成功" : "插入失败");
printf("%s\n", InsertHashBucket(&pHB, 87) ? "插入成功" : "插入失败");
printf("%s\n", InsertHashBucket(&pHB, 36) ? "插入成功" : "插入失败");
printf("%s\n", InsertHashBucket(&pHB, 90) ? "插入成功" : "插入失败");
printf("%s\n", InsertHashBucket(&pHB, 24) ? "插入成功" : "插入失败");
printf("%s\n", InsertHashBucket(&pHB, 46) ? "插入成功" : "插入失败");
printf("%s\n", InsertHashBucket(&pHB, 12) ? "插入成功" : "插入失败");
printf("%s\n", InsertHashBucket(&pHB, 12) ? "插入成功" : "插入失败");
printf("%s\n", InsertHashBucket(&pHB, 99) ? "插入成功" : "插入失败");
printf("%s\n", InsertHashBucket(&pHB, 99) ? "插入成功" : "插入失败");
printf("%s\n", InsertHashBucket(&pHB, 99) ? "插入成功" : "插入失败");


printf("哈希表%s空\n", EmptyHashBucket(&pHB) == 1 ? "为" : "不为");
printf("哈希表中元素个数:%d \n", SizeHashBucket(&pHB));

printf("%s\n", FindHashBucket(&pHB, 24) ? "找到了" : "没找到");
printf("%s\n", FindHashBucket(&pHB, 46) ? "找到了" : "没找到");
printf("%s\n", FindHashBucket(&pHB, 120) ? "找到了" : "没找到");

printf("%s\n", DeleteHashBucket(&pHB, 24) ? "删除成功" : "删除失败");
printf("%s\n", DeleteHashBucket(&pHB, 46) ? "删除成功" : "删除失败");
printf("%s\n", DeleteHashBucket(&pHB, 100) ? "删除成功" : "删除失败");

printf("%s\n", FindHashBucket(&pHB, 24) ? "找到了" : "没找到");
printf("%s\n", FindHashBucket(&pHB, 46) ? "找到了" : "没找到");
printf("%s\n", FindHashBucket(&pHB, 120) ? "找到了" : "没找到");

}


最后我附上我的所有代码

common.h


#define PRIME_SIZE  28
unsigned long GetNextPrime(unsigned long prime);
unsigned long StrToINT(const char * str);




unsigned long GetNextPrime(unsigned long prime)
{
	static unsigned long _PrimeList[PRIME_SIZE] =
	{
		53ul, 97ul, 193ul, 389ul, 769ul,
		1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
		49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
		1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
		50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
		1610612741ul, 3221225473ul, 4294967291ul
	};

	int i = 0;
	for (; i < PRIME_SIZE; ++i)
	{
		if (_PrimeList[i] > prime)
			return _PrimeList[i];
	}

	return _PrimeList[PRIME_SIZE - 1];
}


unsigned long StrToINT(const char * str)
{
	unsigned int seed = 131; // 31 131 1313 13131 131313
	unsigned int hash = 0;
	while (*str)
	{
		hash = hash * seed + (*str++);
	}
	return (hash & 0x7FFFFFFF);
}


闭散列 HashTable.h

#pragma once
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include"common.h"

//typedef int HTDataType;
typedef char* HTDataType;
typedef int(*PDTInt)(HTDataType data);

typedef enum
{
	EMPTY,
	EXIST,
	DELETE
}State;

typedef struct HTElem
{
	HTDataType _data;
	State _state;
}HTElem;

// 约定:哈希表格中的元素是唯一的
typedef struct HashTable
{
	HTElem* _ht;
	int _capacity;
	int _size;  // 哈希表中有效元素的个数
	int _total; // EXIST 和 DELETE
	PDTInt _PDTInt;

}HashTable, HT;



void InitHashTable(HT* pHT, int capacity, PDTInt pDTInt);
int InsertHashTable(HT* pHT, HTDataType data);
int DeleteHashTAble(HT* pHT, HTDataType data);
int FindHashTable(HT* pHT, HTDataType data);
int EmptyHashTable(HT* pHT);
int SizeHashTAble(HT* pHT);
int HashFunc(HashTable* pHT, HTDataType data);
void _CheckCapacity(HashTable* pHT);
void DestroyHashTable(HashTable* pHT);



void InitHashTable(HT* pHT, int capacity, PDTInt pDTInt)
{
	assert(pHT);
	capacity = GetNextPrime(capacity);
	pHT->_ht = (HTElem*)malloc(capacity*sizeof(HTElem));
	if (!pHT->_ht)
	{
		assert(0);
		return;
	}
	for (int i = 0; i < capacity; i++)
		pHT->_ht[i]._state = EMPTY;

	pHT->_capacity = capacity;
	pHT->_PDTInt = pDTInt;
	pHT->_size = 0;
	pHT->_total = 0;
}

void _CheckCapacity(HashTable* pHT)
{
	int hashAddr = 0;
	assert(pHT);
	if (pHT->_total / pHT->_capacity > 7)
	{
		int old_capacity = pHT->_capacity;
		int new_capacity = GetNextPrime(old_capacity * 2);
		HTElem* new_ht = (HTElem*)malloc(new_capacity*sizeof(HTElem));
		if (!new_ht)
		{
			assert(0);
			return;
		}

		for (int i = 0; i < new_capacity; i++)
			new_ht[i]._state = EMPTY;

		for (int i = 0; i < old_capacity; i++)
		{
			if (EXIST != pHT->_ht[i]._state)
				continue;

			hashAddr = HashFunc(pHT, pHT->_ht[i]._data);

			if (EMPTY != pHT->_ht[i]._state)
			{
				//线性探测
				hashAddr++;


				//二次探测
				hashAddr = hashAddr + 2 * i + 1;
				if (hashAddr == new_capacity)
					hashAddr = 0;
			}
			new_ht[hashAddr]._data = pHT->_ht[i]._data;
			new_ht[hashAddr]._state = EXIST;
		}
		// 3. 释放就空间
		free(pHT->_ht);
		pHT->_ht = new_ht;
		pHT->_total = pHT->_size;
	}
}

int InsertHashTable(HT* pHT, HTDataType data)
{
	assert(pHT);
	_CheckCapacity(pHT);
	int hasAddr = HashFunc(pHT, data);

	while (EXIST == pHT->_ht[hasAddr]._state)
	{
		if (EXIST == pHT->_ht[hasAddr]._state && data == pHT->_ht[hasAddr]._data)
			return 0;
#if 0
		//线性探测
		hasAddr++;
		if (hasAddr == pHT->_capacity)
			hasAddr = 0;
#else
		//二次探测
		int i = 0;
		hasAddr = hasAddr + 2*i + 1;
		hasAddr %= pHT->_capacity;
#endif
	}
	pHT->_ht[hasAddr]._data = data;
	pHT->_ht[hasAddr]._state = EXIST;
	pHT->_size++;
	pHT->_total++;
	return 1;
}


int DeleteHashTAble(HT* pHT, HTDataType data)
{
	int hasAddr = FindHashTable(pHT, data);
	if (-1 != hasAddr)
	{
		pHT->_ht[hasAddr]._state = DELETE;
		pHT->_size -= 1;
		return 1;
	}
	return 0;
}


int FindHashTable(HT* pHT, HTDataType data)
{
	int hasAddr = HashFunc(pHT, data);
	int i = 0;
	while (pHT->_ht[hasAddr]._state != EMPTY)
	{
		if (pHT->_ht[hasAddr]._state == EXIST && pHT->_ht[hasAddr]._data == data)
			return hasAddr;

#if 0
		//线性探测
		hasAddr++;
		if (hasAddr == pHT->_capacity)
			hasAddr = 0;
#else
		//二次探测
		hasAddr = hasAddr + 2 * i + 1;
		hasAddr %= pHT->_capacity;
#endif
	}
	return -1;
}


int EmptyHashTable(HT* pHT)
{
	assert(pHT);
	return 0 == pHT->_size;
}


int SizeHashTAble(HT* pHT)
{
	assert(pHT);
	return pHT->_size;
}


int HashFunc(HashTable* pHT, HTDataType data)
{
	assert(pHT);
	return pHT->_PDTInt(data) % pHT->_capacity;
}

void DestroyHashTable(HashTable* pHT)
{
	free(pHT->_ht);
	pHT->_ht = NULL;
	pHT->_capacity = 0;
	pHT->_size = 0;
	pHT->_total = 0;
}

void TestHashTable()
{
	HashTable ht;
	InitHashTable(&ht, 10, StrToINT);
	InsertHashTable(&ht, "9527");
	InsertHashTable(&ht, "秋香");
	InsertHashTable(&ht, "石榴姐");
	InsertHashTable(&ht, "管家");

	printf("%d\n", SizeHashTAble(&ht));

	if (-1 != FindHashTable(&ht, "石榴姐"))
		printf("是 唐伯虎点秋香中的人物\n");
	else
		printf("不是 唐伯虎点秋香中的人物\n");

	if (-1 != FindHashTable(&ht, "轮轮"))
		printf("是 唐伯虎点秋香中的人物\n");
	else
		printf("不是 唐伯虎点秋香中的人物\n");

	DestroyHashTable(&ht);
}

开散列 HashBucket.h

#pragma once
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include"common.h"

typedef int HBDataType;

typedef struct HashBucketNode
{
	struct HashBucketNode* _pNext;
	HBDataType _data;
}Node, *PNode;


typedef struct HashBucket
{
	PNode* _table;
	int _capacity;
	int _size;
}HashBucket;


void InitHashBucket(HashBucket* pHB, int capacity);
int InsertHashBucket(HashBucket* pHB, HBDataType data);
int DeleteHashBucket(HashBucket* pHB, HBDataType data);
int FindHashBucket(HashBucket* pHB, HBDataType data);
int EmptyHashBucket(HashBucket* pHB);
int SizeHashBucket(HashBucket* pHB);
int DestroyHashBucket(HashBucket* pHB, HBDataType data);
int HashFuncBucket(HashBucket* pHB, HBDataType data);
PNode BuyHashBucketNode(HBDataType data);



void InitHashBucket(HashBucket* pHB, int capacity)
{
	assert(pHB);
	capacity = GetNextPrime(capacity);
	pHB->_table = (PNode*)malloc(capacity*sizeof(PNode));
	if (!pHB->_table)
	{
		assert(0);
		return;
	}

	for (int i = 0; i < capacity; i++)
		pHB->_table[i] = NULL;

	pHB->_size = 0;
	pHB->_capacity = capacity;
}


PNode BuyHashBucketNode(HBDataType data)
{
	PNode new_node = (PNode)malloc(sizeof(Node));
	if (!new_node)
	{
		assert(0);
		return;
	}
	new_node->_data = data;
	new_node->_pNext = NULL;

}

int InsertHashBucket(HashBucket* pHB, HBDataType data)
{
	assert(pHB);
	int bucketNo = HashFuncBucket(pHB, data);
	PNode pCur = pHB->_table[bucketNo];

	while (pCur != NULL)
	{
		if (data == pCur->_data)
			return 0;
		pCur = pCur->_pNext;
	}

	//头插法
	pCur = BuyHashBucketNode(data);
	pCur->_pNext = pHB->_table[bucketNo];
	pHB->_table[bucketNo] = pCur;
	pHB->_size++;
	return 1;
}


int DeleteHashBucket(HashBucket* pHB, HBDataType data)
{
	int bucketNo = HashFuncBucket(pHB, data);
	PNode pCur = NULL;
	PNode pPrev = NULL;
	assert(pHB);

	pCur = pHB->_table[bucketNo];

	if (pCur == NULL)
		return 0;

	//删除头结点
	if (pCur->_data == data)
	{
		pHB->_table[bucketNo] = pCur->_pNext;
		free(pCur);
		pCur = NULL;
		pHB->_size--;
		return 1;
	}

	while (pCur != NULL)
	{
		if (data == pCur->_data)
			break;
		pPrev = pCur;
		pCur = pCur->_pNext;
	}

	if (pCur == NULL)
		return 0;

	pPrev->_pNext = pCur->_pNext;
	free(pCur);
	pCur = NULL;
	pHB->_size--;
	return 1;
}

int FindHashBucket(HashBucket* pHB, HBDataType data)
{
	assert(pHB);
	int bucketNo = HashFuncBucket(pHB, data);
	PNode pCur = NULL;

	pCur = pHB->_table[bucketNo];
	while (pCur != NULL)
	{
		if (data == pCur->_data)
			return 1;
		pCur = pCur->_pNext;
	}
	return 0;
}


int EmptyHashBucket(HashBucket* pHB)
{
	assert(pHB);
	return 0 == pHB->_size;
}

int SizeHashBucket(HashBucket* pHB)
{
	assert(pHB);
	return pHB->_size;
}

void MoveLinkList(PNode* pHead)
{
	PNode pCur = NULL;
	PNode pPrev = NULL;
	pCur = *pHead;
	while (pCur != NULL)
	{
		pPrev = pCur->_pNext;
		free(pCur);
		pCur = NULL;
		pCur = pPrev;
	}
}

int DestroyHashBucket(HashBucket* pHB, HBDataType data)
{
	assert(pHB);
	for (int i = 0; i < pHB->_capacity; i++)
	{
		MoveLinkList(&pHB->_table[i]);
	}
	free(pHB->_table);
	pHB->_table = NULL;
	pHB->_capacity = 0;
	pHB->_size = 0;
}

int HashFuncBucket(HashBucket* pHB, HBDataType data)
{
	assert(pHB);
	return data %= pHB->_capacity;
}

void TestHashBucket()
{
	HashBucket pHB;
	InitHashBucket(&pHB, 10);

	printf("哈希表%s空\n", EmptyHashBucket(&pHB) == 1 ? "为" : "不为");

	printf("%s\n", InsertHashBucket(&pHB, 35) ? "插入成功" : "插入失败");
	printf("%s\n", InsertHashBucket(&pHB, 87) ? "插入成功" : "插入失败");
	printf("%s\n", InsertHashBucket(&pHB, 36) ? "插入成功" : "插入失败");
	printf("%s\n", InsertHashBucket(&pHB, 90) ? "插入成功" : "插入失败");
	printf("%s\n", InsertHashBucket(&pHB, 24) ? "插入成功" : "插入失败");
	printf("%s\n", InsertHashBucket(&pHB, 46) ? "插入成功" : "插入失败");
	printf("%s\n", InsertHashBucket(&pHB, 12) ? "插入成功" : "插入失败");
	printf("%s\n", InsertHashBucket(&pHB, 12) ? "插入成功" : "插入失败");
	printf("%s\n", InsertHashBucket(&pHB, 99) ? "插入成功" : "插入失败");
	printf("%s\n", InsertHashBucket(&pHB, 99) ? "插入成功" : "插入失败");
	printf("%s\n", InsertHashBucket(&pHB, 99) ? "插入成功" : "插入失败");


	printf("哈希表%s空\n", EmptyHashBucket(&pHB) == 1 ? "为" : "不为");
	printf("哈希表中元素个数:%d \n", SizeHashBucket(&pHB));

	printf("%s\n", FindHashBucket(&pHB, 24) ? "找到了" : "没找到");
	printf("%s\n", FindHashBucket(&pHB, 46) ? "找到了" : "没找到");
	printf("%s\n", FindHashBucket(&pHB, 120) ? "找到了" : "没找到");

	printf("%s\n", DeleteHashBucket(&pHB, 24) ? "删除成功" : "删除失败");
	printf("%s\n", DeleteHashBucket(&pHB, 46) ? "删除成功" : "删除失败");
	printf("%s\n", DeleteHashBucket(&pHB, 100) ? "删除成功" : "删除失败");

	printf("%s\n", FindHashBucket(&pHB, 24) ? "找到了" : "没找到");
	printf("%s\n", FindHashBucket(&pHB, 46) ? "找到了" : "没找到");
	printf("%s\n", FindHashBucket(&pHB, 120) ? "找到了" : "没找到");

}

主函数

#define _CRT_SECURE_NO_WARNINGS 1
//#include"hashTable.h"
#include"hashBucket.h"
int main()
{
	//TestHashTable();
	TestHashBucket();
	return 0;
}

哈希时数据结构这儿的重点,以上我总结的比较乱,如果发现错误,欢饮下方讨论。

10-05 15:09