时间戳

首页 > 解决方案 > 双散列封闭散列表问题

c - 双散列封闭散列表问题

问题描述

我不明白出了什么问题。我使用橡皮鸭技术多次完成该程序。请问有什么问题吗？

#include<stdlib.h>
#include<stdio.h>
#include<string.h>

enum state {legitimate, empty, deleted};

typedef struct 
{

    enum state info;
    char *key;
    char *value;

}cell;

typedef struct 
{

    cell *cells;
    unsigned int size;

}hash_table;

 
unsigned int
hash1(const char *key, unsigned int size)
{
    unsigned int hash = 0;
    
    for(unsigned int i = 0; key[i]; i++)
    {
        hash = (hash << 5) + key[i];
    }

    return (hash%size);

}

unsigned int
hash2(const char *key)
{
    unsigned int hash = 0;
    unsigned int prime = 3;
    
    for(unsigned int i = 0; key[i]; i++)
    {
        hash = prime - (key[i] % prime);
    }

    return (hash);

}


hash_table*
initialize(unsigned int size)
{
    hash_table *H = malloc(sizeof(*H));
    H->cells = malloc(sizeof(*H->cells)*size);

    for(unsigned int i = 0; i<size; i++)
    {
        H->cells[i].info = empty;
    }

    return H;

}

unsigned int
find(hash_table *H, const char *key)
{
    unsigned int index = hash1(key, H->size);
    unsigned int hash = hash2(key);
    unsigned max = index;

    while(H->cells[index].key!=key && H->cells[index].info!=empty)
    {
        index = (index+hash)%H->size;

        if(index==max){printf("Not found!"); return -1;}
        if(index>=H->size){index-=H->size;}

    }

    return index;
    

}

void
insert(hash_table *H, const char *key, const char *value)
{
    unsigned int index = find(H, key);

    if(H->cells[index].info!=legitimate)
    {

        H->cells[index].key= malloc(strlen(key)+1);
        H->cells[index].value = malloc(strlen(value)+1);


        strcpy(H->cells[index].key,key);
        strcpy(H->cells[index].value,value);

        H->cells[index].info = legitimate;

    }
}

void
dump(hash_table *H)
{
    for(unsigned int i = 0; i<H->size; i++)
    {   
        if(H->cells[i].info!=legitimate){continue;}

        printf("Index[%d]: %s\n", i, H->cells[i].value);
    }
}


int main()
{
    hash_table *H = initialize(10);
    insert(H,"name1","David");
    insert(H, "name2", "Radka");
    dump(H);
    return 0;
}

输出：

NO OUTPUT

我检查了 hash1()、hash2() 和 find() 函数是否正常工作，它们确实有效，检查了多个输入，一切似乎都正常工作。我不确定缺少什么或我做错了什么。请帮忙。

标签： cdata-structureshashtabledouble-hashing

解决方案

由于您的程序会生成核心转储，因此您可以利用它

运行你的程序，你得到

浮点异常（核心转储）

当进程意外终止时，它会生成一个包含进程内存内容的文件（崩溃时程序的快照）。由于默认情况下禁用核心文件创建，我们使用ulimit命令启用写入核心文件：

打开控制台并将进程资源限制设置为unlimited

ulimit -c unlimited

再次运行您的程序以生成核心文件

使用生成的核心文件启动调试器

> gdb demo core

Program terminated with signal SIGFPE, Arithmetic exception.
#0  0x000055cd5fe03202 in hash1 (key=0x55cd5fe04024 "name1", size=0) at demo.c:35
35      return (hash%size);

它崩溃了hash1()，让我们看看为什么：

(gdb) print hash
$1 = 118636753
(gdb) print size
$2 = 0

你说对了！除以零return (hash%size);

的原型hash1是

unsigned int hash1(const char *key, unsigned int size);

检查谁在呼叫hash1()设置size为 0：

(gdb) frame 1
#1  0x0000555555555309 in find (H=0x5555555592a0, key=0x555555556024 "name1") at demo.c:73
73      unsigned int index = hash1(key, H->size);

H->size是罪魁祸首，它未初始化使用。

hash_table*
initialize(unsigned int size)
{
    hash_table *H = malloc(sizeof(*H));
    H->cells = malloc(sizeof(*H->cells)*size);

    for(unsigned int i = 0; i<size; i++)
    {
        H->cells[i].info = empty;
    }
    H->size = size; // Initialize it here
    return H;
}

推荐阅读