c-双重哈希关闭哈希哈希表问题

Question

我不明白怎么了。我使用橡皮鸭技术多次浏览该程序。请问有什么问题？

#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]: %sn", 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((函数是否有效，它们确实有效，并通过多个输入检查了一切似乎都正常工作。我不确定我遗漏了什么或做错了什么。请帮忙。

Answer 1

由于您的程序生成了一个核心转储，因此您可以利用

运行你的程序，你会得到

浮点异常(核心转储(

当进程意外终止时，它会生成一个包含进程内存内容的文件(崩溃时程序的快照(。由于默认情况下禁用了核心文件创建，因此我们使用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);

在size设置为0:的情况下，检查谁在呼叫hash1()

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