初遇哈希表

一、哈希表

哈希表：可以在 O(1) 的时间复杂度内找到元素

哈希函数： Hash(key) = key % capacity

哈希冲突：不同的关键字计算出相同的哈希地址

这是哈希表无法解脱的桎梏，一旦使用哈希表，哈希冲突是无法避免的，只能通过巧妙的设计哈希函数，尽量减少哈希冲突，而无法避免

二、开放地址法解决哈希冲突

当发生哈希冲突时，就把值放到下一个空位

// hash.h
#include <stdio.h>
#include <malloc.h>
#include <stdint.h>
#include <assert.h>

typedef int Key;

typedef enum State
{
	EMPTY,
	EXIST,
	DELETE
}State;

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

typedef size_t(*HashFunc)(Key key, size_t capacity);

typedef struct HashTable{
	KeyType *array;
	size_t capacity;
	size_t size;
	HashFunc hashfunc;
}HashTable;

int HashInit(HashTable* pHT, size_t capacity, HashFunc hashfunc);

int HashDestory(HashTable *pHT);

int HashInsert(HashTable *pHT, Key key);

int HashSearch(const HashTable *pHT, Key key);

int HashRemove(HashTable *pHT, Key key);

//hash.c
#include "hash.h"

int HashInit(HashTable* pHT, size_t capacity, HashFunc hashfunc)
{
	if (pHT == NULL)
	{
		return -1;
	}

	pHT->array = malloc(sizeof(KeyType)* capacity);
	if (pHT->array == NULL)
	{
		return -1;
	}

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

	pHT->capacity = capacity;
	pHT->size = 0;
	pHT->hashfunc = hashfunc;
	return 0;
}

int HashDestory(HashTable *pHT)
{
	if (pHT == NULL)
	{
		return -1;
	}

	if (pHT->array == NULL)
	{
		return -1;
	}

	free(pHT->array);
	pHT->array = NULL;
	pHT->capacity = 0;
	pHT->size = 0;
	pHT->hashfunc = NULL;
	return 0;
}

// 1. 计算哈希地址
// 2. 状态
int HashSearch(const HashTable *pHT, Key key)
{
	if (pHT == NULL)
	{
		return -1;
	}

	// 计算哈希地址
	size_t index = pHT->hashfunc(key, pHT->capacity);
	size_t copy = index;

	// 判断状态
	while (1)
	{
		if (pHT->array[index].state == EXIST && pHT->array[index].key == key)
		{
			return index;
		}

		index = (index + 1) % pHT->capacity;
		if (index == copy)
			return -1;
	}
}

// 检测容量
void checkCapacity(HashTable* pHT)
{
	if (pHT->size * 100 / pHT->capacity < 75)
	{// a 负载因子 不需要扩容
		return;
	}

	HashTable temp;
	HashInit(&temp, pHT->capacity * 2, pHT->hashfunc);
	for (size_t i = 0; i < pHT->capacity; ++i)
	{
		HashInsert(&temp, pHT->array[i].key);
	}

	pHT->array = temp.array;
	pHT->capacity = temp.capacity;
}

// 1. 先查找这个元素是否已经在哈希表中 在   返回 -1 插入失败   
// 2. 不在哈希表中
//    1) 考虑是否要增容
//    2) 计算哈希地址 线性探测插入元素
int HashInsert(HashTable *pHT, Key key)
{
	if (pHT == NULL)
	{
		return -1;
	}

	int res = HashSearch(pHT, key);
	if (res != -1)
	{
		return -1;
	}

	checkCapacity(pHT);
	int index = pHT->hashfunc(key, pHT->capacity);
	while (1)
	{// 已经检测容量了 所以肯定能插入成功
		if (pHT->array[index].state == EMPTY)
		{
			pHT->array[index].key = key;
			pHT->array[index].state = EXIST;
			pHT->size++;
			return index;
		}

		index = (index + 1) % pHT->capacity;
	}
}

// 删除元素
int HashRemove(HashTable *pHT, Key key)
{
	// 1. 先根据哈希函数 计算哈希地址
	assert(pHT);
	size_t index = pHT->hashfunc(key, pHT->capacity);
	
	while (pHT->array[index].key != EMPTY)
	{
		if (pHT->array[index].state == EXIST && pHT->array[index].key == key)
		{
			pHT->array[index].state = DELETE;
			pHT->size--;
			return 0;
		}
		index = (index + 1) % pHT->capacity;
	}

	return -1;
}

//test.c
#include "hash.h"
#include <stdlib.h>

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

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

	size_t index = HashInsert(&ht, 7);
	printf("ht.array[%d] = %d\n", index, ht.array[index]);

	index = HashInsert(&ht, 14);
	printf("ht.array[%d] = %d\n", index, ht.array[index]);

	index = HashInsert(&ht, 21);
	printf("ht.array[%d] = %d\n", index, ht.array[index]);

	index = HashInsert(&ht, 28);
	printf("ht.array[%d] = %d\n", index, ht.array[index]);

	index = HashInsert(&ht, 4);
	printf("ht.array[%d] = %d\n", index, ht.array[index]);

	index = HashInsert(&ht, 5);
	printf("ht.array[%d] = %d\n", index, ht.array[index]);

	index = HashInsert(&ht, 6);
	printf("ht.array[%d] = %d\n", index, ht.array[index]);

	index = HashInsert(&ht, 9);
	printf("ht.array[%d] = %d\n", index, ht.array[index]);

	index = HashSearch(&ht, 9);
	printf("index = %d\n", index);

	index = HashRemove(&ht, 9);
	if (index == -1)
	{
		printf("删除失败\n");
	}
	else
	{
		printf("删除成功\n");
	}

	index = HashSearch(&ht, 9);
	printf("index = %d\n", index);

}

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

测试结果：
初遇哈希表

初遇哈希，如有不正，还请指出，谢谢：）

一、哈希表

二、开放地址法解决哈希冲突

相关推荐