在大量调试遇到此 malloc 错误后尝试使用哈希表实现字典
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/* to store a data (consisting of key and value) in hash table array */
struct item
{
char key[100];
char value[1000];
};
/* each hash table item has a flag (status) and data (consisting of key and value) */
struct hashtable_item
{
int flag;
/*
* flag = 0 : data does not exist
* flag = 1 : data exists at given array location
* flag = 2 : data was present at least once
*/
struct item *data;
};
struct hashtable_item *array;
int size = 10007;
int max = 10007;
/* 该函数返回给定键对应的索引 */
int hashcode(char* key,int TS)
{
return (key[0]+27*key[1]+729*key[2])%TS;
}
/* this function initializes the hash table array */
void init_array()
{
int i;
for (i = 0; i < max; i++)
{
array[i].flag = 0;
array[i].data = NULL;
}
}
/* 这个函数在哈希表中插入一个元素 */
void insert(char* key, char* value,int TS)
{
int index = hashcode(key,TS);
int i = index;
int h = 1;
struct item *new_item = (struct item*) malloc(sizeof(struct item));
strcpy(new_item->key , key);
strcpy(new_item->value , value);
/* probing through the array until an empty space is found */
while (array[i].flag == 1)
{
if (array[i].data->key == key)
{
/* case when already present key matches the given key */
printf("\n This key is already present in hash table, hence updating it's value \n");
strcpy(array[i].data->value , value);
return;
}
i = (i + (h * h)) % max;
h++;
if (i == index)
{
printf("\n Hash table is full, cannot add more elements \n");
return;
}
}
array[i].flag = 1;
array[i].data = new_item;
printf("\n Key (%s) has been inserted\n", key);
size++;
}
/* to remove an element form the hash table array */
void remove_element(char* key,int TS)
{
int index = hashcode(key,TS);
int i = index;
int h = 1;
/* probing through the hash table until we reach at location where there had not been an element even once */
while (array[i].flag != 0)
{
if (array[i].flag == 1 && array[i].data->key == key)
{
/* case where data exists at the location and its key matches to the given key */
array[i].flag = 2;
array[i].data = NULL;
size--;
printf("\n Key (%s) has been removed \n", key);
return;
}
i = (i + (h * h)) % max;
h++;
if (i == index)
{
break;
}
}
printf("\n Key does not exist \n");
}
/* to display the contents of hash table */
void display()
{
int i;
for(i = 0; i < max; i++)
{
if (array[i].flag != 1)
{
printf("\n Array[%d] has no elements \n", i);
}
else
{
printf("\n Array[%d] has elements \n %s (key) and %s (value) \n", i, array[i].data->key, array[i].data->value);
}
}
}
int size_of_hashtable()
{
return size;
}
主要功能
void main()
{
int choice,n, c;
char key[100];
char value[1000];
int TS=10007;
array = (struct hashtable_item*) malloc(max * sizeof(struct hashtable_item*));
init_array();
do {
printf("Implementation of Hash Table in C with Quadratic Probing.\n\n");
printf("MENU-: \n1.Inserting item in the Hash table"
"\n2.Removing item from the Hash table"
"\n3.Check the size of Hash table"
"\n4.Display Hash table"
"\n\n Please enter your choice-:");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Inserting element in Hash table \n");
printf("Enter key:");
fgets(key,100, stdin);
printf("Enter value:");
fgets(value,1000, stdin);
insert(key, value,TS);
break;
case 2:
printf("Deleting in Hash table \n Enter the key to delete-:");
fgets(key,100, stdin);
remove_element(key,TS);
break;
case 3:
n = size_of_hashtable();
printf("Size of Hash table is-:%d\n", n);
break;
case 4:
display();
break;
default:
printf("Wrong Input\n");
}
printf("\n Do you want to continue-:(press 1 for yes)\t");
scanf("%d", &c);
}while(c == 1);
}
在 C 中使用二次探测实现哈希表。 这是输出的样子
MENU-:
1.Inserting item in the Hash table
2.Removing item from the Hash table
3. Check the size of the Hash table
4.Display Hash table
Please enter your choice-:1
Inserting element in Hash table
Enter key:Enter value:john helllo we aer
a.out: malloc.c:2374: sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end `enter code here`& pagemask) == 0)' failed.
Aborted (core dumped)
最佳答案
通常 sysmalloc 错误会在您损坏某些内存时抛出，例如从未分配的空间写入或读取等。
我首先注意到的是数组的分配不太正确。我发现您需要一个 struct hashtable_item 数组，但您正在为一个指针数组分配空间。
sizeof(struct hashtable_item*) 在 x64 系统中将始终为 8，因为它是指针的大小。你可能应该使用 sizeof(struct hashtable_item) 它会给你实际结构对象的大小。
你需要的是这样的:
array = (struct hashtable_item*) malloc(max * sizeof(struct hashtable_item));
但另一方面，由于您的 array 是静态的，我建议您将它分配到 stack 而不是 heap 中:
struct hashtable_item[10007];
此外，如果您能提供有关您的 insert() 失败的信息，我们将不胜感激。
关于c - 我该如何修复散列时发生的这个 malloc 错误，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58445222/