@romajke

Как создать хэш таблицу с помощью си?

Пытаюсь разобраться со структурами данных, и сейчас впал в ступор перед хэш-таблицами.
Суть задачи такова: имеется большой словарь(~150к английских слов), нужно организовать в нем быстрый поиск заданного слова.

Первое, что приходит мне в голову - это (для начала, что бы понять принципы работы) сгруппировать слова по первой букве. Соответственно - это уже ускорит поиск в 26 раз (по сравнению с перебором всех слов)

Я всё это вижу как массив состоящий из 26 связных списков. То есть, мы определяем по первой букве каждого слова в какую ячейку его отнести, и добавляем в список находящийся в данной ячейке. Сответственно, когда мы вводим слово для поиска, мы так же определяем по его первой букве в какой ячейке массива его искать, и уже бежим по этому списку в поисках нужного слова.

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

Вопрос второй: я теоретически понимаю как должен работать алгоритм, но никак не могу его реализовать. Уже запутался во всей этой работе с памятью, указателями и т.д. По крупицам собираю информацию в гугле относительно динамических списков и массивов структур, но картина пока не складывается :(
Подскажите как это реализовать и\или где можно почитать о создании таких вот вещей?

П.с. Могу прекрепить код своих попыток реализовать сие )

update:
Моя попытка реализовать считывание словаря в хэш-таблицу:
//максимальная длина слова в словаре
#define SIZE 45 

int hash_function (char* key);

//определяем структуру
typedef struct node
    {
        char *word1;
        struct node *next;
    } node;


//создаем хэш-таблицу, в которой будут хранится списки
node hashtable[26];


int main()
{
    char *text = "small";
    FILE *fp = fopen(text, "r");
    if (fp == NULL)
    {
        printf("Could not open %s.\n", text);
        return 1;
    }

    char word[SIZE];
    
    //инициализируем всю хэш-таблицу нулями, для того,
    //что бы далее была возможность проверить, пустая ячейка или нет
    for (int i=0; i < 26; i++)
    {
        hashtable[i].word1 = NULL;
        hashtable[i].next = NULL;
    }


    while(!feof(fp))
    {
        //считываем слово из словаря
        fscanf(fp,"%s",word);
        
        //определяем его место в массиве
        int k=hash_function(word);
        
        //если ячейка пуста - вставляем туда наше слово
        if(hashtable[k].word1==NULL)
        {
            
            hashtable[k].word1=(char*)malloc(sizeof(char) * SIZE);
            strcpy(hashtable[k].word1, word);
            hashtable[k].next=NULL;

        }
        else
        {
            // создать новый элемент
            node * new = malloc (sizeof (node));


            // инициализировать новый элемент
            new-> word1 = NULL;
            new-> next = NULL;

            // вставить новый элемент в голову списка
            new-> next = hashtable[k];
            hashtable[k] = new;
            strcpy(hashtable[k]->word1, word);

        }

  	}


    fclose(fp);

    return 0;
}

int hash_function (char* key)
{
  int hash = tolower (key [0]) - 'a';
  return hash;
}
  • Вопрос задан
  • 3625 просмотров
Решения вопроса 1
jcmvbkbc
@jcmvbkbc
"I'm here to consult you" © Dogbert
Вопрос первый: я правильно понимаю, что эту структуру данных где будут хранится мои слова можно назвать хэш таблицей, а функцию, определяющую к какой ячейке массива отнести очередное слово - хэш-функцией?

Да.

По крупицам собираю информацию в гугле относительно динамических списков и массивов структур, но картина пока не складывается :(


38000000 результатов, нифига себе "по крупицам".

Подскажите как это реализовать и\или где можно почитать о создании таких вот вещей?

Тут уже читал?
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@res2001
Developer, ex-admin
Проще было бы ваш словарь отсортировать один раз и сохранить в таком виде, искать двоичным поиском, без всяких хэш таблиц и накладных расходов. Работать будет быстрее, чем хэш-таблица.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы