Помочь с преобразованием хеш-функции на Си

Question

Задача поставлена такова: "Модифицируйте функцию lookup из кода, чтобы при превышении средней длиной списка некоторого порога х массив расширялся бы автоматически с коэффициентом пропорциональности в и так, чтобы хеш-таблиця подвергалась перестройке" Вот собственно код:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NHASH 11
typedef struct Nameval Nameval;
struct Nameval{
    char *name;
    int value;
    Nameval *next;
};
Nameval *symbtab[NHASH];

enum {MULTIPLIER = 31};
unsigned int hash(char *str){
    unsigned int h = 0;
    unsigned char *p;
    for(p = (unsigned char *)str; *p != '\0'; p++)
        h = MULTIPLIER*h + *p;
    return h % NHASH;
}
Nameval *lookup(char *name, int create, int value){
    Nameval *sym;
    int h = hash(name);
    for(sym = symbtab[h]; sym != NULL; sym = sym->next)
        if(strcmp(name, sym->name) == 0)
            return sym;
    if(create){
        sym = (Nameval *) malloc(sizeof(Nameval));
        sym->name = name;
        sym->value = value;
        sym->next = symbtab[h];
        symbtab[h] = sym; 
    }
    return sym;
}

int main(void) {
    Nameval *node = lookup("Billy", 1, 12);
    printf("%s %d\n", node->name, node->value);
    return 0;
}

Я не совсем понимаю, как можно менять размерность *symbtab[NHASH].

Answer 1

Массив symbtab можно сделать с помощью calloc и потом если надо , то освободить память и сделать ещё раз calloc. Но я не понимая, как хеш функция может меняться, ведь эта функция не имеет обратного хода. Но если нужно менять только функцию, тогда переменные MULTIPLIER и NHASH нужно сделать обычными переменными.

unsigned  int NHASH = 11U ;
Nameval * * symbtab = 0 ;
unsigned  int MULTIPLIER = 31U  ;
...
int main(void) {
  symbtab = calloc(NHASH,sizeof(Nameval *)) ;
  { Nameval *node = lookup("Billy", 1, 12);
    printf("%s %d\n", node->name, node->value);
    free(node); }
  free(symbtab);
  NHASH = 13 ;
  MULTIPLIER = 65 ;
  symbtab = calloc(NHASH,sizeof(Nameval *)) ;
  { Nameval *node = lookup("Billy", 1, 12);
    printf("%s %d\n", node->name, node->value);
    free(node); }
  free(symbtab);
    return 0;
}

БЛОГ НА HUSL

Помочь с преобразованием хеш-функции на Си

Ответы (1 шт):