Что такое хеш-таблица и как вы ее делаете в C?

Ответ 1

Предпосылки

Для этого ответа я собираюсь предположить, что вы знаете, как использовать указатели, структуры и иметь базовое понимание языка Си.

Также, если вы не знаете. Говоря о скорости алгоритмов и структур данных, вы должны знать термины:

O() = (произносится "Big-oh") Big-oh или O() относится к среде выполнения "наихудшего сценария". Точно так же, в математике, это большие обозначения O и описывает ограничивающее поведение функции. Если что-то O (1), то постоянное время "действительно хорошо". Если что-то O (n), это означает, что список длинен. В худшем случае это будет бегать миллион раз. O() обычно используется для определения того, насколько быстро что-то работает, потому что как быстро оно будет работать в худшем случае.

Ω = (греческая буква омега) относится к этому наилучшему сценарию. Он не использовал это так, как O(), поэтому я не буду вдаваться в подробности. Но просто знайте, что если что-то Ω (1), то в лучшем случае это займет всего один раз.

Θ = (греческая буква тета) уникальна тем, что используется только тогда, когда время выполнения O() и Ω() одинаково. Как и в случае алгоритма рекурсивной сортировки сортировка слиянием. Время выполнения составляет Θ (n (log (n))). Это означает, что это O (n (log (n))) и Ω (n (log (n))).

Что такое хэш-таблица?

Хеш-таблица или ассоциативный массив - это популярная структура данных, используемая в программировании. Хеш-таблица - это просто связанный список (я вернусь к тому, что представляет собой связанный список позже) с хэш-функцией. Хэш-функция в основном просто берет вещи и помещает их в разные "корзины". Каждая "корзина" - это просто другой связанный список или что-то еще, в зависимости от того, как вы его реализуете. Я объясню подробнее о хеш-таблицах, когда покажу, как их реализовать.

Почему я хочу использовать хеш-таблицу, а не массив?

Массив очень прост в использовании и прост в создании, но он также имеет свои недостатки. Для этого примера, скажем, у нас есть программа, в которой мы хотим сохранить всех ее пользователей в массиве.

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

char* users[100];

// iterate over every user and "store" their name
for (int i = 0; i < userCount; i++)
{
    users[i] = "New username here";
}

Так что все работает хорошо и очень быстро. Это O (1) прямо там. Мы можем получить доступ к любому пользователю в постоянное время.

Но давайте теперь предположим, что наша программа становится действительно популярной. Сейчас у него более 80 пользователей. Uh-Oh! Нам лучше увеличить размер этого массива, иначе мы получим переполнение буфера.

Так как мы это сделаем? Что ж, нам нужно будет сделать новый массив побольше и скопировать содержимое старого массива в новый массив.

Это очень дорого, и мы не хотим этого делать. Мы хотим мыслить умно и не использовать что-то, что имеет фиксированный размер. Ну, мы уже знаем, как использовать указатели в наших интересах, и мы можем объединить информацию в struct, если захотим.

Таким образом, мы могли бы создать struct для хранения имени пользователя и затем указать его (через указатель) на новый struct. Вуаля! Теперь у нас есть структура данных, которая расширяется. Это список связанной информации, которая связана указателями. Таким образом, название связанного списка.

Связанные списки

Итак, давайте создадим этот связанный список. Сначала нам понадобится struct

typedef struct node
{
    char* name;
    struct node* next;
}
node;

Хорошо, у нас есть строка name и... Подожди секунду... Я никогда не слышал о типе данных, который называется struct node. Для удобства мы typedef создали новый "тип данных" под названием node, который также называется нашим struct под названием node.

Итак, теперь, когда у нас есть наш узел для нашего списка, что нам нужно дальше? Что ж, нам нужно создать "корень" для нашего списка, чтобы мы могли traverse его (я объясню, что я имею в виду под traverse позже). Так что давайте назначим рут. (помните, что node тип данных я typdef редактировался ранее)

node* first = NULL;

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

/*
 * inserts a name called buffer into
 * our linked list
 */
void insert(char* buffer)
{     
    // try to instantiate node for number
    node* newptr = malloc(sizeof(node));
    if (newptr == NULL)
    {
        return;
    }

    // make a new ponter
    newptr->name = buffer;
    newptr->next = NULL;

    // check for empty list
    if (first == NULL)
    {
        first = newptr;
    }
    // check for insertion at tail
    else
    {
        // keep track of the previous spot in list
        node* predptr = first;

        // because we don't know how long this list is
        // we must induce a forever loop until we find the end
        while (true)
        {
            // check if it is the end of the list
            if (predptr->next == NULL)
            {
                // add new node to end of list
                predptr->next = newptr;

                // break out of forever loop
                break;
            }

            // update pointer
            predptr = predptr->next;
        }
    }         
}

Итак, поехали. У нас есть базовый связанный список, и теперь мы можем продолжать добавлять пользователей, сколько захотим, и нам не нужно беспокоиться о том, что не хватит места. Но это идет с недостатками. Большая проблема в том, что каждый узел или "пользователь" в нашем списке является "анонимным". Мы не знаем, были ли они или даже сколько у нас пользователей с этим. (конечно, есть способы сделать это намного лучше - я просто хочу показать очень простой связанный список) Мы должны просмотреть весь список, чтобы добавить пользователя, потому что мы не можем получить доступ к концу напрямую.

Как будто мы находимся в огромной пыльной буре, и вы ничего не видите, и нам нужно добраться до нашего сарая. Мы не можем видеть, где находится наш сарай, но у нас есть решение. Там стоят люди (наши node), и все они держат две веревки (наши указатели). У каждого человека есть только одна веревка, но кто-то другой удерживает ее на другом конце. Как и наш struct, веревка действует как указатель на то, где они находятся. Так как же нам добраться до нашего сарая? (для этого примера сарай является последним "человеком" в списке). Ну, мы понятия не имеем, насколько велика наша линия людей или куда они идут. На самом деле все, что мы видим, - это забор с привязанной к нему веревкой. (Наш корень!) Этот столб забора никогда не изменится, поэтому мы можем захватить столб и начать двигаться дальше, пока не увидим нашего первого человека. Этот человек держит две веревки (указатель записи и их указатель).

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

Так что это вкратце связанный список. Его преимущества в том, что он может расширяться настолько, насколько вы хотите, но его время выполнения зависит от того, насколько большой список, а именно O (n). Так что, если есть 1 миллион пользователей, он должен был бы запустить миллион раз, чтобы вставить новое имя! Ух ты, что кажется действительно расточительным, просто вставить 1 имя.

К счастью, мы умны и можем найти лучшее решение. Почему бы нам, вместо одного связанного списка, не иметь несколько связанных списков. Массив связанных списков, если хотите. Почему бы нам не создать массив размером 26. Таким образом, мы можем иметь уникальный связанный список для каждой буквы алфавита. Теперь вместо времени выполнения n. Мы можем разумно сказать, что наше новое время выполнения будет n/26. Теперь это не будет иметь большого значения, если у вас большой список на 1 миллион. Но мы просто будем упрощать этот пример.

Итак, у нас есть массив связанных списков, но как мы собираемся сортировать наших пользователей в массив. Ну... почему бы нам не сделать функцию, которая решает, куда и куда идти. Эта функция будет "хэшировать" пользователей, если вы попадете в массив или "таблицу". Итак, давайте создадим этот "хешированный" связанный список. Таким образом, имя хэш-таблицы

Хеш-таблица

Как я только что сказал, наша хеш-таблица будет массивом связанных списков и будет хешироваться первой буквой имени пользователя. A перейдет в положение 0, B в 1 и т.д.

struct для этой хеш-таблицы будет такой же, как структура для нашего предыдущего связного списка

typedef struct node
{
    char* name;
    struct node* next;
}
node;

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

node* first[26] = {NULL};

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

Пусть сделают главную функцию. Требуется имя пользователя, которое мы собираемся хэшировать, а затем вставить.

int main(char* name)
{
    // hash the name into a spot
    int hashedValue = hash(name);

    // insert the name in table with hashed value
    insert(hashedValue, name);
}

Так что здесь наша хэш-функция. Это довольно просто. Все, что мы хотим сделать, это посмотреть на первую букву в слове и дать значение от 0 до 25, в зависимости от того, какая это буква

/*
 * takes a string and hashes it into the correct bucket
 */
int hash(const char* buffer)
{
    // assign a number to the first char of buffer from 0-25
    return tolower(buffer[0]) - 'a';
}

Так что теперь все, что нам нужно, это создать нашу функцию вставки. Он будет выглядеть так же, как наша функция вставки раньше, за исключением того, что каждый раз, когда мы ссылаемся на наш корень, мы будем ссылаться на него как на массив.

/*
 * takes a string and inserts it into a linked list at a part of the hash table
 */
void insert(int key, const char* buffer)
{
    // try to instantiate node to insert word
    node* newptr = malloc(sizeof(node));
    if (newptr == NULL)
    {
        return;
    }

    // make a new pointer
    strcpy(newptr->word, buffer);
    newptr->next = NULL;

    // check for empty list
    if (first[key] == NULL)
    {
       first[key] = newptr;
    }
    // check for insertion at tail
    else
    {
        node* predptr = first[key];
        while (true)
        {
            // insert at tail
            if (predptr->next == NULL)
            {
                predptr->next = newptr;
                break;
            }

            // update pointer
            predptr = predptr->next;
        }
    }
}

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