Пытаюсь разобраться со структурами данных, и сейчас впал в ступор перед хэш-таблицами.
Суть задачи такова: имеется большой словарь(~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;
}
Простой
