先决条件
对于这个答案，我将假设您知道如何使用指针，结构，并对C语言有基本的了解。
另外，如果您不知道。在谈论算法和数据结构的速度时，您应该了解以下术语:
O()=(它的发音为“Big-oh”)Big-oh或O()表示“最坏情况”的运行时。同样，在数学中，它是一个大的O表示法，它描述了函数的限制行为。如果某个时间为O(1)，则表示“确实很好”。如果是O(n)，则表示列表长度为一百万。最坏的情况是要运行一百万次。 O()通常是用来确定某事物运行速度的函数，因为在最坏的情况下它就是运行速度。
Ω=(希腊字母Omega)表示最佳情况。它没有像O()那样被广泛使用，所以我不会在此赘述。但是，只要知道如果是Ω(1)，在最佳情况下就只用一次。
Θ=(希腊字母theta)的唯一性在于，仅当O()和Ω()运行时间相同时才使用。因此，就像在递归排序算法merge sort的情况下一样。它的运行时间是Θ(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多个用户。哦!我们最好增加该数组的大小，否则将导致缓冲区溢出。
那么我们该怎么做呢？好了，我们将不得不制作一个更大的新数组，并将旧数组的内容复制到新数组中。
那是非常昂贵的，我们不想这样做。我们想聪明地思考，不要使用大小固定的东西。好了，我们已经知道如何使用指向自己的优势的指针，并且如果愿意，可以将信息 bundle 到
struct中。
因此，我们可以创建一个
struct来存储用户名，然后使其(通过指针)指向新的
struct。瞧!现在，我们有了一个可扩展的数据结构。它是由指针链接在一起的 bundle 信息的列表。因此名称链表。
链接列表
因此，让我们创建该链接列表。首先，我们需要一个
struct
typedef struct node
{
char* name;
struct node* next;
}
node;
好吧，我们有一个字符串
name和一个...等等，我从未听说过一种称为
struct node的数据类型。为方便起见，我
typedef一个新的称为
node的“数据类型”，它也恰好是我们的名为
struct的
node。
因此，既然我们有了 list 的节点，下一步需要什么？好吧，我们需要在列表中创建一个“root”，以便我们对其进行
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一样，绳索充当指向它们所在位置的指针。那么我们如何到达谷仓呢？ (在此示例中，谷仓是列表中的最后一个“人”)。好吧，我们不知道我们的人脉有多大或者他们去哪里。实际上，我们所看到的只是一个绑有绳子的栅栏柱。 (我们的根!)该围栏帖子永远不会改变，因此我们可以捕获该帖子并开始前进，直到我们看到第一个人为止。该人拿着两条绳子(岗位的指针和他们的指针)。
因此，我们一直沿着绳索前进，直到我们结识新 friend 并捕获他们的绳索。最终，我们走到了尽头，找到了我们的谷仓!
简而言之，这是一个链接列表。它的好处是它可以根据需要进行扩展，但是其运行时间取决于列表的大小，即O(n)。因此，如果有100万用户，则必须运行100万次才能插入新名称!哇，仅插入1个名字似乎真的很浪费。
幸运的是，我们很聪明，可以创建更好的解决方案。为什么我们不仅仅拥有一个链表，而是拥有一些链表。如果需要的话，一个由链表组成的数组。我们为什么不做一个大小为26的数组。所以我们可以为每个字母组合一个唯一的链表。现在，而不是运行时间n。我们可以合理地说我们的新运行时间为n / 26。如果您拥有一百万个大型列表，那么这根本不会有太大改变。但是在这个示例中，我们将保持简单。
因此，我们有一个链接列表数组，但是如何将用户分类到该数组中。好吧...为什么我们不做一个决定哪个用户应该去哪里的功能。如果要进入数组或“表”，此功能将“散列”用户。因此，让我们创建此“哈希”链接列表。因此名称哈希表
哈希表
就像我刚才说的那样，我们的哈希表将是一个链接列表的数组，并将通过其用户名的第一个字母进行哈希处理。
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->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;
}
}
}
这就是哈希表的基础。如果您知道如何使用指针和结构，则非常简单。我知道这是一个仅带有插入函数的哈希表的非常简单的示例，但是您可以使其变得更好，并通过哈希函数获得更多创意。您还可以将数组设为所需的大小，甚至可以使用多维数组。
个人中心
文章发布
退出
24
4
0
我是一名优秀的程序员,十分优秀！