c - 简单哈希表中的段错误

Question

我正在尝试用 C 编写一个简单的哈希表，但在使用我的 main() 显示的代码对其进行测试时遇到了一个非常奇怪的段错误。

设计:我有一个哈希表，其底层数组大小为 10,000。我持有一个指向 struct node_t(或 node)指针数组开头的双指针。当我想将某些内容put() 放入哈希表时，我会检查适当位置的node 元素是否为NULL。如果是，我会创建一个新节点来填充该位置，否则，如果存在冲突，我会从冲突节点构建一个链表。

场景:在main() 中，我试图将数字3328 put() 放入哈希表中。相反，程序会出现段错误。这对我来说毫无意义，因为前面的 put() 工作正常，您可以清楚地看到我将所有初始指针设置为 NULL。据我所知，指向哈希表位置 3328 的指针未设置为 NULL，因为当我在 put() 函数中取消引用它时，它就会出现段错误。我的主要功能看起来应该将所有指针设置为 NULL 就好了......

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

int TABLE_SIZE = 10000;

typedef struct node_t {
    int key;
    int value;
    struct node_t* next;
} node;

node** table;

inline node** get_node_address(int key) {
    key = (key > -key ? key : -key) % TABLE_SIZE;
    return (node**) (table + key * sizeof(node*)); 
}

inline node* new_node(int key, int value) {
    node* n = malloc(sizeof(node));
    n->key = key;
    n->value = value;
    n->next = NULL;
    return n;
}

void put(int key, int value) {
    node** n = (node**) get_node_address(key);
    node* iterator = (node*) *n;

    if (*n == NULL) {
        *n = new_node(key, value);
    } else {
        while (iterator->next != NULL)
            iterator = iterator->next;

        iterator->next = new_node(key, value);
    }
}

int* get(int key) {
    node* iterator = (node*) *get_node_address(key);

    while (iterator != NULL && iterator->key != key) {
        iterator = iterator->next;
    }

    if (iterator == NULL)
        return NULL;
    else
        return &(iterator->value); 
}

int main() {
    printf("Starting..\n");

    int i;
    table = malloc(sizeof(node*) * TABLE_SIZE);
    memset(table, 0, sizeof(node*) * TABLE_SIZE);

    for (i = 0; i < TABLE_SIZE; i++) {
        table[i] = NULL;
        printf("setting %x\n", &table[i]);
    }

    printf("before bad: %x\n", *get_node_address(3327));
    printf("bad address: %x\n", *get_node_address(3328));
    printf("last address: %x\n", table + sizeof(node*) * TABLE_SIZE);

    printf("Hashing...\n");

    put(3328, 3338);
    printf("%d", *get(3328));

    return 0;
}

Answer 1

至少有一个问题:

inline node** get_node_address(int key) {
      key = (key > -key ? key : -key) % TABLE_SIZE;
      return (node**) (table + key * sizeof(node*)); /* <---- */
}

你不能乘以 key。由于指针算法在 C 中的工作方式，table + key 生成第 key 元素。