基于C语言的简易数据库系统
设计并实现一个轻量级的键值对数据库系统，理解数据库的基本概念和操作。
设计一个基于C语言的简易键值对数据库系统是一个很好的实践项目，它可以帮助你深入理解数据库的基本原理和操作方法。键值对数据库（如Redis）是数据库系统中最简单的形式之一，主要存储键值对，支持快速的查找、插入、删除等操作。
设计概述
1. 数据结构
键值对存储：使用哈希表（或简单的链表数组）来存储键值对。键（Key）和值（Value）都是字符串。
哈希表：为了快速访问，我们将使用哈希表来存储键值对。哈希表的每个槽位可以是一个链表，以解决哈希冲突。
2. 功能需求
插入（SET）：向数据库中添加或更新一个键值对。
获取（GET）：根据键获取对应的值。
删除（DEL）：根据键删除键值对。
列出所有键（KEYS）：列出数据库中所有的键（可选，根据实现复杂度决定）。
3. 错误处理
在进行数据库操作时，需要处理各种错误情况，如内存不足、键已存在（对于SET操作，根据是否覆盖现有值决定是否为错误）等。
实现步骤
1. 定义数据结构
#include <stdio.h> |
#include <stdlib.h> |
#include <string.h> |
|
#define HASH_TABLE_SIZE 1024 |
|
typedef struct KeyValue { |
char *key; |
char *value; |
struct KeyValue *next; |
} KeyValue; |
|
KeyValue *hashTable[HASH_TABLE_SIZE]; |
|
// 哈希函数（简单示例，实际使用中可能需要更复杂的哈希算法） |
unsigned int hash(const char *str) { |
unsigned int hash = 5381; |
int c; |
|
while ((c = *str++)) |
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ |
|
return hash % HASH_TABLE_SIZE; |
} |
2. 实现基本操作
void set(const char *key, const char *value) { |
unsigned int index = hash(key); |
KeyValue *entry = hashTable[index]; |
|
while (entry != NULL) { |
if (strcmp(entry->key, key) == 0) { |
free(entry->value); |
entry->value = strdup(value); |
return; |
} |
entry = entry->next; |
} |
|
// 如果没有找到，添加新的键值对 |
KeyValue *newEntry = malloc(sizeof(KeyValue)); |
newEntry->key = strdup(key); |
newEntry->value = strdup(value); |
newEntry->next = hashTable[index]; |
hashTable[index] = newEntry; |
} |
|
char *get(const char *key) { |
unsigned int index = hash(key); |
KeyValue *entry = hashTable[index]; |
|
while (entry != NULL) { |
if (strcmp(entry->key, key) == 0) { |
return entry->value; |
} |
entry = entry->next; |
} |
|
return NULL; // 找不到键时返回NULL |
} |
|
void del(const char *key) { |
unsigned int index = hash(key); |
KeyValue *entry = hashTable[index]; |
KeyValue *prev = NULL; |
|
while (entry != NULL) { |
if (strcmp(entry->key, key) == 0) { |
if (prev == NULL) { |
hashTable[index] = entry->next; |
} else { |
prev->next = entry->next; |
} |
free(entry->key); |
free(entry->value); |
free(entry); |
return; |
} |
prev = entry; |
entry = entry->next; |
} |
} |
|
// 实现其他功能，如列出所有键等 |
3. 测试和调试
编写测试程序来验证SET、GET、DEL等操作的正确性。
使用断言或手动检查来确保数据的一致性和正确性。
总结
这个简易的键值对数据库系统是一个很好的学习项目，可以帮助你理解数据库的基本原理，如数据存储、哈希表的使用、错误处理等。随着学习的深入，你可以逐步增加更复杂的功能，如持久化存储、并发控制等。
基于C语言的简易数据库系统（扩展）
在深入探讨如何修改和补充一个基于哈希表的键值存储系统时，我们将从多个方面着手，包括哈希表的定义、哈希函数的实现、键值对的插入、删除、查找功能，以及额外的辅助功能如列出所有键等。此外，我们还将讨论如何测试这些功能的正确性和性能。
1. 哈希表的定义与初始化
首先，我们需要定义哈希表及其节点的数据结构。这里使用C语言来实现：
#include <stdlib.h> |
#include <string.h> |
#include <stdio.h> |
|
#define HASH_TABLE_SIZE 1024 |
|
typedef struct KeyValue { |
char *key; |
char *value; |
struct KeyValue *next; |
} KeyValue; |
|
KeyValue *hashTable[HASH_TABLE_SIZE]; |
|
// 初始化哈希表 |
void initHashTable() { |
for (int i = 0; i < HASH_TABLE_SIZE; i++) { |
hashTable[i] = NULL; |
} |
} |
2. 哈希函数的实现
哈希函数是哈希表性能的关键因素之一。这里我们采用一个简单的字符串哈希算法（djb2算法变种），但请注意，在实际应用中可能需要更复杂且冲突率更低的算法。
unsigned int hash(const char *str) { |
unsigned int hash = 5381; |
int c; |
while ((c = *str++)) { |
hash = ((hash << 5) + hash) + c; // hash * 33 + c |
} |
return hash % HASH_TABLE_SIZE; |
} |
3. 键值对的插入
在插入新的键值对时，我们需要先检查该键是否已存在。如果存在，则更新其值；如果不存在，则创建新的键值对并插入到相应的哈希桶中。
void set(const char *key, const char *value) { |
unsigned int index = hash(key); |
KeyValue *entry = hashTable[index]; |
KeyValue *prev = NULL; |
|
// 查找键是否已存在 |
while (entry != NULL) { |
if (strcmp(entry->key, key) == 0) { |
// 更新值 |
free(entry->value); // 释放旧值 |
entry->value = strdup(value); // 分配新值 |
return; |
} |
prev = entry; |
entry = entry->next; |
} |
|
// 插入新键值对 |
KeyValue *newNode = malloc(sizeof(KeyValue)); |
if (!newNode) { |
perror("Failed to allocate memory for new key-value pair"); |
return; |
} |
newNode->key = strdup(key); |
newNode->value = strdup(value); |
newNode->next = NULL; |
|
if (prev == NULL) { |
hashTable[index] = newNode; |
} else { |
prev->next = newNode; |
} |
} |
4. 键值对的删除
删除操作与插入类似，需要先找到对应的键值对，然后释放其内存并从链表中移除。
void del(const char *key) { |
unsigned int index = hash(key); |
KeyValue *entry = hashTable[index]; |
KeyValue *prev = NULL; |
|
while (entry != NULL) { |
if (strcmp(entry->key, key) == 0) { |
if (prev == NULL) { |
hashTable[index] = entry->next; |
} else { |
prev->next = entry->next; |
} |
free(entry->key); |
free(entry->value); |
free(entry); |
return; |
} |
prev = entry; |
entry = entry->next; |
} |
} |
5. 键值对的查找
查找操作较为简单，遍历哈希桶中的链表，直到找到匹配的键。
const char* get(const char *key) { |
unsigned int index = hash(key); |
KeyValue *entry = hashTable[index]; |
|
while (entry != NULL) { |
if (strcmp(entry->key, key) == 0) { |
return entry->value; |
} |
entry = entry->next; |
} |
|
return NULL; // 未找到 |
} |
