时间戳

首页 > 解决方案 > 使用一个结构重新散列和调整链式散列表的大小

c - 使用一个结构重新散列和调整链式散列表的大小

问题描述



我用 rehash/resize 函数创建了一个简单的链式哈希表，但它似乎不起作用。我不确定问题出在哪里。

当一个键存储超过 5 个元素时，我想重新散列。

我知道调试器是我的朋友，我尝试使用调试器找到问题，但没有成功。我知道这可能不是有史以来最好的哈希表，但这是我第一次这样做。

谢谢你的帮助

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

#define MAX 10
#define CAPACITY 5
#define FACTOR 0.7       // not using currently

typedef struct hast_table_item
{
    int data;
    int key;
    struct hast_table_item *next_data;
}HASH_TABLE_ITEM;

int hash_function(int value)
{
    return value % MAX;
}

void display_hash_table(HASH_TABLE_ITEM **hash_table);

void rehash(HASH_TABLE_ITEM **old_hash_table) {
    int current_capacity = MAX;
    int old_capacity = current_capacity;
    int new_capacity = old_capacity*2;
    HASH_TABLE_ITEM *new_hash_table[new_capacity];
    int i_my_hash;

    /* Clear the table */
    for (i_my_hash=0; i_my_hash<new_capacity; i_my_hash++) {                         
        new_hash_table[i_my_hash] = NULL;
    }

    /* Do Rehash */
    for (i_my_hash=0; i_my_hash<old_capacity; i_my_hash++) {
        if (old_hash_table[i_my_hash]->key != NULL) {                      // Guess there is problem in this if statement
          insert_hti(new_hash_table, old_hash_table[i_my_hash]->data);
        }
    }
    display_hash_table(new_hash_table);
}

void check_capacity(HASH_TABLE_ITEM **hash_table, HASH_TABLE_ITEM *new_item) 
{
    int count = 0;
    HASH_TABLE_ITEM *current = new_item;
    int i;

    for (i=0; i<MAX; i++) {
        if (hash_table[i] != NULL) {
            while (current != NULL) {
                count++;
                current = current->next_data;
                if (count == 5) {
                        printf("--- REHASHING ---\n");
                        rehash(hash_table);
                        // count = 0;
                        break;
                    }
            }
        } 
    }
    printf("Key %d has %d elements.\n",new_item->key, count);
}

void insert_hti(HASH_TABLE_ITEM **hash_table, int value)
{
    HASH_TABLE_ITEM *new_item = NULL;
    new_item = (HASH_TABLE_ITEM*)malloc(sizeof(HASH_TABLE_ITEM));

    new_item->data = value;
    new_item->key = hash_function(value);
    new_item->next_data = NULL;

    if (hash_table[new_item->key] == NULL) {
        hash_table[new_item->key] = new_item;
        check_capacity(hash_table,new_item);
    }
    else {
        new_item->next_data = hash_table[new_item->key];
        hash_table[new_item->key] = new_item;
        check_capacity(hash_table,new_item);
    }

}

void display_hash_table(HASH_TABLE_ITEM **hash_table) 
{
    HASH_TABLE_ITEM *current = NULL;
    int i;

    for (i=0; i<MAX; i++) {
        if (hash_table[i] != NULL) {
            current = hash_table[i];
            printf("Table Key (%d) -->   ", i);

            while (current != NULL) {
                printf("   | Data: %d |", current->data);
                current = current->next_data;
            }
            printf("\n");
        }
    }
}

void main() {
    /* Declare My Hash */
    int insert_value_my_hash = 0;
    int i_my_hash;
    HASH_TABLE_ITEM* hash_table[MAX];

    /* Clear the table */
    for (i_my_hash=0; i_my_hash<MAX; i_my_hash++) {                         
        hash_table[i_my_hash] = NULL;
    }

    /* Insert into My Hash */
    while (scanf("%d", &insert_value_my_hash) == 1) {       
        insert_hti(hash_table, insert_value_my_hash);
        printf("Vložila som element %d do mojej Hash tabuľky.\n", insert_value_my_hash);
    }
    display_hash_table(hash_table);    
    printf("\n\n");
}

标签： chashhashtable

解决方案

您正在为散列表使用局部变量数组（原始的和重新散列的），但是这些需要分配并传递指针。

new_hash_table目前，当您重新哈希时，您会在本地数组中构建新表。您填充它，然后在函数结束时将其丢弃（泄漏为节点分配的所有内存）。

您的散列函数假定原始数组大小固定，并且当您在重新散列期间执行大量额外工作时，这是不必要的，只会降低性能。

推荐阅读