c - 通用 HashMap，不需要的输出 (C)

Question

我正在编写一个通用的 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;
  }

Answer 1

在 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 $