c - C 中哈希表链接的问题

Question

我的入门 C 类作业是完成具有动态分配的哈希表的实现。我必须使用提供的头文件，但我不确定自己做错了什么。头文件:

/// structure for the nodes of the chains
struct node_s {
    char *key;
    int value;
    struct node_s *link;
};

/// This is the main structure for the overall table.
struct table_s {
    /// This should be used as a pointer to a dynamically
    /// allocated array of pointers to node structures.
    struct node_s **table;

    /// This is for storing the maximum number of buckets/lists in the table.
    size_t bins;

    /// This is for storing the current number of elements in the table
    size_t size;
};
    /// A convenience declaration for referring to a pointer to a HT..
    typedef struct table_s *hash_t;

我需要实现的:

/// Allocate a table with some initial empty bins.
/// @param bins -- the number of bins in the table (initally empty)
/// @return -- a pointer to a dynamically allocated hash table
hash_t create_table(int bins){
        struct node_s *nodes[bins];
        for(int i = 0; i < bins; i++){
                nodes[i] = NULL;
        }
        hash_t table = malloc(sizeof(hash_t));
        table -> table = nodes;
        table -> bins = bins;
        table -> size = 0;
        return table;
}

/// Set the value for a key in a given hash table.
/// @note -- if this is the first time setting this key, then the
///          table must make a dynamic copy of the string.  This
///          copy must be freed when the table is freed.
/// @note -- if the table exceeds a load factor of 1 after setting
///          the key/value pair, then this function should trigger
///          rehashing into a larger table.  It will then deallocate
///          the table field in the table_s structure, but it will
///          NOT free the table address in the table parameter.
/// @param table -- a pointer to a hash table

void set(hash_t table, char *key, int value){
        int index = hash(key) % table -> bins;
        printf("Index: %d\n", index);
        struct node_s *node = table -> table[index];
        struct node_s *newNode = malloc(sizeof(newNode));
        newNode -> key  = key;
        newNode -> value = value;
        newNode -> link = NULL;

        printf("New node, key: %s\n", newNode -> key);
        if(node == NULL){
                printf("Filled bucket!\n");
                table -> table[index] = newNode;
                table -> size = table -> size + 1;
        }else{
                printf("Chained!\n");
                while(node -> link != NULL){
                        node = node -> link;
                }
                node -> link  = newNode;
        }
        printf("\n");
}

什么运行:

 char key[max_key];
    hash_t table = create_table(10);
    for (int i = 0; i < trials; i++) {
        int sample = rand() % max_num;
        sprintf(key, "%d", sample);
        set(table, key, sample);
    }

输出:

Index: 7
New node, index: 7, key: 83
NULL!
New bucket filled!

Index: 0
New node, index: 0, key: 86
NOT NULL!
Segmentation fault (core dumped)

预期输出:

Index: 7
New node, index: 7, key: 83
NULL!
New bucket filled!

Index: 0
New node, index: 0, key: 86
NULL!
New bucket filled!

依此类推，直到索引处的节点不为 NULL 时发生冲突，此时 newNode 通过替换存在的最后一个节点的 NULL *链接来链接自身。

我知道我的链接还不是很正确，需要扩展，但我真的很困惑为什么它不在索引处注册 NULL 并放置一个新的链表节点，而是试图添加到链接列表中，就好像发生了冲突一样。

Answer 1

编码提示:不要在点 . 或箭头 -> 运算符之前/之后放置空格。

取而代之的是:

table -> bins

这个:

table->bins

您的实际问题是这样的。 create_table 没有正确地为 bin 分配内存。更糟糕的是，它在堆栈上使用了一个数组。一旦 create_table 返回，该内存就是未定义的行为。更好:

hash_t create_table(int bins){
        hash_t table = malloc(sizeof(hash_t));
        table->table = calloc(sizeof(struct node_s*) * bins); //malloc and zero-init
        table->bins = bins
        table->size = 0;
        return table;
}

此外，代替这个:

        if(node == NULL){
                printf("Filled bucket!\n");
                table -> table[index] = newNode;
                table -> size = table -> size + 1;
        }else{
                printf("Chained!\n");
                while(node -> link != NULL){
                        node = node -> link;
                }
                node -> link  = newNode;
        }

只需这样做:

printf("%s\n", (table->table[index] ? "Filled bucked!" : "Chained!"));
newNode->link = table->table[index];
table->table[index] = newNode;

每次将一个新节点添加到容器中时，它就会成为容器链表中的头项。链接发生在每个 bin 列表的前面而不是后面。