【数据结构与算法】哈希表

哈希表（Hash Table）是一种基于键（Key）直接访问数据的高效数据结构，其核心思想是通过哈希函数将键映射到数组的特定位置，从而实现平均时间复杂度为 O(1)O(1) 的插入、查找和删除操作。

结构定义

// 哈希表节点
typedef struct HashNode {
    int key;
    int value;
    struct Hashcode* next;
} HashNode;

// 哈希表
typedef struct {
    int size;
    HashNode** buckets;
} HashTable;

初始化

创建HashTable结构体变量，进行初始化赋值，分配桶的内存。

// 初始化哈希表
HashTable *creat_hash_table(int size)
{
    HashTable* table = (HashTable*)malloc(sizeof(HashTable));
    table->size = size;
    table->buckets = (HashNode**)malloc(size * sizeof(HashNode*));
    for(int i = 0; i < size; i++)
    {
        table->buckets[i] = NULL;
    }
    return table;
}

哈希函数

// 哈希函数
int hash(int key, int size)
{
    return key % size;
}

通过简单取模运算获得哈希值

插入

// 插入
void insert(HashTable *table, int key, int value)
{
    int index = hash(key, table->size);
    HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;

    // 插入链表头部，避免遍历链表
    if (table->buckets[index] == NULL)
    {
        table->buckets[index] = newNode;
    }
    else
    {
        newNode->next = table->buckets[index];
        table->buckets[index] = newNode;
    }
}

头插法无需遍历到尾部。

查找

// 查找

int search(HashTable *table, int key)
{
    int index = hash(key, table->size);
    HashNode *current = table->buckets[index];
    while (current != NULL)
    {
        if (current->key == key)
        {
            return current->value;
        }
        current = current->next;
    }
    return -1;
}

删除

void deleate(HashTable* table, int key)
{
	int index = hash(key, table->size);
	HashNode* current = table->buckets[index];
	HashNode* prev = NULL;

	while(current != NULL)
	{
		if(current->key == key)
		{
			if(prev == NULL)
			{
				table->buckets[index] = current->next;
			}
			else
			{
				prev->next = current->next;
			}

			free(current);
			return;
		}
			prev = current;
			current = current->next;
	}
}