HashTable 插入和查找的指针问题

Question

我正在使用来自 github 的数据结构的自定义 C 实现。此处的文档：http://fragglet.github.io/c-algorithms/doc/

这是我第一次使用这种低级别的 HashTable，当我恢复之前插入的值时遇到了一些指针问题。

我的代码只是一个简单的测试，只需要插入和恢复数据。

#include "list.h"
#include "hash-table.h"
#include <stdio.h>

//typedef unsigned int (*HashTableHashFunc)(HashTableKey value);
unsigned int hashFunc(HashTableKey v_key)
{
    unsigned int *key = (unsigned int *)v_key;
    return *key % 20;
}

//typedef int (*HashTableEqualFunc)(HashTableKey value1, HashTableKey value2);
int equalFunc(HashTableKey value1, HashTableKey value2)
{
    int *key1 = (int *)value1;
    int *key2 = (int *)value2;
    return *key1 == *key2;
}

int main(int argc, char const *argv[])
{
    HashTable *mapMatrices;
    //ListEntry *posicionListaPeticiones;

    mapMatrices = hash_table_new(hashFunc, equalFunc);

    for (int i = 0; i < 10; i++)
    {
        int key = i;
        int value = i * 200;
        int stat = hash_table_insert(mapMatrices, &key, &value);
        if (!stat)
            printf("Error inserting key %i with value %i\n", key, value);
        else
            printf("Inserted key %i with value %i\n", key, value);
    }

    for (int i = 0; i < 10; i++)
    {
        int key = i;
        void *v_value = hash_table_lookup(mapMatrices, &key);
        int value = *(int *)v_value;
        printf("Key pointer %x : Value pointer %x\n", &key, &value);
    }
}

如果我打印数据地址，这是我的输出

Inserted key 0 with value 0
Inserted key 1 with value 200
Inserted key 2 with value 400
Inserted key 3 with value 600
Inserted key 4 with value 800
Inserted key 5 with value 1000
Inserted key 6 with value 1200
Inserted key 7 with value 1400
Inserted key 8 with value 1600
Inserted key 9 with value 1800
Key ed75a354 : Value pointer ed75a358
Key ed75a354 : Value pointer ed75a358
Key ed75a354 : Value pointer ed75a358
Key ed75a354 : Value pointer ed75a358
Key ed75a354 : Value pointer ed75a358
Key ed75a354 : Value pointer ed75a358
Key ed75a354 : Value pointer ed75a358
Key ed75a354 : Value pointer ed75a358
Key ed75a354 : Value pointer ed75a358
Key ed75a354 : Value pointer ed75a358

这就是我尝试打印地址内容后发生的情况

printf("Key %i : Value pointer %i\n", key, value);

Inserted key 1 with value 200
Inserted key 2 with value 400
Inserted key 3 with value 600
Inserted key 4 with value 800
Inserted key 5 with value 1000
Inserted key 6 with value 1200
Inserted key 7 with value 1400
Inserted key 8 with value 1600
Inserted key 9 with value 1800
Segmentation fault (core dumped)

HashTable的实现代码

HashTable *hash_table_new(HashTableHashFunc hash_func,
                          HashTableEqualFunc equal_func)
{
    HashTable *hash_table;

    /* Allocate a new hash table structure */

    hash_table = (HashTable *) malloc(sizeof(HashTable));

    if (hash_table == NULL) {
        return NULL;
    }

    hash_table->hash_func = hash_func;
    hash_table->equal_func = equal_func;
    hash_table->key_free_func = NULL;
    hash_table->value_free_func = NULL;
    hash_table->entries = 0;
    hash_table->prime_index = 0;

    /* Allocate the table */

    if (!hash_table_allocate_table(hash_table)) {
        free(hash_table);

        return NULL;
    }

    return hash_table;
}

int hash_table_insert(HashTable *hash_table, HashTableKey key,
                      HashTableValue value)
{
    HashTableEntry *rover;
    HashTablePair *pair;
    HashTableEntry *newentry;
    unsigned int index;

    /* If there are too many items in the table with respect to the table
     * size, the number of hash collisions increases and performance
     * decreases. Enlarge the table size to prevent this happening */

    if ((hash_table->entries * 3) / hash_table->table_size > 0) {

        /* Table is more than 1/3 full */

        if (!hash_table_enlarge(hash_table)) {

            /* Failed to enlarge the table */

            return 0;
        }
    }

    /* Generate the hash of the key and hence the index into the table */

    index = hash_table->hash_func(key) % hash_table->table_size;

    /* Traverse the chain at this location and look for an existing
     * entry with the same key */

    rover = hash_table->table[index];

    while (rover != NULL) {

        /* Fetch rover's HashTablePair entry */

        pair = &(rover->pair);

        if (hash_table->equal_func(pair->key, key) != 0) {

            /* Same key: overwrite this entry with new data */

            /* If there is a value free function, free the old data
             * before adding in the new data */

            if (hash_table->value_free_func != NULL) {
                hash_table->value_free_func(pair->value);
            }

            /* Same with the key: use the new key value and free
             * the old one */

            if (hash_table->key_free_func != NULL) {
                hash_table->key_free_func(pair->key);
            }

            pair->key = key;
            pair->value = value;

            /* Finished */

            return 1;
        }

        rover = rover->next;
    }

    /* Not in the hash table yet.  Create a new entry */

    newentry = (HashTableEntry *) malloc(sizeof(HashTableEntry));

    if (newentry == NULL) {
        return 0;
    }

    newentry->pair.key = key;
    newentry->pair.value = value;

    /* Link into the list */

    newentry->next = hash_table->table[index];
    hash_table->table[index] = newentry;

    /* Maintain the count of the number of entries */

    ++hash_table->entries;

    /* Added successfully */

    return 1;
}

HashTableValue hash_table_lookup(HashTable *hash_table, HashTableKey key)
{
    HashTableEntry *rover;
    HashTablePair *pair;
    unsigned int index;

    /* Generate the hash of the key and hence the index into the table */

    index = hash_table->hash_func(key) % hash_table->table_size;

    /* Walk the chain at this index until the corresponding entry is
     * found */

    rover = hash_table->table[index];

    while (rover != NULL) {
        pair = &(rover->pair);

        if (hash_table->equal_func(key, pair->key) != 0) {

            /* Found the entry.  Return the data. */

            return pair->value;
        }

        rover = rover->next;
    }

    /* Not found */

    return HASH_TABLE_NULL;
}

Answer 1

您的指针有些混乱。如果替换：

for (int i = 0; ...

和

int i;
for (i = 0; ...

对于 main 中的第一个循环，以及：

for (i = 0;...

在第二个循环中，您将得到您期望的输出。

如果您将此行添加到您的 equalFunc：

fprintf(stderr,"cmp %p/%d, %p/%d\n", key1, *key1, key2, *key2);

您会注意到 equalFunc 的两个参数始终相同——它们实际上指向您的本地“i”变量。这就是为什么这不适用于两个单独的“i”值。

使用调试器的时刻将显示：

void *v_value = hash_table_lookup(mapMatrices, &i);

returns 源代码中为 NULL [即。未找到 ]，但您还是继续取消引用它。

为了让你的程序正确，你应该按值传递你的键，而不是引用：

int stat = hash_table_insert(mapMatrices, (int *)i, (int *)value);
...
void *v_value = hash_table_lookup(mapMatrices, (int *)i);
int value = (int )v_value;
...
/* equalFunc: */
return (int)value1 == (int)value2;

但出于卫生原因，请使用 intptr_t 和无关的演员表，以免未定义行为的邪恶之神烧毁你的家。

HashTable 插入和查找的指针问题

Pointer problem with HashTable insertion and lookup

c

hashtable