您的位置: 首页  >  文章  >  闭散列法处理哈希冲突

闭散列法处理哈希冲突

分类: 文章 • 2024-05-07 08:37:58

通常，我们所谓的哈希冲突可以定义为对于两个不相等的数据元素 i和 j，将他们代入哈希函数hashFunc有： 
            hashFunc(i) == hashFunc(j)
            即不同关键字通过相同哈希函数计算出相同的哈希地址，对于哈希冲突的处理方法，通常有两种：闭散列法和开散列法，本文先介绍闭散列法，也叫开放地址法。当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把关键字key存放到表中“下一个位置“。

首先定义一个哈希表结构体HashTable，结构体里面包含储存关键字key集合的数组table，数组元素的个数size，数组的容量capacity和所设计的哈希函数hashFunc。采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。这里将数组table中的每个位置当前状况采用标一种枚举类型的state来标注，state分为三种状态：删除DELETED,存在EXIST和空白EMPTY。同时，将数组table定义为一种包含关键字key和枚举state的Element结构体类型。相关代码如下：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef  int  Key;

typedef  enum
{
	EMPTY,
	EXIST,
	DELETED
}State;

typedef struct  Element{
	Key   key;
	State   state;
}Element;

typedef   int ( *HashFuncType)(Key key, int capacity);

typedef   struct  HashTable
{
	Element *table;
	int size;//数据个数
	int capacity;//容量
	HashFuncType   hashFunc;//哈希函数
}HashTable;

对于哈希表结构体的初始化和销毁，代码如下：

//初始化
void   HashInit(HashTable *pHT, int capacity, HashFuncType hashFunc)
{
	pHT->table = (Element *)malloc(sizeof(Element)*capacity);
	assert(pHT->table);
	pHT->size = 0;
	pHT->capacity = capacity;
	pHT->hashFunc = hashFunc;

	for (int i = 0; i < capacity; i++)
	{
		pHT->table[i].state = EMPTY;
	}
}

//销毁
void Destory(HashTable *pHT)
{
	free(pHT->table);
}

这里对于哈希函数的定义采用除留余数法，代码如下：


int hashFunc(Key key, int capacity)
{
	return key%capacity;
}

          当发生哈希冲突时，如果哈希表未被装满，把key存放到表中“下一个” 空位中去 ，对于寻找下一个空余位置，有两种方法，首先介绍第一种方法——一次线性探测法，当插入时，从发生冲突的位置开始，依次继续向后探测，如果该位置中有元素且和待插入元素key相同，则不用插入；如果该位置中有元素但不是待插入元素则发生哈希冲突，使用线性探测找到下一个空位置，插入新元素key。采用一次线性探测，发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”。解决办法把数组的容量capacity扩容为原来的2倍。扩充的前提条件是散列表的负载因子不小于7。负载因子可定义为

        闭散列法处理哈希冲突

即pHT->size*10/pHT->capacity<7。

一次线性探测插入的代码如下：

//插入
//key重复不允许插入
void ExpandIfRequired(HashTable *pHT)
{
	//不扩容
	if (pHT->size*10/pHT->capacity<7)
	{
		return;
	}
	//需要扩容
	int newCapacity = pHT->capacity * 2;
	HashTable newHT;
	HashInit(&newHT, newCapacity, pHT->hashFunc);
    //将旧数组中的数据搬移到新数组中
	for (int i = 0; i < pHT->capacity; i++)
    {
		if (pHT->table[i].state == EXIST)
		{
			HashInsert(&newHT, pHT->table[i].key);
		}
	}
	free(pHT->table);
	pHT->table = newHT.table;
	pHT->capacity = newHT.capacity;
}

int HashInsert(HashTable *pHT, Key key)
{
	ExpandIfRequired(pHT);
	int index = pHT->hashFunc(key, pHT->capacity);
	while (1)
	{
		if (pHT->table[index].key == key
			&&pHT->table[index].state == EXIST)
		{
			return 0;
		}
		if (pHT->table[index].state != EXIST)
		{
			pHT->table[index].key = key;
			pHT->table[index].state = EXIST;
			pHT->size++;
			return 1;
		}
		index = (index + 1) % pHT->capacity;
	}

	return 0;
}

     对于插入我的测试代码如下：

void   test()
{
	HashTable ht;
	HashInit(&ht, 10, hashFunc);

	HashInsert(&ht, 1);
	HashInsert(&ht, 11);
	HashInsert(&ht, 21);
	HashInsert(&ht, 31);
	HashInsert(&ht, 41);
	HashInsert(&ht, 51);
	HashInsert(&ht, 61);
	HashInsert(&ht, 71);
	HashInsert(&ht, 81);
	
	Destory(&ht);
}

     下面是测试行结果

闭散列法处理哈希冲突

对于关键字的查找，如果找到关键字返回其所在位置下标，否则返回0，代码如下：

//查找
int HashSearch1(HashTable *pHT, Key key)
{
	int index = pHT->hashFunc(key, pHT->capacity);
	while ((pHT->table[index].state) != EMPTY)
	{
		if (pHT->table[index].key == key&&pHT->table[index].state == EXIST)
		{
			return index;
		}
		else
			index = (index + 1) % pHT->capacity;
	}
	//没找到
	return 0;
}

对于关键字的删除，当查找到要删除的关键字时，只需将这个位置的状态置为删除DELETED。如果删除失败，则返回0。代码如下：

void HashTableRemove(HashTable *pHT, Key key)
{
	int index = pHT->hashFunc(key, pHT->capacity);
	while ((pHT->table[index].state) !=EMPTY)
	{
		if (pHT->table[index].key == key&&pHT->table[index].state == EXIST)
		{
			pHT->table[index].state = DELETED;
			return 1;
		}
		else
			index = (index + 1) % pHT->capacity;
	}
	return 0;
}

接下来的第二种方法是二次探测法，二次探测法相对于一次探测法，优点在于解决了一次探测数据“堆积”的问题。。二次探测法的下一个空位计算方式为index = (oindex + i*i) % pHT->capacity，其中i代表查找次数，oindex代表上一找到的位置。这里只叙述二次探测法查找代码，其代码如下：

int HashSearch2(HashTable *pHT, Key key)
{
	int oindex = pHT->hashFunc(key, pHT->capacity);//i-1次查找的的元素下标
	int index = oindex;
	int i = 1;//i代表查找次数
	while ((pHT->table[index].state) != EMPTY)
	{
		if (pHT->table[index].key == key&&pHT->table[index].state == EXIST)
		{
			return index;
		}
		//二次探测法变化的位置
		index = (oindex + i*i) % pHT->capacity;
		i++;
	}
	//没找到
	return 0;
}

 

相关推荐