初始化哈希表的问题

Question

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

“地址 0x8 未堆栈、未分配 或（最近）被释放”

几乎每次我尝试“编辑”哈希表。 例如，大小、插入、删除等。 我一遍又一遍地查看我的代码，但我找不到问题所在。我以为我已经正确地分配和堆叠了所有内容。但有了这个消息，显然出了问题。 对此有什么想法吗？

我的代码：

     //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 得到这个：

大小 8 的读取无效 ==3773==在0x40110E：查找（360） ==3773== 地址 0x8 未被堆栈、分配或（最近）释放

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吗？

谢谢。

Answer 1

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

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

Answer 2

以下玩具程序可以使用您发布的结构定义和函数正常工作（至少不会出现段错误）：

#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;
}

更新：您无法从您发布的 valgrind 日志中将空指针传递给 strcmp，这就是您出现分段错误的原因。上面的查找函数已更新为更多断言，以确保不会发生这种情况。

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

通读该文件后：我必须说实话，您在该代码中遇到了一些非常严重的问题:-)我认为您尚未掌握手动内存处理和初始化的概念 - 您是否可能先学习了 Java ？

无论如何，以下是我发现的问题（排名不分先后）：

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

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