---
abbrlink: 971437699
categories:
- 技术
date: "2025-05-28 21:44:28"
tags:
- 黑历史
- 数据结构与算法
title: 【数据结构与算法】哈希表
---
哈希表（Hash Table）是一种基于键（Key）直接访问数据的高效数据结构，其核心思想是通过哈希函数将键映射到数组的特定位置，从而实现平均时间复杂度为 O(1)O(1) 的插入、查找和删除操作。

## 结构定义
```c
// 哈希表节点
typedef struct HashNode {
    int key;
    int value;
    struct Hashcode* next;
} HashNode;

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

## 初始化
创建HashTable结构体变量，进行初始化赋值，分配桶的内存。
```c
// 初始化哈希表
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;
}
```

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

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

## 插入
```c
// 插入
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;
    }
}
```
头插法无需遍历到尾部。

## 查找
```c
// 查找

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;
}
```

## 删除
```c
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;
	}
}

```