Хеширование структур на С

Question

Итак, я пытаюсь реализовать хеш-таблицу, которая будет содержать хеш-структуры, содержащие слова.

структуры будут похожи на это:

#ifndef HASHTABLE_H
#def HASHTABLE_H

typedef int (*HashFunctionT) (char* string, int upperbound);

struct node_
{
    char * word;
    struct node * next;
}
typedef struct node_ * node;

struct nodehash_
{
    int size;
    struct node * hash[100];
}
typedef struct nodehash_ * nodehash;

Hashtable createHashTable();
void addtohash(node list, nodehash hash);
#endif

И я хочу, чтобы хеш-функцияработает примерно так:

#include "hashtable.h"

int hashFunction(char *word, int hashTableSize)
{
    int length = strlen(word);
    int h = 0;
    int i;  
    for(i = 0; i<length; i++)
    {
        h=31 *h  + word[i];
    }
    return h % hashTableSize;
};

nodehash createHashtable()
{
    nodehash hashtable;    
    hashtable = malloc(sizeof(struct nodehash_));

    hashtable->size = 100;
    hashtable->hash = malloc(100 * sizeof (node));
    int i;   
    for (i = 0; i < hashtable->size; i++)
    {
            hashtable->table[i] = NULL;
    }
    return hashtable;
};

void addtohash(node list, nodehash hashtable)
{
    int nodehashnumber;
    nodehashnumber = hashfunction(list->word, hash->size);
    hashtable->hash[nodehasnumber] = list;
};

И основная функция будет выглядеть примерно так (предположим, что связанный список структур узлов был создан и заполнен).

int main()
{
    nodehash hashtable = createhashtable();
    node nodelist;
    /* here the nodelist would be created and filled and such and such*/
    while (nodelist->next != NULL)
    {
        addtohash(nodelist, hashtable);
    }
    return;
}

Предположим, чтоне может быть никаких коллизий, потому что каждое хешируемое слово будет отличаться.

В общем, мне интересно, пропустил ли я и бросил ли я в глаза явные ошибки или недостатки в логике.

Любая помощь будет принята с благодарностью.

Спасибо.

Answer 1

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

Answer 2

У вас, похоже, проблема с точкой с запятой:

struct node_
{
    char * word;
    struct node * next;
}   /* <<-- HERE */
typedef struct node_ * node;

Но ::

int hashFunction(char *word, int hashTableSize)
{
    int length = strlen(word);
    int h = 0;
    int i;  
    for(i = 0; i<length; i++)
    {
        h=31 *h  + word[i];
    }
    return h % hashTableSize;
}; /* <<-- NOT here */

Кроме того, ИМХО является мудрым советом использовать как можно больше беззнаковых типов: для значения хеша (что делает деление по модулю с отрицательным операндом?) И для размеров и индексов.

Правило большого пальца: , если оно не может быть отрицательным: оно без знака .