什么是哈希表,你如何在C中创建它？

Question

我对一个称为哈希表(也称为关联数组)的数据结构以及如何在C中实现它有几个问题.

你如何在C中创建哈希表？什么是哈希表,你如何实现它？为什么我要使用哈希表而不是数组？

注意:我知道这是一个非常广泛的问题,需要一个很大的答案,但我这样做是因为我有一些人问我这是什么.所以我把它放在这里以充分解释它并帮助其他人.

Answer 1

先决条件

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

如果你不知道的话.在谈论算法和数据结构的速度时,您应该了解以下术语:

O()=(它的发音为"Big-oh")Big-oh或O()指的是"最坏情况"运行时.类似地,在数学中,它是一个很大的O符号并描述了函数的限制行为.如果有事O(1)那个恒定的时间"非常好".如果有些事情O(n)意味着这个名单是一百万长.最坏的情况是运行一百万次.O()通常是用来确定某些东西运行速度的那个,因为它在最坏的情况下运行的速度有多快.

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

Θ=(希腊字母theta)是唯一的,因为它仅在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个用户.嗯,哦!我们最好增加该数组的大小,否则我们会得到缓冲区溢出.

那我们该怎么做呢？好吧,我们必须创建一个更大的新数组,并将旧数组的内容复制到新数组中.

这是非常昂贵的,我们不想这样做.我们想巧妙地思考而不是使用具有固定大小的东西.好吧,我们已经知道如何使用指针优势,如果我们愿意,我们可以将信息捆绑到一个结构中.

所以我们可以创建一个结构来存储用户名,然后让它(通过指针)指向一个新结构.中提琴!我们现在有一个可扩展的数据结构.它是通过指针链接在一起的捆绑信息列表.因此名称链表.

链接列表

所以让我们创建那个链表.首先,我们需要一个结构

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

好吧所以我们有一个字符串struct和一个......等一下......我从来没有听说过一个名为a的数据类型struct.为了方便起见,我将struct一个新的"数据类型"称为节点,它也恰好是我们的结构,称为节点.

那么现在我们的列表中有我们的节点,现在我们需要什么？好吧,我们需要在列表中创建一个"根".所以我们可以遍历它(我将在后面解释我的意思).所以让我们分配一个根.(记住之前的节点数据类型I typdef)

node* first = NULL;

所以现在我们有了root,我们需要做的就是创建一个函数来将新的用户名插入到我们的列表中.

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

你去吧 我们有一个基本的链接列表,现在我们可以继续添加我们想要的用户,我们不必担心用完房间.但这确实伴随着不利因素.这个问题的一大问题是我们列表中的每个节点或"用户"都是"匿名的".我们不知道他们是谁,甚至我们有多少用户.(当然有很多方法可以做得更好,但我只想展示一个非常基本的链表)所以我们必须遍历整个列表来添加用户,因为我们无法访问结尾.

这就像我们正处于一场巨大的沙尘暴中,你看不到任何东西,我们需要到达我们的谷仓.我们无法看到我们的谷仓在哪里,但我们有一个解决方案.有人站在那里(我们的节点),他们都持有两根绳子(我们的指针).每个人只拥有一根绳子,但是另一根绳子被另一根绳子夹住.就像我们的结构一样,绳索充当指向它们所在位置的指针.那我们怎么去我们的谷仓？(对于这个例子,谷仓是列表中的最后一个"人").好吧,我们不知道我们的人员有多大或者去哪里.事实上,我们所看到的只是一个用绳子系在上面的栅栏柱.(我们的根!)围栏岗位永远不会改变所以我们可以抓住帖子并开始一直移动直到我们看到我们的第一个人.那个人拿着两根绳子(柱子的指针和指针).

因此,我们一直沿着绳索行进,直到我们找到一个新人并抓住他们的绳索.最终,我们走到尽头找到我们的谷仓!

简而言之,这是一个链表.它的好处是它可以根据需要扩展,但它的运行时间取决于列表的大小.它的运行时间是O(n).如果列表是100万大,那么它必须运行100万次才能运行以插入新名称!插入1个名字似乎真的很浪费.

幸运的是,我们很聪明,可以创造更好的解决方案.为什么我们不是只有一个链表,而是有一些链表.如果您愿意,可以使用一系列链接列表.为什么我们不做一个大小为26的数组.所以我们可以为字母表的每个字母都有一个唯一的链表.现在而不是n的运行时间.我们可以合理地说我们的新运行时间将是n/26.如果你有一个100万大的名单,现在根本不会有太大的差别.但是我们只是为了这个例子而保持简单.

所以我们有一系列链表但我们如何将用户排序到数组中.那么......为什么我们不做一个决定哪个用户应该去哪里的功能呢？如果您要进入数组或"表",此函数将"哈希"用户.那么让我们创建这个"哈希"链表.因此名称哈希表

哈希表

正如我刚才所说,我们的哈希表将是一个链表的数组,并将通过其用户名的第一个字母进行哈希处理.A将转到位置0,B转到1,依此类推.

此哈希表的结构将与我们之前链接列表的结构相同

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

现在就像我们的链表一样,我们需要一个哈希表的根

node* first[26] = {NULL};

根将是一个字母大小的数组,其中的所有位置都将初始化为struct.(记住:链接列表中的最后一个元素总是必须指向name或者我们不知道它是结束)

让我们做一个主要功能.这需要我们要哈希的用户名然后插入.

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

所以现在我们只需要创建插入函数.它看起来就像我们之前的insert函数一样,除非每次引用我们的root时,我们都会将它作为数组引用.

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

这就是哈希表的基础知识.如果你知道如何使用指针和结构,这很简单.我知道这只是一个只有插入函数的哈希表的一个非常简单的例子,但是你可以使用哈希函数使它变得更好并且更有创意.您也可以根据需要使数组变大,甚至使用多维数组.