哈希索引Uber出行数据文件搜索异常问题求助

我用哈希表给包含Uber城市区域出行时间的CSV文件建索引，字段包括sourceid（起点）、dstid（终点）、hod（时段）、mean_travel_time（平均出行时间）。设置了1160个桶（对应区域数），用取模哈希函数，链表处理冲突，最后把索引存成二进制文件。生成索引的代码如下：

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

#define casillas 1160

typedef struct {
    int sourceid;
    int dstid;
    int hod;
    float mean_travel_time;
    float standard_deviation_travel_time;
    float geometric_mean_travel_time;
    float geometric_standard_deviation_travel_time;
} Viaje;

typedef struct _Nodo {
    Viaje viaje;
    struct _Nodo* siguiente;
} Nodo;

int hash(int sourceid) {
    return sourceid % casillas;
}

void insertar_en_lista(Viaje viaje, Nodo* tabla_hash[]) {
    int indice = hash(viaje.sourceid);
    Nodo* nuevo_nodo = (Nodo*) malloc(sizeof(Nodo));
    nuevo_nodo->viaje = viaje;
    nuevo_nodo->siguiente = tabla_hash[indice]; 
    tabla_hash[indice] = nuevo_nodo; // --&gt; new node is now first node
}

int main(){
    FILE* archivo = fopen("viajes.csv", "r");
    char linea[1024];
    fgets(linea, 1024, archivo); // Descartamos la primera línea (cabecera)
    Nodo* tabla_hash[casillas] = {NULL}; // Inicializamos la tabla hash con punteros nulos
    while (fgets(linea, 1024, archivo)) {
        Viaje viaje;
        sscanf(linea, "%d,%d,%d,%f,%f,%f,%f",
            &viaje.sourceid,
            &viaje.dstid,
            &viaje.hod,
            &viaje.mean_travel_time,
            &viaje.standard_deviation_travel_time,
            &viaje.geometric_mean_travel_time,
            &viaje.geometric_standard_deviation_travel_time
        );
        insertar_en_lista(viaje, tabla_hash);
    }
    fclose(archivo);

    archivo = fopen("index.bin", "wb");
    for (int i = 0; i < casillas; i++) {
        Nodo* nodo_actual = tabla_hash[i];
        while (nodo_actual) {
            fwrite(&nodo_actual->viaje, sizeof(Viaje), 1, archivo);
            nodo_actual = nodo_actual->siguiente;
        }
    }
    fclose(archivo);
    return 0;
} 

生成索引后，我需要根据给定的起点、终点、时段查找路线。用hash()计算索引后用fseek定位，但调试发现，比如查sourceid=1140时，定位后读到的第一条记录sourceid是1160，像是倒序遍历文件。而且只有定位到首个索引记录时搜索有效，循环没法继续遍历。查询代码如下：

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

#define casillas 1160
void exit(int _code);

typedef struct {
    int sourceid;
    int dstid;
    int hod;
    float mean_travel_time;
    float standard_deviation_travel_time;
    float geometric_mean_travel_time;
    float geometric_standard_deviation_travel_time;
} Viaje;

int hash(int sourceid) {
    return sourceid % casillas;
}

float buscarTiempoViaje(int sourceid, int dstid, int hod, FILE* archivo) {
    int indice = hash(sourceid);
    Viaje viaje;
    int result = fseek(archivo, indice * sizeof(Viaje), SEEK_SET); // Apuntamos al inicio de la lista correspondiente
    printf("%ld\n", indice*sizeof(viaje));
    printf("%ld\n", ftell(archivo));
    if(result < 0){
        perror("No se pudo hallar la lista correspondiente al índice calculado");
        exit(-1);
    }
    while (fread(&viaje, sizeof(Viaje), 1, archivo) == 1) {
        if(viaje.sourceid == indice){
            if (viaje.sourceid == sourceid && viaje.dstid == dstid && viaje.hod == hod) {
                return viaje.mean_travel_time;
            }
        }
    }
    // Si llegamos aquí, no se encontró el viaje
    viaje.sourceid = -1;
    printf("NA\n");
    return -1;
}

问题根源 #

1. 二进制文件存储逻辑错误：你错误地认为每个桶的记录在文件中的起始位置是indice * sizeof(Viaje)，但实际上每个桶的记录数量不固定，没有存储桶的偏移量的话，根本无法通过哈希值直接定位到对应桶的起始位置。另外，链表用头插法构建，每个桶的记录是倒序写入文件的，但这不是核心问题。
2. 查询逻辑错误：
   • if(viaje.sourceid == indice)判断完全错误：indice是sourceid取模后的哈希值，比如sourceid=1160的哈希值是0，显然sourceid不等于哈希值，这个判断会跳过所有正确记录。
   • 用indice * sizeof(Viaje)作为偏移量，假设每个桶只有1条记录，完全不符合实际数据分布，导致定位位置错误。

修复方案 #

1. 修改索引文件格式，存储桶的偏移量 #

要实现快速定位，必须先存储每个桶在二进制文件中的起始偏移量，步骤如下：

• 遍历哈希表统计每个桶的记录数
• 计算每个桶的起始偏移量（前一个桶的起始偏移量+前一个桶的记录数*sizeof(Viaje)）
• 先将偏移量数组写入二进制文件，再写入所有桶的记录

2. 修正查询逻辑 #

• 先读取偏移量数组，通过哈希值拿到对应桶的起始偏移量并定位
• 遍历当前桶的所有记录（读到下一个桶的起始位置或文件末尾停止）
• 去掉错误的viaje.sourceid == indice判断，直接匹配目标sourceid、dstid、hod

修改后的生成索引代码 #

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

#define casillas 1160

typedef struct {
    int sourceid;
    int dstid;
    int hod;
    float mean_travel_time;
    float standard_deviation_travel_time;
    float geometric_mean_travel_time;
    float geometric_standard_deviation_travel_time;
} Viaje;

typedef struct _Nodo {
    Viaje viaje;
    struct _Nodo* siguiente;
} Nodo;

int hash(int sourceid) {
    return sourceid % casillas;
}

void insertar_en_lista(Viaje viaje, Nodo* tabla_hash[]) {
    int indice = hash(viaje.sourceid);
    Nodo* nuevo_nodo = (Nodo*) malloc(sizeof(Nodo));
    nuevo_nodo->viaje = viaje;
    nuevo_nodo->siguiente = tabla_hash[indice]; 
    tabla_hash[indice] = nuevo_nodo;
}

int main(){
    FILE* archivo = fopen("viajes.csv", "r");
    if (!archivo) {
        perror("无法打开CSV文件");
        return 1;
    }
    char linea[1024];
    fgets(linea, 1024, archivo); // 跳过表头

    Nodo* tabla_hash[casillas] = {NULL};
    while (fgets(linea, 1024, archivo)) {
        Viaje viaje;
        sscanf(linea, "%d,%d,%d,%f,%f,%f,%f",
            &viaje.sourceid,
            &viaje.dstid,
            &viaje.hod,
            &viaje.mean_travel_time,
            &viaje.standard_deviation_travel_time,
            &viaje.geometric_mean_travel_time,
            &viaje.geometric_standard_deviation_travel_time
        );
        insertar_en_lista(viaje, tabla_hash);
    }
    fclose(archivo);

    // 统计每个桶的记录数
    int conteo[casillas] = {0};
    for (int i = 0; i < casillas; i++) {
        Nodo* nodo_actual = tabla_hash[i];
        while (nodo_actual) {
            conteo[i]++;
            nodo_actual = nodo_actual->siguiente;
        }
    }

    // 计算每个桶的起始偏移量，第一个桶的偏移量是偏移量数组的大小
    long long offsets[casillas];
    offsets[0] = casillas * sizeof(long long); // 前面存casillas个偏移量
    for (int i = 1; i < casillas; i++) {
        offsets[i] = offsets[i-1] + conteo[i-1] * sizeof(Viaje);
    }

    // 写入二进制文件：先写偏移量，再写记录
    archivo = fopen("index.bin", "wb");
    if (!archivo) {
        perror("无法创建索引文件");
        return 1;
    }
    // 写入偏移量数组
    fwrite(offsets, sizeof(long long), casillas, archivo);
    // 写入每个桶的记录
    for (int i = 0; i < casillas; i++) {
        Nodo* nodo_actual = tabla_hash[i];
        while (nodo_actual) {
            fwrite(&nodo_actual->viaje, sizeof(Viaje), 1, archivo);
            nodo_actual = nodo_actual->siguiente;
        }
        // 释放链表内存
        Nodo* temp;
        while (tabla_hash[i]) {
            temp = tabla_hash[i];
            tabla_hash[i] = tabla_hash[i]->siguiente;
            free(temp);
        }
    }
    fclose(archivo);
    return 0;
}

修改后的查询代码 #

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

#define casillas 1160

typedef struct {
    int sourceid;
    int dstid;
    int hod;
    float mean_travel_time;
    float standard_deviation_travel_time;
    float geometric_mean_travel_time;
    float geometric_standard_deviation_travel_time;
} Viaje;

int hash(int sourceid) {
    return sourceid % casillas;
}

float buscarTiempoViaje(int sourceid, int dstid, int hod, FILE* archivo) {
    int indice = hash(sourceid);
    Viaje viaje;
    long long offsets[casillas];

    // 先读取偏移量数组
    rewind(archivo);
    fread(offsets, sizeof(long long), casillas, archivo);

    // 定位到对应桶的起始位置
    int result = fseek(archivo, offsets[indice], SEEK_SET);
    if(result < 0){
        perror("无法定位到对应桶的起始位置");
        exit(-1);
    }

    // 计算当前桶的结束位置：下一个桶的起始偏移量（如果是最后一个桶，读到文件末尾）
    long long end_offset;
    if (indice == casillas - 1) {
        fseek(archivo, 0, SEEK_END);
        end_offset = ftell(archivo);
        fseek(archivo, offsets[indice], SEEK_SET);
    } else {
        end_offset = offsets[indice + 1];
    }

    // 遍历当前桶的所有记录
    while (ftell(archivo) < end_offset && fread(&viaje, sizeof(Viaje), 1, archivo) == 1) {
        if (viaje.sourceid == sourceid && viaje.dstid == dstid && viaje.hod == hod) {
            return viaje.mean_travel_time;
        }
    }

    // 未找到记录
    printf("NA\n");
    return -1;
}

// 示例main函数
int main() {
    FILE* archivo = fopen("index.bin", "rb");
    if (!archivo) {
        perror("无法打开索引文件");
        return 1;
    }
    float tiempo = buscarTiempoViaje(1140, 123, 5, archivo);
    if (tiempo != -1) {
        printf("平均出行时间：%.2f\n", tiempo);
    }
    fclose(archivo);
    return 0;
}

内容的提问来源于stack exchange，提问作者Dan-code-str