哈希桶（开散列）

完整代码块

/***************************************/
//HashBucket.h

#pragma once

typedef int HBDataType;

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

//将data转化成整形数据
typedef int(*PDTInt)(HBDataType data);

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


void InitHashBucket(HashBucket *pHB, int capacity, PDTInt pDTInt);

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);

void DestroyHashBucket(HashBucket *pHB);

int HashFuncBucket(HashBucket *pHB, HBDataType data);

//打印哈希桶元素
void PrintHashbucket(HashBucket *pHB);



/***************************************/
//HashBucket.c
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "Common.h"

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

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

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

PNode BuyHashBucketNode(HBDataType data)
{
	PNode pNewNode = (PNode)malloc(sizeof(Node));
	if (NULL == pNewNode)
	{
		assert(0);
		return;
	}

	pNewNode->_pNext = NULL;
	pNewNode->_data = data;

	return pNewNode;
}

//增容
void _CheckCapacity(HashBucket *pHB)
{
	assert(pHB);
	int i = 0;

	//有效元素个数与哈希桶的个数相当（最佳状态：每个桶中挂一个结点）
	if (pHB->_size == pHB->_capacity)
	{
		int newCapacity = GetNextPrime(pHB->_capacity);

		//开辟新空间
		PNode *pNewTable = (PNode *)malloc(sizeof(PNode));
		if (NULL == pNewTable)
		{
			assert(0);
			return;
		}

		pHB->_capacity = newCapacity;
		memset(pNewTable, 0, sizeof(PNode)*newCapacity);

		//拷贝元素
		for (; i < pHB->_capacity; ++i)
		{
			//将i号桶中所有结点重新哈希
			PNode pCur = pHB->_table[i];
			while (pCur)
			{
				int hashAddr = HashFuncBucket(pHB, pCur->_data);

				//将pCur从原来链表中删除
				pHB->_table[i] = pCur->_pNext;

				//将pCur插入到新链表中
				pCur->_pNext = pNewTable[hashAddr];
				pNewTable[hashAddr] = pCur;

				//取原链表中的下一个结点
				pCur = pHB->_table[i];
			}
		}

		free(pHB->_table);
		pHB->_table = pNewTable;
	}
}

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

	_CheckCapacity(pHB);

	//计算哈希桶号
	bucketNo = HashFuncBucket(pHB, data);

	//检测元素是否在哈希表中
	while (pCur)
	{
		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)
{
	assert(pHB);
	int bucketNo;
	PNode pCur = NULL;
	PNode pParent = NULL;

	bucketNo = HashFuncBucket(pHB, data);
	pCur = pHB->_table[bucketNo];
	while (pCur)
	{
		if (data == pCur->_data)
		{
			//删除第一个结点
			if (pCur = pHB->_table[bucketNo])
			{
				pHB->_table[bucketNo] = pCur->_pNext;
				free(pCur);
			}
			else
				pParent->_pNext = pCur->_pNext;

			free(pCur);
			pHB->_size--;
			return 1;
		}

		pParent = pCur;
		pCur = pCur->_pNext;
	}
}

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

	bucketNo = HashFuncBucket(pHB, data);
	pCur = pHB->_table[bucketNo];
	while (pCur)
	{
		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)
{
	return pHB->_size;
}

void DestroyHashBucket(HashBucket *pHB)
{
	assert(pHB);
	int i = 0;
	for (; i < pHB->_capacity; ++i)
	{
		PNode pDel = pHB->_table[i];
		while (pDel)
		{
			pHB->_table[i] = pDel->_pNext;
			free(pDel);
			pDel = pHB->_table[i];
		}
	}

	free(pHB->_table);
	pHB->_table = NULL;
	pHB->_capacity = 0;
	pHB->_size = 0;
}

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

//打印哈希桶元素
void PrintHashbucket(HashBucket *pHB)
{
	assert(pHB);
	int i = 0;
	for (; i < pHB->_capacity; ++i)
	{
		PNode pCur = pHB->_table[i];
		printf("table[%d]:", i);
		while (pCur)
		{
			printf("%d-->", pCur->_data);
			pCur = pCur->_pNext;
		}

		printf("NULL\n");
	}
}



/***************************************/
//Common.h

#pragma once

//素数表
unsigned long GetNextPrime(unsigned long prime);

//字符串类型
unsigned long StrToINT(const char * str);

//默认转化方法
unsigned long DefToINT(long data);


/////////////////////////////////////////////////
//Common.c
#define PRIME_SIZE 28

//素数表
unsigned long GetNextPrime(unsigned long prime)
{

	// 使用素数表对齐做哈希表的容量，降低哈希冲突      
	static const 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 = 0; 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);
}

//默认转化方法
unsigned long DefToINT(long data)
{
	return data;
}



/***************************************/
//test.c
#include "HashBucket.h"

void TestHashBucket()
{
	HashBucket ht;
	InitHashBucket(&ht, 10, DefToINT);
	InsertHashBucket(&ht, 11);
	InsertHashBucket(&ht, 6);
	InsertHashBucket(&ht, 49);
	InsertHashBucket(&ht, 28);
	InsertHashBucket(&ht, 10);
	InsertHashBucket(&ht, 23);
	InsertHashBucket(&ht, 14);
	InsertHashBucket(&ht, 35);
	InsertHashBucket(&ht, 22);
	InsertHashBucket(&ht, 27);
	InsertHashBucket(&ht, 17);
	InsertHashBucket(&ht, 17);
		
	printf("size = %d\n", SizeHashBucket(&ht));
	PrintHashbucket(&ht);
	DestroyHashBucket(&ht);
}

int main()
{
	TestHashBucket();
	system("pause");
	return 0;
}

结果输出：