基于C语言实现哈希表存储提升随机访问效率及数据库生成程序问询

一、C语言哈希表实现（提升随机访问速度） #

哈希表是优化随机访问性能的理想选择，咱们用链地址法来实现（冲突处理简单且高效）——核心逻辑是通过哈希函数将键映射到数组索引，遇到冲突时用链表挂载后续节点。

1. 核心结构体定义 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 哈希表节点：存储哈希索引（键）和对应的数据
typedef struct HashNode {
    int key;                  // 哈希索引（范围1~1e8）
    float* float_sequence;    // 固定长度的float序列
    int x_coord, y_coord;     // x、y坐标
    int doc_id;               // 文档ID
    struct HashNode* next;    // 链表指针（处理冲突）
} HashNode;

// 哈希表主结构体
typedef struct HashTable {
    int bucket_count;         // 哈希表桶的数量
    HashNode** buckets;       // 桶数组
} HashTable;

2. 哈希函数与核心操作 #

咱们先选用简单高效的取模哈希函数（如果需要更均匀的分布，后期可以换成MurmurHash这类工业级哈希算法），同时实现初始化、插入、查找、销毁四个核心操作：

// 哈希函数：将键映射到桶索引
int hash_func(int key, int table_size) {
    // 保证索引非负（key本身是1~1e8，直接取模即可）
    return key % table_size;
}

// 初始化哈希表
HashTable* hash_table_create(int bucket_num) {
    HashTable* table = (HashTable*)malloc(sizeof(HashTable));
    table->bucket_count = bucket_num;
    // 用calloc初始化桶数组，避免野指针
    table->buckets = (HashNode**)calloc(bucket_num, sizeof(HashNode*));
    return table;
}

// 插入数据到哈希表
void hash_table_insert(HashTable* table, int key, float* float_seq, int x, int y, int doc_id, int float_len) {
    int bucket_idx = hash_func(key, table->bucket_count);
    HashNode* new_node = (HashNode*)malloc(sizeof(HashNode));
    
    // 复制数据到节点
    new_node->key = key;
    new_node->float_sequence = (float*)malloc(float_len * sizeof(float));
    memcpy(new_node->float_sequence, float_seq, float_len * sizeof(float));
    new_node->x_coord = x;
    new_node->y_coord = y;
    new_node->doc_id = doc_id;
    
    // 头插法插入链表（插入效率更高）
    new_node->next = table->buckets[bucket_idx];
    table->buckets[bucket_idx] = new_node;
}

// 根据哈希索引查找数据
HashNode* hash_table_find(HashTable* table, int key) {
    int bucket_idx = hash_func(key, table->bucket_count);
    HashNode* current = table->buckets[bucket_idx];
    
    while (current != NULL) {
        if (current->key == key) {
            return current; // 找到目标节点
        }
        current = current->next;
    }
    return NULL; // 未找到对应数据
}

// 销毁哈希表，释放内存
void hash_table_destroy(HashTable* table, int float_len) {
    for (int i = 0; i < table->bucket_count; i++) {
        HashNode* current = table->buckets[i];
        while (current != NULL) {
            HashNode* temp = current;
            free(temp->float_sequence);
            free(temp);
            current = current->next;
        }
    }
    free(table->buckets);
    free(table);
}

使用提示 #

• 初始化哈希表时，建议把桶数量设为预期数据量的1.5~2倍，能有效减少冲突概率
• 查找操作的平均时间复杂度是O(1)，完全满足随机访问提速的需求

二、Database Generation程序实现 #

这个程序的核心是读取输入数据，生成符合格式要求的数据库行并写入文件。咱们假设输入文件每行包含：固定长度的float序列 + x坐标 + y坐标 + 文档ID（你可以根据实际输入格式调整读取逻辑）。

完整代码示例 #

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define FLOAT_SEQ_LEN 156    // 示例中的float序列长度，可按需修改
#define MIN_HASH_IDX 1
#define MAX_HASH_IDX 100000000 // 哈希索引上限1e8

// 生成[MIN_HASH_IDX, MAX_HASH_IDX]范围内的随机哈希索引
int generate_random_hash() {
    return MIN_HASH_IDX + rand() % (MAX_HASH_IDX - MIN_HASH_IDX + 1);
}

int main(int argc, char* argv[]) {
    // 检查命令行参数是否正确
    if (argc != 3) {
        fprintf(stderr, "用法: %s <输入文件路径> <输出数据库路径>\n", argv[0]);
        return 1;
    }

    FILE* input_fp = fopen(argv[1], "r");
    FILE* output_fp = fopen(argv[2], "w");
    if (!input_fp || !output_fp) {
        perror("文件打开失败");
        return 1;
    }

    // 初始化随机数种子
    srand(time(NULL));

    float float_seq[FLOAT_SEQ_LEN];
    int x, y, doc_id;

    // 逐行读取输入数据并生成数据库行
    while (fscanf(input_fp, "%f", &float_seq[0]) != EOF) {
        // 读取剩余的float值
        for (int i = 1; i < FLOAT_SEQ_LEN; i++) {
            fscanf(input_fp, "%f", &float_seq[i]);
        }
        // 读取三个整数参数
        fscanf(input_fp, "%d %d %d", &x, &y, &doc_id);

        // 生成哈希索引
        int hash_idx = generate_random_hash();

        // 写入数据库行：先写哈希索引
        fprintf(output_fp, "%d ", hash_idx);
        // 写入float序列（保留两位小数，可调整格式）
        for (int i = 0; i < FLOAT_SEQ_LEN; i++) {
            fprintf(output_fp, "%.2f ", float_seq[i]);
        }
        // 写入坐标和文档ID
        fprintf(output_fp, "%d %d %d\n", x, y, doc_id);
    }

    // 关闭文件
    fclose(input_fp);
    fclose(output_fp);
    printf("数据库文件生成完成！\n");

    return 0;
}

关键细节说明 #

• 哈希索引唯一性：如果需要保证索引不重复，可以结合第一部分的哈希表，把已生成的索引存入表中做查重
• 输入格式适配：如果你的输入文件格式不同（比如每行开头是文档ID），直接调整fscanf的读取顺序即可
• 编译运行：用gcc database_gen.c -o database_gen编译，执行时输入./database_gen input.txt output.db即可

内容的提问来源于stack exchange，提问作者user1371666