如何初始化哈希表以存储在 C 文件中

Question

我正在尝试使用线性探测在 C 中实现一个固定大小的哈希表来解决碰撞问题。此哈希表将存储在文件中，以便以后通过生成的哈希值进行(和快速(检索。我已经处理了大部分扭结，但我似乎卡在初始化我将使用的表时。我认为使用我正在注册的结构类型的数组，然后将所有值初始化为 NULL 或空白"是要走的路，但现在我不太确定。

我也不确定检索过程将如何工作。我还没有在网上找到任何有用的资源来描述C语言。检索特定索引的信息时，我是否需要在内存中加载整个哈希表(这似乎不切实际(，或者是否有办法加载特定索引内容(也许使用 lseek 来定位正确的文件位置(？

我只包含与哈希表初始化相关的代码，但如果您需要更多，请告诉我。提前致谢：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#define HSZ 10
struct client{
char last_name[80];
char maiden_name[80];
char name[80];
}client;
void init_array(){
int fd, i;
int bucket_no = 0;
struct client buff;
if ((fd = open("output", O_RDWR|O_CREAT,0777))<0){
perror("Inside init function: ");
printf("There was a problem initializing the hash table!");
}
for (i = 0; i<HSZ; i++){
strcpy(buff.name,"_");
strcpy(buff.last_name,"_");
strcpy(buff.maiden_name,"_");
lseek(fd, sizeof client * bucket_no, SEEK_SET);
write(fd, &buff, sizeof client);
bucket_no++;
}
close(fd);
}

Answer 1

您可以使用mmap.它基本上允许您像访问数组一样访问文件。

struct stat s = stat(filename, &s);
size_t size = s.st_size;
int fd = open(filename, O_RDONLY, 0);
struct client *map = mmap(NULL, size, PROT_READ, fd, 0);

https://man7.org/linux/man-pages/man2/mmap.2.html

Answer 2

虽然mmap()可能是最简单的方法，但只要每个存储桶都是固定大小(如您的示例所示(，在读取给定的偏移量之前，很容易计算要在文件中查找的偏移量 - 或者使用pread()在一个文件中执行两个步骤。

类似的东西

int bucket_number = 4; // 0 based like an array
struct client bucket;
lseek(hash_fd, sizeof bucket * bucket_number, SEEK_SET);
read(hash_fd, &bucket, sizeof bucket);

或

pread(hash_fd, &bucket, sizeof bucket, sizeof bucket * bucket_number);

对于将存储桶写入文件，请使用具有相同数学类型的write()或pwrite()- 或者在创建文件时一次写入整个数组的值。