所以我做这个项目只是为了刷新哈希表和一些C库。
我已经实现了一般的哈希函数和使用文件I/o的基本表所需的一切。但是当我试图思考如何去调整表的大小时，我卡住了。
我想知道是否最好将数据从我的表复制到一个新的…或者只是初始化一个新的哈希表当第一个填充…
我的困惑主要在于如何有效地将一个哈希表的值复制到一个新的哈希表文件中，以及如何处理之前文件的无用内存分配
下面是我的代码:#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
int currSize = 0;
int tableSize = 25;
typedef struct mydata_tag{
int used;
/* 0 - empty 1- used */
int key;
char name[25];
char ailment[30];
char insurance[30];
char social[10];
} mydata;
int setInfo(mydata * data)
{
printf("What is the client's ailment?");
scanf("%s", data->ailment);
printf("What is the client's insurance provider?");
scanf("%s", data->insurance);
printf("What is the client's Social Security Number?");
scanf("%s", data->social);
}
int hashKey(char * name){
int key, len, i;
key = 0;
len = strlen(name);
for(i = 0; i < len; i++)
{
key += name[i] * 10;
}
key %= 19;
key %= 7;
return key;
}
void init_table(char *filename, int size)
{
if(!filename || size < 1)
{
exit(1);
}
currSize++;
FILE * fp;
mydata data;
int i;
memset(&data, 0, sizeof(data));
fp = fopen(filename, "w+"); //create file with write capabilities
for(i = 0; i < size; i++)//initialize table
{
fwrite(&data, sizeof(mydata), i, fp);
}
}
void insert_data(double key, char *name, char *filename)
{
if(!name || !filename)
{
exit(1);
}
FILE * fp;
mydata data, slot;
int pos;
pos = key;
data.used = 1;
data.key = key;
strcpy(data.name, name);
setInfo(&data);
fp = fopen(filename, "r+");
while(1)
{
fseek(fp, pos*sizeof(mydata), SEEK_SET);
fread(&slot, sizeof(mydata), 1, fp);
if(slot.used != 1)
{
break;
}
printf("COLLISION!n");
pos++;
pos %= 19;
pos %= 7;
}
printf("pos = %dn", pos);
printf("key = %dn", data.key);
fseek(fp, pos*sizeof(mydata), SEEK_SET);
fwrite(&data, sizeof(mydata), 1, fp);
fclose(fp);
}
void print_buckets(char * filename)
{
FILE * fp;
mydata data;
int i;
fp = fopen(filename, "r+");
if(fp == NULL)
{
perror("fopen: print_buckets");
exit(1);
}
for(i = 0; i < 25; i++)
{
fread(&data, sizeof(mydata), 1, fp);
if(data.used == 1){
printf("used = %d n key = %d n Name = %sn Ailment: %s n",
data.used, data.key, data.name, data.ailment);
}
}
fclose(fp);
}
int main(int argc, char** argv) {
int i, key;
init_table("myhashtable", tableSize);
while(1)
{
char choice[1];
printf("----------Menu-----------n");
printf("------(A)dd Client-------n");
printf("---(P)rint Client List---n");
printf("---------(E)xit----------n");
scanf("%s", &choice);
if(choice[0] == 'e' || choice[0] == 'E'){break;}
else if(choice[0] == 'a' || choice[0] == 'A')
{
char name[20];
printf("What is the clients name?");
scanf("%s", &name);
key = hashKey(name);
insert_data(key, name, "myhashtable");
}else if(choice[0] == 'p' || choice[0] == 'P'){
print_buckets("myhashtable");
}
}
return (EXIT_SUCCESS);
}
编辑:这是一个古老而愚蠢的问题，无视
我不知道你是怎么想到的
key %= 19
key %= 7
但我觉得这很可疑，而且可能是错误的。
使用素数背后的基本思想是好的，但是%是模运算，因此第一行之后的key将在[0,18]范围内，第二行之后的[0,6]，因此只有7个可能的哈希值。
这样做会更好:
for(i = 0; i < len; i++)
key = 19*key + name[i];
key % tableSize;
简单地将每个值乘以10(就像你所做的那样)并不理想，因为abc和cab将具有相同的哈希值-你希望它们的权重不同，即第一个值乘以1，第二个乘以10，第三个乘以100，等等-在这里使用素数有助于减少冲突。
使tableSize为素数也有助于减少冲突。
对素数除法取两次模没有帮助。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ...
% 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 2 3 4 5 6 ...
% 7 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 0 1 2 3 4 5 6 ...
看看19发生了什么-我们跳过了5和6 -这并不好-这意味着0-4更有可能发生，因此立即增加了这些冲突的机会。
无论如何，您都需要重新散列所有内容(因为如果文件大小改变，散列值可能会改变，并且由于冲突而偏移的条目可能不再偏移)，因此是否使用相同的文件或其他文件并不重要-您仍然需要读取所有内容，并写入所有内容。
请记住，使用相同的文件会增加复杂性-在擦除文件并开始再次写入之前，您需要有一个内存结构来存储所有数据。使用单独的文件，您可能只需要对代码进行微小的更改。
如果整个文件不能放入内存中(这是您选择使用文件而不是内存结构的原因之一)，除了使用其他文件之外，您没有其他选择，因为中间的内存结构将无法选择。
处理完旧文件后，可以直接删除。