C - 访问哈希表中的结构成员时出现段错误(插入函数)

Question

我是 C 语言新手，在为我的哈希表实现插入函数时遇到问题。

这是我的结构:

typedef struct HashTableNode {
    char *url;                               // url previously seen
    struct HashTableNode *next;              // pointer to next node
} HashTableNode;

typedef struct HashTable {
    HashTableNode *table[MAX_HASH_SLOT];     // actual hashtable
} HashTable;

这是我初始化表的方法:

HashTable *initTable(){
  HashTable* d = (HashTable*)malloc(sizeof(HashTable));
  int i;
  for (i = 0; i < MAX_HASH_SLOT; i++) {
    d->table[i] = NULL;
  }
  return d;
}

这是我的插入函数:

int HashTableInsert(HashTable *table, char *url){

    long int hashindex = JenkinsHash(url, MAX_HASH_SLOT);
    int uniqueBool = 2; // 0 for true, 1 for false, 2 for init

    HashTableNode* theNode = (HashTableNode*)malloc(sizeof(HashTableNode));
    theNode->url = url;

    if (table->table[hashindex] != NULL) { // if we have a collision

        HashTableNode* currentNode = (HashTableNode*)malloc(sizeof(HashTableNode)); 
        currentNode = table->table[hashindex]->next; // the next node in the list


        if (currentNode == NULL) { // only one node currently in list


           if (strcmp(table->table[hashindex]->url, theNode->url) != 0) { // unique node

                table->table[hashindex]->next = theNode; 
                return 0; 
           }
           else{
            printf("Repeated Node\n");
            return 1;
           }


        }
        else { // multiple nodes in this slot

            printf("There was more than one element in this slot to start with. \n");
            while (currentNode != NULL)
            {


            // SEGFAULT when accessing currentNode->url HERE
               if (strcmp(currentNode->url, table->table[hashindex]->url) == 0 ){ // same URL 

                    uniqueBool = 1; 
               }
               else{
                    uniqueBool = 0; 
               }

                currentNode = currentNode->next;

            }   
        }

        if (uniqueBool == 0) {

            printf("Unique URL\n");

            theNode->next = table->table[hashindex]->next; // splice current node in

            table->table[hashindex]->next = theNode; // needs to be a node for each slot
            return 0; 
            }

    }
    else{

        printf("simple placement into an empty slot\n");
        table->table[hashindex] = theNode; 

    }   

    return 0; 

}

每次尝试访问 currentNode->url(给定槽的链表中的下一个节点)时，我都会收到 SegFault，如果节点本身不为 NULL，则其中应该有一个字符串。

我知道这段代码有点冒险，所以提前感谢任何愿意接受挑战的人。

芯片

更新:

这是调用所有 ht 函数的函数。通过对 hash table.c 的 main() 中的常规字符串进行测试，我得出结论，段错误是由于以下原因造成的:

void crawlPage(WebPage * page){

   char * new_url = NULL;  

   int pos= 0;

   pos = GetNextURL(page->html, pos, URL_PREFIX, &new_url);

   while (pos != -1){


        if (HashTableLookup(URLsVisited, new_url) == 1){ // url not in table

            printf("url is not in table......\n");

            hti(URLsVisited, new_url);

            WebPage * newPage = (WebPage*) calloc(1, sizeof(WebPage));
            newPage->url = new_url;


            printf("Adding to LIST...\n");
            add(&URLList, newPage); // added & to it.. no seg fault 


        }
        else{
            printf("skipping url cuz it is already in table\n");
        }


        new_url = NULL; 

        pos = GetNextURL(page->html, pos, URL_PREFIX, &new_url);

    }

    printf("freeing\n");
    free(new_url); // cleanup
    free(page); // free current page
}

Answer 1

您的哈希表插入逻辑违反了一些相当基本的规则。

• 在确定您实际需要一个新节点之前先分配一个新节点。
• currentNode 分配中存在明显的内存泄漏
• url 指针的所有权语义可疑。

除此之外，该算法变得过于复杂，超出了其真正应有的范围。

• 通过哈希值对表大小取模来计算哈希索引。
• 从哈希索引的表槽开始，遍历节点指针，直到发生以下两种情况之一:
  1. 您发现该节点已经存在
  2. 您已到达碰撞链的末端。

只有在上面的#2 中，您才真正分配冲突节点并将其链接到现有的冲突列表。当采用指针到指针方法时，大部分内容都是微不足道的，我将在下面进行演示:

int HashTableInsert(HashTable *table, const char *url)
{
    // find collision list starting point
    long int hashindex = JenkinsHash(url, MAX_HASH_SLOT);
    HashTableNode **pp = table->table+hashindex;

    // walk the collision list looking for a match
    while (*pp && strcmp(url, (*pp)->url))
        pp = &(*pp)->next;

    if (!*pp)
    {
        // no matching node found. insert a new one.
        HashTableNode *pNew = malloc(sizeof *pNew);
        pNew->url = strdup(url);
        pNew->next = NULL;
        *pp = pNew;
    }
    else
    {   // url already in the table
        printf("url \"%s\" already present\n", url);
        return 1;
    }
    return 0;
}

这确实是全部内容了。

我之前提到的 url 所有权问题已在上面通过使用 strdup() 进行字符串复制来解决。虽然不是标准库函数，但它符合 POSIX 标准，并且我在过去二十年中看到的每一个非尼安德特人的半成品实现都提供了它。如果您没有 (a) 我想知道您正在使用什么，以及 (b) 使用 strlen 和 malloc 实现它很简单。无论如何，当在值删除或表删除期间释放节点时，请确保在释放节点之前释放节点的url本身。

祝你好运。