计算完成的哈希表 C 的完整性的函数

发布于 01-20 08:39 字数 1162 浏览 1 评论 0原文

计算完成的哈希表的完整性的函数。 有一个哈希表的实现及其主要功能。 您需要编写一个仅接受 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

挖个坑埋了你2025-01-27 08:39:35

您有一个具有溢出功能的哈希表的实现(如果具有特定哈希键的条目已经存在,则将新值推送到该索引处的列表中)。因此,哈希表永远不会真正满。添加到表中的内容越多,它就越会退化为链表。

为了使这一点显而易见,请假设您有 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).

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文