ハッシュ表の基本的な操作--ファスナー法

#pragma once

#include 
#include 
#include 
#include 
#include 
//typedef char* HTBKeyType;
//typedef char* HTBValueType;

//typedef char* HTBKeyType;
//typedef int HTBValueType;

typedef int HTBKeyType;
typedef int HTBValueType;

typedef struct HashNode
{
	struct HashNode* _next;
	HTBKeyType _key;
	HTBValueType _value;
}HashNode;

typedef struct HashTableBucket
{
	HashNode** _tables;
	size_t _size;
	size_t _len;
}HTB;

//   
void HTBInit(HTB* htb, size_t len);
//  
void HTBDestory(HTB* htb);
//  
int HTBInsert(HTB* htb, HTBKeyType key, HTBValueType value);
//  
int HTBRemove(HTB* htb, HTBKeyType key);
//  
HashNode* HTBFind(HTB* htb, HTBKeyType key);
//  
int HTBSize(HTB* htb);
//      
int HTBEmpty(HTB* htb);

void TestHashTableBucket();

#include "HashTableBucket.h"



static size_t GetNextPrime(size_t value)//   ，             
{
	int i = 0;
	//const int _PrimeSize = 28;
	static const unsigned long _PrimeList[28] =
	{
		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
	};

	for (; i < 28; ++i)
	{
		if (_PrimeList[i] > value)
		{
			return _PrimeList[i];
		}
	}

	return _PrimeList[27];
}
//   
void HTBInit(HTB* htb, size_t len)
{
	assert(htb);
	////             
	htb->_len = GetNextPrime(len);
	htb->_size = 0;
	//        
	htb->_tables = (HashNode**)malloc(sizeof(HashNode*)*htb->_len);
	//               
	memset(htb->_tables, 0, sizeof(HashNode*)*htb->_len);
}
//  
void HTBDestory(HTB* htb)
{
	assert(htb);
	//              
	for (size_t i = 0; i < htb->_len; i++)
	{
		HashNode* cur = htb->_tables[i];
		while (cur)
		{
			HashNode* next = cur->_next;
			free(cur);
			cur = next;
		}
		htb->_tables[i] = NULL;
	}
	//     
	free(htb->_tables);
	htb->_tables = NULL;
	htb->_size = 0;
	htb->_len = 0;
}
int HTBHashFunc(HTBKeyType key, int len)
{
	//return StrHash(key) % len;
	return key % len;
}
//          1，    1，     
void HTBCheckCapacity(HTB* htb)
{
	assert(htb);
	if (htb->_size == htb->_len)
	{
		HTB newhtb;
		newhtb._len = GetNextPrime(htb->_len);
		HTBInit(&newhtb, newhtb._len);
		for (size_t i = 0; i < htb->_len; ++i)
		{
			HashNode* cur = htb->_tables[i];
			while (cur)
			{
				HashNode* next = cur->_next;
				size_t index = HTBHashFunc(cur->_key, newhtb._len);

				cur->_next = newhtb._tables[index];
				newhtb._tables[index] = cur;

				cur = next;
			}

			htb->_tables[i] = NULL;
		}
		//       
		HTBDestory(htb);
		htb->_tables = newhtb._tables;
		htb->_size = newhtb._size;
		htb->_len = newhtb._len;
	}
}

//    
HashNode* BuyHashNode(HTBKeyType key, HTBValueType value)
{
	HashNode* node = malloc(sizeof(HashNode));
	node->_key = key;
	node->_value = value;
	node->_next = NULL;

	return node;
}

//      
int HTBInsert(HTB* htb, HTBKeyType key, HTBValueType value)
{
	assert(htb);
	HashNode* cur, *newNode;
	HTBCheckCapacity(htb);
	int index = HTBHashFunc(key, htb->_len);
	cur = htb->_tables[index];
	while (cur)
	{
		if (cur->_key == key)
			return -1;

		cur = cur->_next;
	}

	newNode = BuyHashNode(key, value);
	newNode->_next = htb->_tables[index];
	htb->_tables[index] = newNode;
	htb->_size++;

	return 0;
}
//      
int HTBRemove(HTB* htb, HTBKeyType key)
{
	assert(htb);

	HashNode* cur = NULL, *prev = NULL;

	int index = HTBHashFunc(key, htb->_len);
	cur = htb->_tables[index];
	while (cur)
	{
		if (cur->_key == key)
		{
			if (prev == NULL)
				htb->_tables[index] = cur->_next;
			else
				prev->_next = cur->_next;

			free(cur);
			--htb->_size;
			return 0;
		}

		prev = cur;
		cur = cur->_next;
	}

	return -1;

}
//           
HashNode* HTBFind(HTB* htb, HTBKeyType key)
{
	assert(htb);
	HashNode* cur;
	int index = HTBHashFunc(key, htb->_len);
	cur = htb->_tables[index];
	while (cur)
	{
		if (cur->_key == key)
		{
			return cur;
		}

		cur = cur->_next;
	}

	return NULL;
}

int HTBSize(HTB* htb)
{
	assert(htb);
	return htb->_size == 0 ? 0 : 1;
}
int HTBEmpty(HTB* htb)
{
	assert(htb);
	return htb->_size == htb->_len ? 0 : 1;
}
//     
void HTBPrint(HTB* htb)
{
	assert(htb);
	for (size_t i = 0; i < htb->_len; ++i)
	{
		int count = 0;
		HashNode* cur = htb->_tables[i];
		printf(" [%d]->", i);

		while (cur)
		{
			printf("[%s:%s]->", cur->_key, cur->_value);
			++count;
			cur = cur->_next;
		}
		printf("%d
", count);
	}

	printf("
");
}
void TestHashTableBucket()
{
	HTB htb;
	HTBInit(&htb, 10);

	HTBInsert(&htb, "insert", "  ");
	HTBInsert(&htb, "delete", "  ");
	HTBInsert(&htb, "hash", "  ");
	HTBInsert(&htb, "test", "  ");

	HTBPrint(&htb);
	HTBRemove(&htb, "test");
	HTBPrint(&htb);

}

int main()
{
	TestHashTableBucket();
	return 0;
}