Initial commit

1 files changed, 130 insertions, 0 deletions

diff --git a/content/posts/【数据结构与算法】哈希表.md b/content/posts/【数据结构与算法】哈希表.md
new file mode 100644
index 0000000..3b78524
--- /dev/null
+++ b/content/posts/【数据结构与算法】哈希表.md
@@ -0,0 +1,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;
+	}
+}
+
+```