c - C中Hashtable的插入函数

Question

所以，我有这些功能。如何在 Hashtable 中插入数字？一直到表格大小的 for？我不知道 for 里面有什么，如果它存在的话。

#include <stdio.h>

//Structure
typedef struct Element {
    int key;
    int value;
} Element;

typedef struct HashTable {
    Element *table[11];
} HashTable;


//Create an empty Hash
HashTable* createHashTable() {
    HashTable *Raking = malloc(sizeof(HashTable));

    int i;
    for (i = 0; i < 11; i++) {
        Raking->table[i] = NULL;
    }
    return Raking;
}

//Insert element
void insertElement(HashTable *Raking, int key, int value) {

    int h = hashFunction(key);

    while(Raking->table[h] != NULL) {

        if(Raking->table[h]->key == key) {
            Raking->table[h]->value = value;
            break;
        }

        h = (h + 1) % 11;
    }

    if(Raking->table[h] == NULL) {
        Element *newElement = (Element*) malloc(sizeof(Element));
        newElement->key = key;
        newElement->value = value;
        Raking->table[h] = newElement;
    }
}

int main() {

    HashTable * Ranking = createHashTable();


    /** ??? **/


}

有人可以向我解释如何使用这些结构编写我的主要功能吗？在这种情况下，我正在修复此表中的元素数量，对吗？ (表 [11]) 我可以为用户做些什么来确定哈希表的大小？是否可以？还是我应该设置尺寸？

Answer 1

我已经对您的代码添加了注释和更改，我认为它们对您有用。我还对其进行了调整，以便不对大小进行硬编码。最后，我释放了所有 malloc 编辑的语句。

编译没有错误，我使用 valgrind 测试了它是否存在内存泄漏和其他错误，没有发现任何投诉。

如果有什么不清楚或者评论无法解释的地方，请告诉我。我已尝试尽可能多地遵循您的代码，但我没有机会正确测试功能。

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

//Structure
typedef struct Element {
    int key;
    int value;
} Element; /* you had a syntax error here */

typedef struct HashTable {
    int size; /* we will need the size for the traversal */
    Element *table; /* leave it as a pointer */
} HashTable; /* a syntax error here too */

HashTable* createHashTable(int size) {
    HashTable *Ranking = malloc(sizeof(HashTable));

    /* set the pointer to point to a dynamic array of size 'size' */
    /* this way you don't have to hardcode the size */
    Ranking->table = malloc(sizeof(Element) * size); 
    Ranking->size = size;

    /* initialisation is a bit different because we don't have pointers here */
    /* only table is a pointer, not its elements */
     int i;
     for (i = 0; i < size; i++) {
         Ranking->table[i].key = 0; 
         Ranking->table[i].value = 0;
     }

    return Ranking;
}

/* I implemented a fake hashFunction just to test the code */
/* all it does is make sure the key does not exceed the size of the table */
int hashFunction(int key, int size)
{
    return (key % size);
}

//Insert element
void insertElement(HashTable *Ranking, int key, int value) {

    int h = hashFunction(key, Ranking->size);
    int i = 0;

    /* if hash is full and key doesn't exist your previous loop would have gone on forever, I've added a check */
    /* also notice that I check if table[h] has empty key, not if it's null as this is not a pointer */
    while(Ranking->table[h].key != 0 && (i < Ranking->size)) {

        if(Ranking->table[h].key == key) {
            Ranking->table[h].value = value;
            return; /* break is intended to quit the loop, but actually we want to exit the function altogether */
        }

        h = (h + 1) % Ranking->size; /* changed 11 to the size specified */
        i++; /* advance the loop index */
    }

    /* okay found a free slot, store it there */
    if(Ranking->table[h].key == 0) {
        /* we now do direct assignment, no need for pointers */
        Ranking->table[h].key = key;
        Ranking->table[h].value = value;
    }
}

int main() {

    int size = 0;
    scanf(" %d", &size);

    HashTable *Ranking = createHashTable(size);

    insertElement(Ranking, 113, 10); /* this is just a test, 113 will be hashed to be less than size */

    /* we free everything we have malloc'ed */
    free(Ranking->table);
    free(Ranking);

    return 0;
}