Перефразирование и изменение размера хеш-таблицы с одной структурой - PullRequest
Новая
       62

Перефразирование и изменение размера хеш-таблицы с одной структурой

0 голосов
/ 10 ноября 2019



Я создал простую хеш-таблицу с функцией перефразирования / изменения размера, но, похоже, она не работает. Я не уверен, где проблема.

Я хотел бы перефразировать, когда в одном ключе хранится более 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");
}

1 Ответ

0 голосов
/ 10 ноября 2019

Вы используете массивы локальных переменных для своих хеш-таблиц (как исходных, так и перефразированных), но их необходимо распределить и передать указатели.

В настоящее время, когда вы перефразируете, вы создаетеновая таблица в локальном массиве new_hash_table. Вы заполняете это, а затем выбрасываете его (теряя всю память, выделенную для узлов) в конце функции.

Ваша хеш-функция принимает исходный массив фиксированного размера, и когда вы выполняете много дополнительной работыво время перефразирования это не нужно и просто замедляет работу.

...