什么是散列 table 以及如何在 C 中制作它？

Question

我有几个关于称为散列的数据结构 table（也称为关联数组）及其在 C 中如何实现的问题。

如何在 C 中创建散列 table？什么是 hashtable 以及如何实现它？为什么我要使用散列 table 而不是数组？

注意：我知道这是一个非常宽泛的问题，需要大量的答案，但我之所以这样做是因为有些人问我这是什么。所以我把它放在这里是为了充分解释它并帮助其他人。

Answer 1

先决条件

对于这个答案，我假设您知道如何使用指针和结构，并且对 C 语言有基本的了解。

还有如果你不知道。在谈论算法和数据结构的速度时，您应该知道这些术语：

O() =（读作"Big-oh"）大哦或O()指的是"worst-case-scenario" 运行时间。同样，在数学中，它是大 O 符号，描述了函数的限制行为。如果 O(1) 是常数时间 "really good"。如果某事 O(n) 这意味着如果列表是一百万长。最坏的情况是运行一百万次。 O() 通常是用来确定某事运行有多快的那个，因为那是它在最坏情况下运行的速度。

Ω =（希腊字母 Omega）指的是最好的情况。它不像 O() 那样经常使用，所以我不会详细介绍它。但是只要知道如果某些东西是 Ω(1)，在最好的情况下它只需要一次。

Θ=（希腊字母theta）的独特之处在于它只在O()和Ω()运行时间相同时使用。就像递归排序算法 merge sort 的情况一样。它的运行时间是 Θ(n(log(n)))。这意味着它是 O(n(log(n))) 并且它是 Ω(n(log(n))).

什么是哈希 table？

哈希 table 或关联数组是编程中常用的数据结构。散列 table 只是一个带有散列函数的链表（稍后我将介绍什么是链表）。哈希函数基本上只是把东西放在不同的 "baskets" 中。每个 "basket" 只是另一个链表或其他东西，具体取决于您如何实现它。当我向您展示如何实现时，我将解释有关哈希 table 的更多详细信息。

为什么我要使用散列 table 而不是数组？

阵列非常易于使用且制作简单，但也有其缺点。对于这个例子，假设我们有一个程序，我们希望将它的所有用户保存在一个数组中。

这很简单。假设我们计划此计划的用户不超过 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 多个用户。呃哦！我们最好增加该数组的大小，否则会发生缓冲区溢出。

那么我们该怎么做呢？那么我们将不得不创建一个更大的新数组，并将旧数组的内容复制到新数组中。

这非常昂贵，我们不想这样做。我们想聪明地思考，而不是使用具有固定大小的东西。好吧，我们已经知道如何使用指针来发挥我们的优势，如果我们愿意，我们可以将信息捆绑到 struct 中。

所以我们可以创建一个 struct 来存储用户名，然后让它（通过指针）指向一个新的 struct。瞧！我们现在有一个可扩展的数据结构。它是通过指针链接在一起的捆绑信息列表。因而得名链表。

链表

所以让我们创建那个链表。首先我们需要 struct

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

好吧，我们有一个字符串 name 和一个...等一下...我从来没有听说过一种叫做 struct node 的数据类型。好吧，为了我们的方便，我 typedef 一个新的 "data type" 叫做 node，它也恰好是我们的 struct 叫做 node。

现在我们有了列表的节点，接下来我们需要做什么？好吧，我们需要为我们的列表创建一个 "root"，这样我们就可以 traverse 它（我稍后会解释 traverse 的意思）。所以让我们分配一个根。（记住我之前 typdef 编辑的 node 数据类型）

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;
        }
    }         
}

好了。我们有一个基本的链表，现在我们可以继续添加我们想要的所有用户，我们不必担心运行空间不足。但这确实有不利的一面。最大的问题是我们列表中的每个节点或 "user" 都是 "anonymous"。我们不知道他们是否在，甚至不知道我们有多少用户。（当然有办法让它变得更好——我只是想展示一个非常基本的链表）我们必须遍历整个链表来添加一个用户，因为我们不能直接访问末尾。

这就像我们在一场巨大的沙尘暴中，你什么也看不见，我们需要回到我们的谷仓。我们看不到我们的谷仓在哪里，但我们有一个解决方案。有人站在那里（我们的 nodes），他们都拿着两条绳子（我们的指针）。每个人只拥有一根绳子，但那根绳子的另一端由其他人握住。就像我们的 struct 一样，绳索充当指向它们所在位置的指针。那我们怎么去我们的谷仓呢？（对于此示例，谷仓是列表中的最后一个 "person"）。好吧，我们不知道我们的人员队伍有多大，也不知道他们去了哪里。事实上，我们看到的只是一个围栏post，上面绑着一根绳子。（我们的根！）围栏 post 永远不会改变，所以我们可以抓住 post 并开始前进，直到我们看到我们的第一个人。那个人拿着两条绳子（post的指针和他们的指针）。

所以我们一直沿着绳子前进，直到遇到一个新人并抓住他们的绳子。最终，我们走到了尽头，找到了我们的谷仓！

简而言之就是一个链表。它的好处是它可以随心所欲地扩展，但它的运行时间取决于列表的大小，即 O(n)。所以如果有100万用户，那就得运行100万次来插入一个新名字！哇，只插入 1 个名字似乎真的很浪费。

幸运的是，我们很聪明，可以创建更好的解决方案。我们为什么不使用几个链表，而不是只有一个链表。如果愿意，可以使用一组链表。为什么我们不创建一个大小为 26 的数组。这样我们就可以为字母表中的每个字母创建一个唯一的链表。现在代替 n 的运行次。我们可以合理地说，我们的新运行时间将是 n/26。现在，如果您有一个 100 万大的列表，那根本不会有太大的不同。但是我们只是为了让这个例子保持简单。

所以我们有一个链表数组，但我们如何将我们的用户排序到数组中。好吧……我们为什么不做一个决定哪个用户应该去哪里的功能。这个函数将 "hash" 用户如果你将成一个数组或 "table"。所以让我们创建这个 "hashed" 链表。因此名称哈希 table

散列Table

正如我刚才所说，我们的散列 table 将是一个链表数组，并将按其用户名的首字母进行散列。 A 将转到位置 0，B 将转到 1，依此类推。

这个散列 table 的 struct 将与我们之前链表的结构相同

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

现在就像我们的链表一样，我们的散列需要一个根 table

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->name, 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;
        }
    }
}

这就是散列的基础知识 table。如果您知道如何使用指针和结构，这将非常简单。我知道这是一个非常简单的散列 table 示例，只有一个插入函数，但您可以使它变得更好，并通过您的散列函数获得更多创意。您还可以根据需要使数组变大，甚至可以使用多维数组。

什么是散列 table 以及如何在 C 中制作它？

What is a hash table and how do you make it in C?

c

data-structures

struct

hashtable