blob: 3b78524a678a74a86c57965b5a656db1e7d5bd23 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
---
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;
}
}
```
|
