计算完成的哈希表 C 的完整性的函数
计算完成的哈希表的完整性的函数。 有一个哈希表的实现及其主要功能。 您需要编写一个仅接受 struct listnode **hashtab 的函数 void hashtab_fullnes(struct listnode **hashtab)
并首先计算表中输入的元素数量。
struct listnode{
char key[32];
int value;
struct listnode *next;
};
#include "Hash.h"
#define HASHTAB_SIZE 200003
unsigned int hashtab_hash(char *key)
{
unsigned int h = 0, hash_mul = 31;
while (*key)
{
h = h * hash_mul + (unsigned int) *key++;
}
return h % HASHTAB_SIZE;
}
void hashtab_init(struct listnode **hashtab)
{
for (int i = 0; i < HASHTAB_SIZE; i++)
hashtab[i] = NULL;
}
void hashtab_add(struct listnode **hashtab, char *key, int value, int hashtype, int *collisions)
{
struct listnode *node;
int index;
if(hashtype == 1){
index = hashtab_hash(key);
} else {
index = hashtab_Hash(key);
}
node = malloc(sizeof(*node));
if (node != NULL)
{
if(hashtab[index] != NULL){
*collisions += 1;
}
strcpy(node->key, key);
node->next = hashtab[index];
hashtab[index] = node;
}
}
A function that counts the fullness of the finished hash table.
There is an implementation of a hash table and its main functions.
You need to write a function that accepts only struct listnode **hashtab
void hashtab_fullnes(struct listnode **hashtab)
and first counts the number of elements entered in the table.
struct listnode{
char key[32];
int value;
struct listnode *next;
};
#include "Hash.h"
#define HASHTAB_SIZE 200003
unsigned int hashtab_hash(char *key)
{
unsigned int h = 0, hash_mul = 31;
while (*key)
{
h = h * hash_mul + (unsigned int) *key++;
}
return h % HASHTAB_SIZE;
}
void hashtab_init(struct listnode **hashtab)
{
for (int i = 0; i < HASHTAB_SIZE; i++)
hashtab[i] = NULL;
}
void hashtab_add(struct listnode **hashtab, char *key, int value, int hashtype, int *collisions)
{
struct listnode *node;
int index;
if(hashtype == 1){
index = hashtab_hash(key);
} else {
index = hashtab_Hash(key);
}
node = malloc(sizeof(*node));
if (node != NULL)
{
if(hashtab[index] != NULL){
*collisions += 1;
}
strcpy(node->key, key);
node->next = hashtab[index];
hashtab[index] = node;
}
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

您有一个具有溢出功能的哈希表的实现(如果具有特定哈希键的条目已经存在,则将新值推送到该索引处的列表中)。因此,哈希表永远不会真正满。添加到表中的内容越多,它就越会退化为链表。
为了使这一点显而易见,请假设您有
HASHTAB_SIZE = 1
。然后,您要添加的每个值都具有(使用各自的哈希函数)相同的键。最后你会得到一个用于所有目的的链接列表。该列表的大小基本上仅受系统内存量的限制。因此,为了计算“填充度”,需要一个相当任意的定义(例如,已用单元格(具有非空列表的槽)/(HASHTAB_SIZE)的比率)。这样的定义还定义了可能会发生什么样的意外,例如,如果您只插入大量具有相同散列键的元素,则您的散列表看起来几乎是空的,同时它消耗了大量内存(并且具有很大的内存)。存储元素的数量)。
You have an implementation of a hash table with overflow capability (If an entry with a certain hash key already exists, you push the new value into the list at that index). As such, the hash-table can never be really full. The more you add to the table, the more it degrades into a linked list.
To make this obvious, consider you have
HASHTAB_SIZE = 1
. Then, every value you want to add has (with a respective hash function) the same key. And you end up with a linked list for all intents of purposes. The size of that list is basically only limited by the amount of memory of your system.So, in order to calculate the "fullness", a quite arbitrary definition is needed (like, e.g. the ratio of used cells (slots with non-empty list) / (HASHTAB_SIZE)). Such a definition also defines, what kind of surprises might happen, e.g. if you only insert a lot of elements which get the same hash-key, your hash table appears to be nearly empty while it consumes a lot of memory (and has a large count of stored elements).