我正在编写一个通用的 Hashtable 库，但在使用 lookup() 等函数时我总是遇到问题。 预期的输出应该是:
result = thirteen
result = thirteen
result = thirteen
但我得到:
result = thirteen
然后它崩溃了。当我多次调用 lookup() 函数时，似乎会出现此问题，事实上，如果我调用 lookup() 一次，代码运行没有任何问题。
每次我调用 lookup() 函数时，它都会创建一个新的 HashMap，但我看不出拥有更多 HashMap 与问题之间有任何关联。 我尝试在每个 lookup() 函数之间使用 free() 方法来解决问题，但问题一直出现。
这是原始代码的一部分:
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
typedef struct _Association Association;
typedef struct _HashMap HashMap;
typedef int (*HashMapCmp)(void*, void*);
/*
Hash Map
*/
struct _HashMap{
Association** array;
int number_of_rows;
int number_of_elements;
HashMapCmp cmp_key;
};
/*
element of the linked Hash Map
*/
struct _Association{
void* key;
void* value;
struct _Association* next;
};
/*
hash function
*/
unsigned int hash(HashMap* map, void* key){
unsigned int hash_value = 0;
hash_value = (*(int*)key * 1500) % map->number_of_rows;
return hash_value;
}
/*
inits a new Hash Map
*/
HashMap* HashMap_new(int table_size, HashMapCmp cmp_key){
HashMap* result = (HashMap*) malloc(sizeof(HashMap));
result->number_of_rows = table_size;
result->array = (Association**) malloc(sizeof(Association*) * result->number_of_rows);
result->number_of_elements = 0;
result->cmp_key = cmp_key;
for(int i = 0; i < result->number_of_rows; i++){
result->array[i] = malloc(sizeof(Association*));
result->array[i] = NULL;
}
return result;
}
/*
inserts a new association in my Hash Map
*/
bool HashMap_insert(HashMap* map, void* key, void* value){
if(map == NULL)
return false;
else{
int index = hash(map, key);
Association* as = malloc(sizeof(Association*));
as->key = key;
as->value = value;
as->next = map->array[index];
map->array[index] = as;
map->number_of_elements++;
return true;
}
}
/*
returns the value of the key passed by parameter
*/
void* HashMap_lookup(HashMap* map, void* key){
int index = hash(map, key);
Association* tmp = map->array[index];
while(tmp != NULL && map->cmp_key(tmp->key,key) != 0){
tmp = tmp->next;
}
return tmp->value;
}
/*
**************************************
tests methods
*/
/*
int pointer (key)
*/
int* int_new(int n) {
int* result = (int*) malloc(sizeof(int));
*result = n;
return result;
}
/*
char* pointer (value)
*/
char** string_new(char* s) {
char** result = (char**) malloc(sizeof(char*)*20);
*result = s;
return result;
}
/*
Integers comparator -> obj1>obj2 = 1, obj1<obj2 = -1, obj1=obj2 = 0
*/
static int compare_ints(int* obj1, int* obj2) {
return *obj1 - *obj2;
}
/*
creation of a 5 elements, high 4, HashMap
*/
HashMap* create_five_elements_hash_map(){
HashMap* map = HashMap_new(4, (HashMapCmp) compare_ints);
HashMap_insert(map, int_new(0), string_new("zero"));
HashMap_insert(map, int_new(13), string_new("thirteen"));
HashMap_insert(map, int_new(22), string_new("twentytwo"));
HashMap_insert(map, int_new(34), string_new("thirtyfour"));
HashMap_insert(map, int_new(41), string_new("fortyone"));
return map;
}
/*
looking inside the Hashmap for the element
*/
void test_lookup(){
HashMap* map = create_five_elements_hash_map();
char** str = (char**)HashMap_lookup(map,int_new(13));
printf("result = %s\n", *str);
}
int main(){
test_lookup();
test_lookup();
test_lookup();
return 0;
}
最佳答案
在 HashMap_insert 中那一行是错误的:
Association* as = malloc(sizeof(Association*));
必须是
Association* as = malloc(sizeof(Association));
或
Association* as = malloc(sizeof(*as));
否则你只为 1 个指针分配内存，而 Association 需要足够的空间来容纳 3 个指针，并且在你设置 as 字段之后你写出分配的 block 未定义的行为。
如果您可以安装 valgrind，我强烈建议您使用它，例如，如果我在我的 PI4 下按照您的定义进行操作，这里有很多消息:
pi@raspberrypi:/tmp $ gcc -g -Wall c.c
pi@raspberrypi:/tmp $ valgrind ./a.out
==6708== Memcheck, a memory error detector
==6708== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==6708== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==6708== Command: ./a.out
==6708==
==6708== Invalid write of size 4
==6708== at 0x10628: HashMap_insert (c.c:64)
==6708== by 0x1081B: create_five_elements_hash_map (c.c:124)
==6708== by 0x108F3: test_lookup (c.c:136)
==6708== by 0x10943: main (c.c:143)
==6708== Address 0x49e2244 is 0 bytes after a block of size 4 alloc'd
==6708== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6708== by 0x1060B: HashMap_insert (c.c:61)
==6708== by 0x1081B: create_five_elements_hash_map (c.c:124)
==6708== by 0x108F3: test_lookup (c.c:136)
==6708== by 0x10943: main (c.c:143)
==6708==
==6708== Invalid write of size 4
==6708== at 0x10648: HashMap_insert (c.c:65)
==6708== by 0x1081B: create_five_elements_hash_map (c.c:124)
==6708== by 0x108F3: test_lookup (c.c:136)
==6708== by 0x10943: main (c.c:143)
==6708== Address 0x49e2248 is 4 bytes after a block of size 4 alloc'd
==6708== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6708== by 0x1060B: HashMap_insert (c.c:61)
==6708== by 0x1081B: create_five_elements_hash_map (c.c:124)
==6708== by 0x108F3: test_lookup (c.c:136)
==6708== by 0x10943: main (c.c:143)
==6708==
==6708== Invalid write of size 4
==6708== at 0x10628: HashMap_insert (c.c:64)
==6708== by 0x10843: create_five_elements_hash_map (c.c:125)
==6708== by 0x108F3: test_lookup (c.c:136)
==6708== by 0x10943: main (c.c:143)
==6708== Address 0x49e2334 is 0 bytes after a block of size 4 alloc'd
==6708== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6708== by 0x1060B: HashMap_insert (c.c:61)
==6708== by 0x10843: create_five_elements_hash_map (c.c:125)
==6708== by 0x108F3: test_lookup (c.c:136)
==6708== by 0x10943: main (c.c:143)
...
但更正后:
pi@raspberrypi:/tmp $ valgrind ./a.out
==6844== Memcheck, a memory error detector
==6844== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==6844== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==6844== Command: ./a.out
==6844==
result = thirteen
result = thirteen
result = thirteen
==6844==
==6844== HEAP SUMMARY:
==6844== in use at exit: 1,596 bytes in 66 blocks
==6844== total heap usage: 67 allocs, 1 frees, 2,620 bytes allocated
==6844==
==6844== LEAK SUMMARY:
==6844== definitely lost: 108 bytes in 18 blocks
==6844== indirectly lost: 1,488 bytes in 48 blocks
==6844== possibly lost: 0 bytes in 0 blocks
==6844== still reachable: 0 bytes in 0 blocks
==6844== suppressed: 0 bytes in 0 blocks
==6844== Rerun with --leak-check=full to see details of leaked memory
==6844==
==6844== For lists of detected and suppressed errors, rerun with: -s
==6844== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
pi@raspberrypi:/tmp $
所以你不再有未定义的行为了，但这并不意味着现在程序会做你想做的事，但正如你所看到的，你有内存泄漏，我鼓励你解决它们，并了解更多关于它们的信息:
pi@raspberrypi:/tmp $ valgrind --leak-check=full --show-leak-kinds=definite ./a.out
==6967== Memcheck, a memory error detector
==6967== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==6967== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==6967== Command: ./a.out
==6967==
result = thirteen
result = thirteen
result = thirteen
==6967==
==6967== HEAP SUMMARY:
==6967== in use at exit: 1,596 bytes in 66 blocks
==6967== total heap usage: 67 allocs, 1 frees, 2,620 bytes allocated
==6967==
==6967== 4 bytes in 1 blocks are definitely lost in loss record 16 of 57
==6967== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967== by 0x1073F: int_new (c.c:96)
==6967== by 0x108FF: test_lookup (c.c:137)
==6967== by 0x10943: main (c.c:143)
==6967==
==6967== 4 bytes in 1 blocks are definitely lost in loss record 17 of 57
==6967== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967== by 0x1073F: int_new (c.c:96)
==6967== by 0x108FF: test_lookup (c.c:137)
==6967== by 0x10947: main (c.c:144)
==6967==
==6967== 4 bytes in 1 blocks are definitely lost in loss record 18 of 57
==6967== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967== by 0x1073F: int_new (c.c:96)
==6967== by 0x108FF: test_lookup (c.c:137)
==6967== by 0x1094B: main (c.c:145)
==6967==
==6967== 16 bytes in 4 blocks are definitely lost in loss record 37 of 57
==6967== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967== by 0x1056F: HashMap_new (c.c:47)
==6967== by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967== by 0x108F3: test_lookup (c.c:136)
==6967== by 0x10943: main (c.c:143)
==6967==
==6967== 16 bytes in 4 blocks are definitely lost in loss record 38 of 57
==6967== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967== by 0x1056F: HashMap_new (c.c:47)
==6967== by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967== by 0x108F3: test_lookup (c.c:136)
==6967== by 0x10947: main (c.c:144)
==6967==
==6967== 16 bytes in 4 blocks are definitely lost in loss record 39 of 57
==6967== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967== by 0x1056F: HashMap_new (c.c:47)
==6967== by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967== by 0x108F3: test_lookup (c.c:136)
==6967== by 0x1094B: main (c.c:145)
==6967==
==6967== 512 (16 direct, 496 indirect) bytes in 1 blocks are definitely lost in loss record 55 of 57
==6967== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967== by 0x104F7: HashMap_new (c.c:40)
==6967== by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967== by 0x108F3: test_lookup (c.c:136)
==6967== by 0x10943: main (c.c:143)
==6967==
==6967== 512 (16 direct, 496 indirect) bytes in 1 blocks are definitely lost in loss record 56 of 57
==6967== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967== by 0x104F7: HashMap_new (c.c:40)
==6967== by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967== by 0x108F3: test_lookup (c.c:136)
==6967== by 0x10947: main (c.c:144)
==6967==
==6967== 512 (16 direct, 496 indirect) bytes in 1 blocks are definitely lost in loss record 57 of 57
==6967== at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967== by 0x104F7: HashMap_new (c.c:40)
==6967== by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967== by 0x108F3: test_lookup (c.c:136)
==6967== by 0x1094B: main (c.c:145)
==6967==
==6967== LEAK SUMMARY:
==6967== definitely lost: 108 bytes in 18 blocks
==6967== indirectly lost: 1,488 bytes in 48 blocks
==6967== possibly lost: 0 bytes in 0 blocks
==6967== still reachable: 0 bytes in 0 blocks
==6967== suppressed: 0 bytes in 0 blocks
==6967==
==6967== For lists of detected and suppressed errors, rerun with: -s
==6967== ERROR SUMMARY: 9 errors from 9 contexts (suppressed: 0 from 0)
pi@raspberrypi:/tmp $
关于c - 通用 HashMap，不需要的输出 (C)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/62169333/