关于#哈希函数#的问题，如何解决？

Question

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

#define MAX_PERSONS 100000    // hash table size - experiment with different values
#define MAX_NAME_LENGTH 50
#define COUNTRY_CODE_LENGTH 4
#define AREA_CODE_LENGTH 4
#define LOCAL_NUMBER_LENGTH 8

// struct to store a persosn name and phone nummber details
typedef struct person {
    char *first_name;
    char *last_name;
    char *fullName;
    char *countryCode;
    char *areaCode;
    char *localNumber;
    
} person_struct;

// global variables for printing status infomation
int collision = 0;
int longest_probing_sequence = 0;

// The bad hash function! TODO: Implement a better hesh function!
int count_hash(int mod, char* fullName, int fullNameLength) {
    int i;
    int hash = 0;
    for(i=0; i < fullNameLength; i++){
        hash = (hash + fullName[i])%mod;
    }
    return hash;
}

/**
 function to insert a person into the hash table
 (maybe not the best way to do it, but will have to do for now)
 the key used for a person is the first name and last name together
 TODO:    I this function you will find the probing method
     You need to implement a better one.
*/
int insertPerson(    person_struct *name_store,
            char *fi_name,
            char *la_name,
            char *c_code,
            char *a_code,
            char *l_number,
            int *allPersons) {
    int i;
    int hash,firsthash;
    
    // Allocating memory for person information
    int fiNameLength = strlen(fi_name);
    char *tempFiName = malloc(fiNameLength*sizeof(char)+1);
    int laNameLength = strlen(la_name);
    char *tempLaName = malloc(laNameLength*sizeof(char)+1);
    int coCodeLength = strlen(c_code);
    char *tempCoCode = malloc(coCodeLength*sizeof(char)+1);
    int arCodeLength = strlen(a_code);
    char *tempArCode = malloc(arCodeLength*sizeof(char)+1);
    int loNumberLength = strlen(l_number);
    char *tempLoNumber = malloc(loNumberLength*sizeof(char)+1);
    int fullNameLength = MAX_NAME_LENGTH*2;
    char *tempFullName = malloc(fullNameLength*sizeof(char)+1);

    strcpy(tempFiName, fi_name);
    strcpy(tempLaName, la_name);
    strcpy(tempCoCode, c_code);
    strcpy(tempArCode, a_code);
    strcpy(tempLoNumber, l_number);
    
    //concatenating first name and last name into a variable for the key
    strcpy(tempFullName, tempFiName);
    strcat(tempFullName, tempLaName);
    
    //changeing the key to capital letters
    for (i=0; i < fullNameLength; i++) {
        tempFullName[i] = toupper(tempFullName[i]);
    }
    tempFullName[i] = 0;

    // counter for number of persons stored in the hash table
    *allPersons = *allPersons+1;

    // compute hash for the key
    hash = count_hash(MAX_PERSONS, tempFullName, fullNameLength);
    
    // insert person into hash table
    firsthash = hash;
    int probing = 0;
    int stored = 0;
    while (stored == 0) {
        if (name_store[hash].fullName != 0) {
            // Linear probing used a probing method
            // TODO: Implement better probing method
            hash = (hash+1)%MAX_PERSONS;
            collision++;
            probing++;
            
            //Check if hashtable full
            if (hash == firsthash) {
                return 0;
            }
        }
        else {
            person_struct person;
            person.first_name = tempFiName;
            person.last_name = tempLaName;
            person.fullName = tempFullName;
            person.countryCode = tempCoCode;
            person.areaCode = tempArCode;
            person.localNumber = tempLoNumber;
            name_store[hash] = person;
            stored = 1;
        }
    }
    if (probing > longest_probing_sequence) {
        longest_probing_sequence = probing;
    }
    return 1;
}

/**
 TODO: Implement function to find person
 Note that a character array cannot be directly copied
 Note also that you must use the same probing mehtod as in insert in case of collisions
 @param name_storage - the the hash table where the persons have been stored
 @param personToFind - the full name of person to find
 @return 0 if person was not found
*/
int findPerson(person_struct *name_storage, char* personToFind) {
    printf("\nSearching...\n");
    return 0;
}

// main function
int main() {
    FILE *personFile;
    //person_struct persons[MAX_PERSONS+1];
    // allocate memory for hash table and initialize needed variables
    person_struct *persons = (person_struct *)malloc(sizeof(person_struct)*(MAX_PERSONS+1));
    char firstName[MAX_NAME_LENGTH];
    char lastName[MAX_NAME_LENGTH];
    char countryCode[COUNTRY_CODE_LENGTH];
    char areaCode[AREA_CODE_LENGTH];
    char localNumber[LOCAL_NUMBER_LENGTH];
    int personCount = 0;
    double totaltime;
    clock_t start,end;
    int i;
    int full = 0;

    // get input file name from user
    char fileName[500];
    printf("Type filename:  > ");
    scanf("%s",fileName);

    personFile = fopen(fileName,"r");

    if (personFile == NULL){
        printf("NO SUCH FILE!\n");
        return 0;
    }

    char garbage[1000];

    // measure time for inserting all persons into the hash table
    start = clock();
    
    // reade lines while not end of file
    while (fscanf(personFile, "%[^,], %[^,], %[^,], %[^,], %[^\n]", firstName, lastName, countryCode, areaCode, localNumber) != EOF) {
        // try to insert person into hash table
        if (insertPerson(persons, firstName, lastName, countryCode, areaCode, localNumber, &personCount) == 0){
            printf("Hash table full. File not processed completely!\n");
            full = 1;
            break;
        }

        if (fscanf(personFile, "%999[^a-zA-Z']", garbage) == EOF) {
            // End of file garbage
            break;
        }
    }

    fclose(personFile);
    
    end = clock();

    // printing status information
    if (full == 0) {
        printf("Total number persons inserted: %d\n",personCount);
        printf("\n\nFillrate is: %f%%\n", (personCount/(double)MAX_PERSONS)*100.00);
        printf("Total number of collisions: %d\n", collision);
        printf("Longest probing sequece: %d\n", longest_probing_sequence);
    }

    totaltime = (double)(end-start)/CLOCKS_PER_SEC;
    printf("\n\nTime for inserting %f seconds\n", totaltime);
    
    // measure time to find a person
    start = clock();
    
    // Searching for one person
    char searchPersonFullName[MAX_NAME_LENGTH*2] = "Tian Alphonse JinchengAnguissola";
    // use findPeso() function to get place of the hash table where the person should be
    int place = findPerson(persons, searchPersonFullName);
    // print detials of person if found, else inform that the person was not found
    
    end = clock();
    
    if (place != 0) {
        printf("Found\n");
        printf("%s ", persons[place].first_name);
        printf("%s ", persons[place].last_name);
        printf("%s ", persons[place].countryCode);
        printf("%s ", persons[place].areaCode);
        printf("%s\n", persons[place].localNumber);
    }
    else {
        printf("Not found\n");
    }
    
    totaltime = (double)(end-start)/CLOCKS_PER_SEC;
    printf("\n\nTime searching %f seconds\n", totaltime);
    
    // Free all person elements from memory
    for (i=0; i <= MAX_PERSONS; i++) {
        if (persons[i].fullName != 0) {
            free(persons[i].last_name);
            free(persons[i].first_name);
            free(persons[i].countryCode);
            free(persons[i].areaCode);
            free(persons[i].localNumber);
        }
    }
    // Free the table
    free(persons);
    return 0;
}

注意!提交时:

•必要时压缩所有文件

•不要包含可执行文件

文件扩展名为。c

在文件名、注释和代码中使用英文

在Moodle中，你可以找到源代码文件phonebook_for_students.c

你将在这个练习中练习。此外，您将发现包含

不同数量的名字和电话号码(这些不是真实的名字和

数字，它们已经生成了)。您可以运行源代码文件。它要求

您需要输入一个文本文件。使用给定的文件。然后程序尝试全部插入

人员和他们的数字组成一个哈希表结构。一旦完成，它就会尝试

从哈希表中找一个人。这不会起作用，因为它没有

已经实现了。研究代码和注释以了解它是如何实现的

的工作原理。查看关于哈希表的幻灯片和视频来帮助你

理解。

1点-找到计算哈希值的函数。这不是一件好事

解决方案。你的任务是实现一个更好的哈希函数。观察

运行时间!越快越好。也要观察总计的打印输出

碰撞次数和最长探测序列。实验

不同的哈希函数。还可以尝试哈希表的大小。不要尝试

大文件与糟糕的哈希函数!这要花很长时间!

1点-找到探测方法。它使用线性探测作为探测

方法。您的任务是实现一种不同的探测方法。实验

不同的探测方法。你也可以尝试不同的哈希函数

不同的探测方法。观察这些如何影响碰撞的数量

以及探测序列的长度。还可以尝试不同大小的散列

表格观察运行时间。

1点-找到应该从哈希中找到一个人的函数

表格您的任务就是实现这个函数。重复使用已经有的东西

送给你。如果你不知道如何处理字符串，请寻求帮助

(char数组)。

在下一页，你会发现一个表，指定输入文件，数量

每个文件中的人，以及他们是否搜索人应该找到

在文件中。

Answer 1

该回答引用GPTᴼᴾᴱᴺᴬᴵ
这个代码实现了一个哈希表，但是哈希函数采用了一个简单的计数哈希。需要改进哈希函数，以减少冲突。改进后，还需要修改插入和查找函数，以便使用新的哈希函数。

改进哈希函数的方法很多，以下是一些常见的方法：

1. 求余数哈希
   求余数哈希是计算哈希值的常见方法。这种方法需要选择一个素数作为哈希表大小，然后将键的字符值相加，然后将结果取模。例如，如果哈希表大小为N，键的字符值为c1, c2, c3等，则哈希值为：(c1 + c2 + c3 + ...) % N。这种方法可以产生比计数哈希更好的分布，但是如果哈希表大小不是素数，就可能会出现不均匀的哈希值分布。

2. 多项式哈希
   多项式哈希是一种计算哈希值的方法，它将键的字符值视为多项式的系数。例如，如果键是"abcd"，则其哈希值可以表示为：a * p^3 + b * p^2 + c * p + d，其中p是一个素数。这种方法可以产生非常好的哈希值分布，并且可以通过选择不同的p值来减少冲突。

3. 布谷鸟哈希
   布谷鸟哈希是一种更高级的哈希函数，它可以在O(1)的时间内完成插入和查找操作。它的基本思想是将哈希表分成多个小部分，每个小部分都可以包含多个键。当哈希函数计算出键的哈希值后，它会在所属的小部分中查找是否已经存在相同的键。如果存在，它会将该键移动到另一个小部分中，并在新的小部分中插入该键。这个过程会一直重复，直到没有更多的冲突发生为止。

在这里，我们选择第一个方法，即求余数哈希。

下面是改进后的哈希函数：

// improved hash function using modulo hashing
int modulo_hash(char* key, int table_size) {
    int hash = 0;
    while(*key) {
        hash = (hash * 31 + *key) % table_size;
        key++;
    }
    return hash;
}

我们还需要修改插入和查找函数，以便使用新的哈希函数。

下面是修改后的插入函数：

// improved insert function using modulo hashing
int insertPerson(person_struct *name_store, char *fi_name, char *la_name, char *c_code, char *a_code, char *l_number, int *allPersons) {
    int i;
    int hash, firsthash;
    char tempFullName[MAX_NAME_LENGTH*2+1];