Hash Table

سلام عليكم.

لدي أستفسار بخصوص ال Hash Table: إذا كان لدينا قاموس ضخم (فلنأخذ قاموس اللغة الأنجليزية كمثال) فإن أنسب هيكل بيانات لتخزين القاموس هو ال Hash Table لما يوفر من سرعة ثابتة علي حساب الذاكرة. كالمثال التالي:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cs50.h>
#include <ctype.h>

// Global variables
#define ALPHABETS 26
#define MAX 35

// Struct node
typedef struct node
{
    string word;
    struct node* next;
} node;

// Functions prototypes
void EXIT(string msg);
node* find_tail(node* head);
void insert_node(node** head, string word);
void print_linked_list(node* head);
void free_linked_list(node* head);

int main(int argc, string argv[])
{
    if (argc != 2)
    {
        EXIT("Usage: ./dictionary [N of words]\n");
    }

    short n_of_words = atoi(argv[1]);
    if (!strcmp(argv[1], "0"))
    {
        EXIT("No words added\n");
    }
    else if (!n_of_words)
    {
        EXIT("Invalid input\n");
    }
    else if (n_of_words > MAX)
    {
        printf("%i ", MAX);
        EXIT("is the max number\n");
    }
    // Hash table starts here
    node* dictionary[ALPHABETS] = {NULL};

    // Take vocabularies & insert them
    for (int i = 0; i < n_of_words; i++)
    {
        string vocabulary = get_string("Word: ");
        short hash = toupper(vocabulary[0]) - 'A';

        insert_node(&dictionary[hash], vocabulary);
    }

    // Print & Free dictionary
    for (int i = 0; i < ALPHABETS; i++)
    {
        printf("%c: ", i + 'A');
        if (dictionary[i])
        {
            // print current bucket
            print_linked_list(dictionary[i]);
            printf("\n");
            // free current bucket
            free_linked_list(dictionary[i]);
        }
        else
        {
            printf("\n");
        }
    }

}

// func1: Exit program function
void EXIT(string msg)
{
    printf("%s", msg);
    exit(0);
}

// func2: To find the tail of a linked list
node* find_tail(node* head)
{
    if (!head)
    {
        return NULL;
    }

    node* temp = head;
    while (temp->next)
    {
        temp = temp->next;
    }
    return temp;
}

// func3: To insert a node to a linked list
void insert_node(node** head, string vocabulary)
{
    node* n = malloc(sizeof(node));
    if (!n)
    {
        return;
    }
    n->word = vocabulary;
    n->next = NULL;

    if (!*head)
    {
        *head = n;
        return;
    }

    find_tail(*head)->next = n;
}

// func4: To print linked list items
void print_linked_list(node* head)
{
    for (node* temp = head; temp; temp = temp->next)
    {
        printf("%s ", temp->word);
    }
}

// func4: To free linked list
void free_linked_list(node* head)
{
    while (head)
    {
        node* temp = head->next;
        free(head);
        head = temp;
    }
}

أعرف أنها طريقة سيئة لتخزين الكلمات؛ إذ أردنا البحث عن كلمة ما في القاموس, فنعم سنختصر الكثير من الوقت لأننا نعلم في أي Bucket سنبحث, لكن ما زال البحث بطئ (أو حتي بنفس البطئ) لأن البرنامج سيضطر للمرور علي عناصر ال Linked List واحدة تلو الأخري. لذلك قاموا بتوسيع الجدول كي تتقسم العناصر أكثر و أكثر (كل هذا علي حساب الذاكرة).

هل يمكن لأحدكم أن يشرح لي هذا التقسيم (في مثال القاموس تحديدا). كما أن هناك عملية تتم علي الكلمات كي نجد ال Bucket بنفس الوقت, ما هي هذه العملية.