c - 初始化哈希表的问题

Question

尝试使用链表实现哈希表来解决冲突问题我在初始化哈希表的代码中遇到了一些问题。我得到一个分段错误。试图找出问题出在哪里，我使用了 valgrind。使用此工具，我收到警告：

“地址 0x8 未堆叠、malloc 或（最近）释放”

几乎每次我尝试“编辑”哈希表。例如尺寸，插入某物，删除等。我一遍又一遍地查看我的代码，但我找不到问题所在。我以为我已经正确地 malloc'd 和 stack'd 一切。但是有了这个消息，显然某事出了问题。对此有什么想法吗？

我的代码：

     //hash table structure 
    typedef struct HashTable 
    {
     int size;   //size of table with connections
     struct List **table; //table elements
    }HashTable;

    typedef struct List
    {
     char* number;
     struct List *next;
    }List;

    struct HashTable *initHashTable(int size)
    {
       struct HashTable *blankTable=(struct HashTable *)malloc(sizeof(struct HashTable));

       if (size<1) 
       {
            return NULL;
       }

       if ((blankTable=malloc(sizeof(HashTable)))==NULL) 
       { 
           return NULL; 
       }
       if ( (blankTable->table=malloc(size*sizeof(List))) == NULL) 
       { 
           return NULL;
       }
       int i;
       for (i=0; i<size; i++) //initializes hash table
       {
         blankTable->table[i]=malloc(sizeof(List));
         blankTable->table[i]=NULL;     //Valgrind :: Invalid write of size 8
       }
       blankTable->size = size;
       //printf("blankTable size:%d\n",blankTable->size);
       return blankTable;
   }

更多注意事项：使用以下代码搜索哈希表中是否已存在数字。我从 valgrind 得到这个：

在 0x40110E 处读取大小为 8 ==3773== 的无效：lookup(360) ==3773== 地址 0x8 未堆栈、malloc 或（最近）释放

struct List *lookup(HashTable *hashtable,char *number)
{
 struct List *list= (struct List *) malloc (sizeof(struct List )); ;
 unsigned int hashval= hash(number);

 if ( (hashtable->table[hashval])!=NULL)  
 {
  for( list=hashtable->table[hashval]; list!=NULL; list=list->next)
  { if(strcmp(number,list->number)==0)  //SEGMENTATION!
   { 
    return list;
   } 
  }
 }
 return NULL;
}

事实上，如果我打电话查看桌子的大小，我也会得到一个分段，这让我更加担心。调用这个：

unsigned int size = Array[pos].TableHead->size;

Array[pos].TableHead 是指向 hashTable 结构的指针。

编辑：

运行 valgring 我得到这个报告：

           Invalid write of size 8
==8724==    at 0x4016D2: initHashTable (hash.c:524)
==8724==    by 0x4019CE: main (hash.c:792)
==8724==  Address 0x5199180 is 8 bytes after a block of size 8 alloc'd
==8724==    at 0x4C25153: malloc (vg_replace_malloc.c:195)
==8724==    by 0x4016B6: initHashTable (hash.c:522)
==8724==    by 0x4019CE: main (hash.c:792)

==8724== Use of uninitialised value of size 8
==8724==    at 0x4C264C4: strcmp (mc_replace_strmem.c:412)
==8724==    by 0x4017A0: lookup (hash.c:551)
==8724==    by 0x401820: add(hash.c:566)
==8724==    by 0x401AAB: main (hash.c:817)
==8724== 
==8724== Invalid read of size 1
==8724==    at 0x4C264C4: strcmp (mc_replace_strmem.c:412)
==8724==    by 0x4017A0: lookup (hash.c:551)
==8724==    by 0x401820: add (hash.c:566)
==8724==    by 0x401AAB: main (hash.c:817)
==8724==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==8724== 
==8724== 
==8724== Process terminating with default action of signal 11 (SIGSEGV)
==8724==  Access not within mapped region at address 0x0
==8724==    at 0x4C264C4: strcmp (mc_replace_strmem.c:412)
==8724==    by 0x4017A0: lookup (hash.c:551)
==8724==    by 0x401820: add (hash.c:566)
==8724==    by 0x401AAB: main (hash.c:817)
==8724==  If you believe this happened as a result of a stack
==8724==  overflow in your program's main thread (unlikely but
==8724==  possible), you can try to increase the size of the
==8724==  main thread stack using the --main-stacksize= flag.
==8724==  The main thread stack size used in this run was 8388608.

读到这篇文章，我首先想到我的号码没有空终止符。所以，我重新初始化它，并在它的最后一个索引上添加了null。不幸的是，您看到的问题仍然存在。在第一次运行（查找函数）时，它将数字与列表的数字进行比较，该数字为空。有细分。但我在徘徊为什么。它不能只返回 NULL 吗？

谢谢你。

score 5 · Accepted Answer

blankTable->table[i]=malloc(sizeof(List));
blankTable->table[i]=NULL;

您为列表项分配内存，然后将其设置为NULL(0x0)。

score 2 · Accepted Answer

以下玩具程序与您发布的结构定义和函数一起正常工作（好吧，至少没有段错误）：

#include <stdlib.h>
#include <assert.h>

/* code from question omitted */

int main(void) 
{
    HashTable * hash = initHashTable(5);
    int i;

    assert(hash->size == 5);

    for ( i = 0; i < hash->size; i++ )
        assert(hash->table[i] == NULL);

    free(hash);

    return EXIT_SUCCESS;
}

我假设以上是正确的，您认为 NULL 指针是一个“空”列表，对吧？（insert因此，该函数将用新列表的第一个元素替换适当的 NULL。）

如果是这样，您可以大大简化事情。可以编写一个初始化程序，使上述玩具程序通过 valgrind 干净地运行。我不想欺骗你的发现，但我可以暗示你可能想查看什么是灵活数组以及它们是如何工作的。

忽略初始化函数中的问题（一旦你的应用程序没有出现段错误，valgrind 应该准确地告诉你出了什么问题），hash()查找函数中函数的界限是什么？

您尝试读取的值hashtable->table[hash(number)]，因此hashtable必须使用至少那么多元素进行初始化，否则您将从尚未分配的内存中读取（因此出现分段错误）。

也许你的意思是

List * lookup(HashTable *hashtable, char *number)
{
    assert(hashtable != NULL);
    assert(number != NULL);

    unsigned int hashval = hash(number) % hashtable->size;
    List * list = hashtable->table[hashval];

    assert( list == NULL || list->number != NULL );

    while ( list != NULL && strcmp(number,list->number)!=0)
    {
        list = list->next;
        assert ( list == NULL || list->number != NULL );
    }

    return list;
}

更新：您不能strcmp从您发布的 valgrind 日志中将空指针传递给，这就是您遇到分段错误的原因。上面的查找函数已经更新了一些断言，以确保不会发生这种情况。

此外，valgrind 提示您已将未初始化的值传递给strcmp，这可能是空指针（如果未初始化的值恰好为零）。但是，仍然缺少一些重要信息来正确回答这个问题，您能否将整个文件发布到hash.c某个地方？

通读文件后：老实说，您在该代码中存在一些非常严重的问题 :-) 我认为您还没有掌握手动内存处理和初始化的概念-您是否有可能先学习 Java ?

无论如何，以下是我发现的问题，没有特别的顺序：

在init_array_for_antennas()中，您初始化局部变量 MyArray，而不是全局变量。只需删除局部变量，您应该就可以了。
静态和全局变量被隐式初始化为零，因此几乎所有内容init_array_for_antennas()都是多余的。
在几个地方，您“初始化”指针，malloc()然后将指针设置为其实际值。这是典型的内存泄漏；您将无法释放此类内存，因为您覆盖了对它的引用。
该声明number[strlen(number)]='\0';是，好吧，只是多余的。想想 strlen() 是如何工作的，你应该自己看看。
如果您还没有，请阅读什么是断言并了解如何使用它们来检查您的假设。注释掉assert(pointer_you_dereference_later != NULL);是错误的。
当您已经有一个指向字符串的指针时，您不必将内容复制到本地数组，然后将该数组传递给底层函数 - 只需传递指针！
您在某些地方使用全局常量bucket_size，在其他地方使用哈希表结构字段size。这是一个等待发生的错误，要么使 size 字段成为实际的编译时常量，要么正确使用运行时值。
确实是风格问题，但是您将很多结构类型定义为漂亮的、人类可读的名称，但结果还是添加了“结构”关键字。
如果你使用calloc()而不是malloc()你得到归零的内存。例如，分配一个指针数组calloc()会使它们初始化为 NULL，而您不需要显式地这样做。

好吧，可能还有更多，但今晚就是这样。我猜列表中的第一点是您实际问题的原因:-)

c - 初始化哈希表的问题

2 回答 2

Related

Reference