1

所以我在这个项目上工作只是为了刷新哈希表和一些 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 = %d\n", pos);
    printf("key = %d\n", 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 = %s\n 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);
}

编辑：这是一个古老而愚蠢的问题，无视

4

1 回答 1

2

我不知道你是怎么想出来的

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's 更有可能发生，因此立即增加了那些发生冲突的机会。

无论如何，您都需要重新散列所有内容（因为如果文件大小发生变化，散列值可能会发生变化，并且因冲突而偏移的条目可能不再被偏移），因此无论您使用同一个文件还是另一个文件并不重要- 您仍然需要阅读所有内容并编写所有内容。

请记住，使用相同的文件会增加复杂性——在擦除文件并再次开始写入之前，您需要有一个内存结构来存储所有数据。使用单独的文件，您可能只需稍作更改即可使用您的代码。

如果整个文件无法放入内存（这是您选择使用文件而不是内存结构的原因之一），那么除了使用不同的文件之外，您实际上别无选择，因为中间内存结构胜出不是一个选择。

完成旧文件后，您可以将其删除。

于 2014-05-09T23:21:49.627 回答