带链接列表的哈希表在 c 中不起作用？

Question

我在 C 中使用链表（为了避免冲突）为散列 table 分配内存时遇到问题。

我认为问题出在物品的分配上。我做了两个结构，一个用于单个项目，一个用于 table。第一个有两个指向下一个和上一个项目的指针。请帮我。我在这个代码上停留了 3 天。代码：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define CAPACITY 50000 

unsigned long hash(char *str) { 
    unsigned long int stringsum = 0; 
    for(; *str != '[=10=]'; str++) { 
        stringsum += *str; 
    } 
    return stringsum % CAPACITY; 
    
} 


typedef struct item  { 
    char *value; 
    char *key; 
    struct item *next; 
    struct item *prev; 
} ht_item; 

typedef struct hashtable { 
    ht_item **items; 
    int dim; 
    int count; 
} HashTable; 

HashTable* create_table(int size); HashTable* create_item(HashTable *table, char *value, char *key); 
void print_table(HashTable* table, int dim); 


int main(void) { 
    HashTable *table = create_table(CAPACITY); 
    table = create_item(table, "Giuseppe", "Nome"); 
    print_table(table, CAPACITY); 
    return 0; 
    
} 


HashTable* create_item(HashTable *table, char *value, char *key) { 
    unsigned long index = hash(key);
    printf("%u", index); 
    ht_item *_iterator; ht_item *prev;
    for(_iterator = table->items[index], prev = NULL; _iterator != NULL; prev = _iterator, _iterator = _iterator->next);
     _iterator = (ht_item*)malloc(sizeof(ht_item));
     _iterator->key = (char*)malloc(200);
     _iterator->value = (char*)malloc(200); 
     strcpy(_iterator->key, key);
     strcpy(_iterator->value, value);
     _iterator->next = NULL;
     _iterator->prev = prev; 
    return table; 
} 


HashTable* create_table(int size)
{ 
    HashTable *table = (HashTable*)malloc(sizeof(HashTable));
    table->dim = size; 
    table->items = (ht_item**)calloc(size, sizeof(ht_item*)); 
    for(int i = 0; i < size; i++){ 
        table->items[i] = NULL; 
    } 
    
    return table; 
} 


void print_table(HashTable* table, int dim) { 
    for(int i = 0; i < CAPACITY; i++)
     { 
        if(table->items[i] != NULL)
         { ht_item *_iterator = (ht_item*)malloc(sizeof(ht_item));
             for(_iterator = table->items[i]; _iterator != NULL;
             _iterator = _iterator->next)
             { 
                printf("Key: %s\tValue: %s\n", _iterator->key, _iterator->value); 
                } free(_iterator); 
            } 
        } 
}

Answer 1

对您的代码进行了一些更改。请通读包含 // CHANGE HERE 评论的区块。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define CAPACITY 50000

// CHANGE HERE - additional parameter, value to be used for modulo
unsigned long hash(char *str, unsigned int mod_value) { 
    unsigned long int stringsum = 0; 
    for(; *str != '[=10=]'; str++) { 
        stringsum += *str; 
    }
    // CHANGE HERE - use mod_value instead of CAPACITY
    return stringsum % mod_value; 
    
} 


typedef struct item  { 
    char *value; 
    char *key; 
    struct item *next; 
    struct item *prev; 
} ht_item; 

typedef struct hashtable { 
    ht_item **items; 
    int dim; 
    int count; 
} HashTable; 

HashTable* create_table(int size); HashTable* create_item(HashTable *table, char *value, char *key); 
void print_table(HashTable* table, int dim); 


int main(void) { 
    HashTable *table = create_table(CAPACITY); 
    table = create_item(table, "Giuseppe", "Nome"); 
    print_table(table); 
    return 0; 
} 


HashTable* create_item(HashTable *table, char *value, char *key) {
    // CHANGE HERE - function arguments validation
    if (table == NULL)
    {
        return table;
    }
    if (value == NULL || key == NULL)
    {
        printf("Key or value is null\n");
        return table;
    }

    // CHANGE HERE - pass table->dim to hash
    unsigned long index = hash(key, table->dim);
    printf("Index: %lu\n", index);
    
    // CHANGE HERE - simplified the code a bit
    ht_item* new_node = malloc(sizeof(ht_item));
    new_node->key = malloc(200 * sizeof(char));
    strncpy(new_node->key, key, 200);
    new_node->value = malloc(200 * sizeof(char));
    strncpy(new_node->value, value, 200);
    
    // CHANGE HERE - if first node in index
    if (table->items[index] == NULL)
    {
        table->items[index] = new_node;
        return table;
    }
    
    ht_item *cur, *prev = NULL;
    for(cur = table->items[index]; cur != NULL; prev = cur, cur = cur->next);
    
    prev->next = new_node;  // CHANGE HERE - it seems this line was missing
    new_node->prev = prev;
    new_node->next = NULL;
    
    return table; 
} 


HashTable* create_table(int size)
{ 
    HashTable *table = (HashTable*)malloc(sizeof(HashTable));
    table->dim = size; 
    table->items = (ht_item**)calloc(size, sizeof(ht_item*)); 
    for(int i = 0; i < size; i++){ 
        table->items[i] = NULL; 
    } 
    
    return table; 
} 


void print_table(HashTable* table) {
    // CHANGE HERE - function arguments validation
    if (table == NULL)
    {
        printf("Table is null\n");
        return;
    }
    // CHANGE HERE - change CAPACITY to dim
    for(int i = 0; i < table->dim; i++)
    {
        //printf("i = %d [%d]\n", i, table->items[i] == NULL);
        if(table->items[i] != NULL)
        {
            // CHANGE HERE - removed unnecessary malloc
            ht_item *_iterator = NULL;
            for(_iterator = table->items[i]; _iterator != NULL; _iterator = _iterator->next)
            { 
                printf("Key: %s\tValue: %s\n", _iterator->key, _iterator->value);
            }
        } 
    } 
}

Answer 2

create_item 函数可以而且应该被简化。我已经内嵌了一些评论。

HashTable* create_item(HashTable *table, char *value, char *key) { 
    // use modulo operator here, not in the hash function
    unsigned long index = hash(key) % table->dim;

    // nicer way of allocating
    ht_item *insert = malloc(sizeof *insert);

    // use strdup to avoid wasted memory and buffer overflows
    insert->key = strdup(key);
    insert->value = strdup(value);

    // head insert rather than tail
    insert->next = table->items[index];
    table->items[index] = insert;        

    return table; 
}

我放弃了 prev 成员的使用。如果你在某个地方需要它，你可以练习添加它。我认为简单的哈希 table.

没有必要

带链接列表的哈希表在 c 中不起作用？

Hashtable with linked list not work in c?

c

memory

hashtable

linked-list