CS50最后教了我什么关于C的

CS50的拼写检查问题集是指针对我真的变成现实的地方，不是介绍它们的讲座。这也是让我熬了两晚过我本来计划完成的问题集，所以这个有一些历史。

那时我已经用了多年的Python（一个Django CRM，一堆爬虫，boot.dev的bookbot）而不曾需要想象内存作为一个我管理的东西。Python就是不会问你。C立刻问你，而拼写检查是让你真正回答的作业。

问题集，大致

把约143万个单词的字典加载到哈希表里，对碰撞使用链表，然后对它检查拼写一个文本文件速度要足够快这样check50不会超时。启动代码给你函数签名的头文件：load、check、hash、size、unload。其他的一切，你构建。

typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

一个这些的链表，每个哈希桶一个。我首次实际需要理解next不是下一个节点的一个复制，它是它的地址，是讲座的白板图表变成我可以推理而不只是点头赞同的时刻。

我的第一个哈希函数，有意没有意义地糟糕

CS50提前告诉你哈希函数是速度生活或死亡的地方，我第一次通过没有认真对待。

unsigned int hash(const char *word)
{
    return tolower(word[0]) % N;
}

单词的第一个字母，模表大小。它编译了。它甚至正确运行，在check对每个单词返回正确答案的意义上。它只是花了大约四十秒来加载和检查一个真实字典，check50不认为是通过时间。

那真正意味着什么

二十六个字母分布在我设置N到的多少水桶意味着每个水桶持有在一个长链表里的数千个单词，查找一个单词意味着走那整个列表，一次一个节点，比较字符串。哈希表只有在哈希真正分散单词时快。我的是函数上只是每个首字母一个巨大链表，这是一个链表应该帮助的东西的更糟版本。

修复，和哪里实际漏洞还是

我切换到一个真实字符串哈希，那种混合每个字符的而不只是第一个。

unsigned int hash(const char *word)
{
    unsigned int h = 0;
    for (int i = 0; word[i] != '\0'; i++)
    {
        h = (h * 31) + tolower(word[i]);
    }
    return h % N;
}

加载时间从四十秒掉到两秒以下。那部分感觉很棒。那不感觉棒的是load()里这介绍的segfault，我没有触碰，在一小时前工作得很好的完全同样的字典上。

它实际在哪里打破

node *n = malloc(sizeof(node));
strcpy(n->word, word);
n->next = table[index];
table[index] = n;

看起来很好。在小字典上运行很好。valgrind（CS50让你实际使用，不只是在讲座中提到）告诉我一旦我对大那个跑它，确切什么错了。

==12345== Invalid write of size 1
==12345==    at 0x1091A2: load (dictionary.c:47)
==12345==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

我没有检查malloc的返回值，在大字典上，足够深入到运行里，一个分配实际失败了。用坏哈希函数这从来没有表面出现，因为所有东西是这样慢内存压力从来没有在测试工具放弃等待之前用同样方式构建。更快哈希函数意味着更多分配在更少时间内发生，这意味着我实际击中我的旧的、更慢的、更糟代码一直以来意外隐藏的失败情况。

一个if (n == NULL) return false;修复了它。漏洞根本不是关于指针。它是关于假设一个可以失败的函数会永远成功，因为它做了前五十次我跑它，让程序的其余部分更快正是那种可以暴露一个漏洞的改变那一直都在那里。

第二个漏洞，在一个完全不同的函数

unload()应该走每个水桶并自由每个节点。我的看起来，对我，完全正确：

bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node *cursor = table[i];
        while (cursor != NULL)
        {
            free(cursor);
            cursor = cursor->next;
        }
    }
    return true;
}

valgrind再次，有耐心如同以往：

==12345== Invalid read of size 8
==12345==    at 0x109310: unload (dictionary.c:63)
==12345==  Address 0x51fc0a0 is 0 bytes inside a block of size 24 free'd

读-后-自由。我自由了cursor，然后立刻从我刚刚告诉分配器可以重用的内存读cursor->next。在这个特定运行它碰巧仍然持有正确值，直到它偶尔没有，这正是那种通过本地和在别的地方失败的漏洞因为你看不到的没有理由。修复是在自由当前节点之前保存下一个指针，不是之后。

node *cursor = table[i];
while (cursor != NULL)
{
    node *next = cursor->next;
    free(cursor);
    cursor = next;
}

两个漏洞，同样问题集，同样根本原因下面两者：我保持用一个指针的值在它停止安全信任的时刻之后，一旦因为一个我调用的函数可以默默失败，一次因为我已经告诉系统那内存可以重用。C不停止你做任何一个。它只是最终展示你，在一个时间和位置它选择的，通常不是实际错误被做的线。

一个更小的旁注，自从在这个问题集醒得过晚值得一个诚实的切线

某处围绕凌晨1点在第二晚我确信字典文件本身被损坏了，因为一个特定运行保持表现不同从一个看起来相同的之前运行。它不是文件。它是那个malloc失败在内存压力下是概率性的，不是确定性的，所以完全相同的输入不总是触发它取决于别的什么机器碰巧在做。我在一个字典文件上花了真正尴尬的大量时间diffing对自己在我接受漏洞在我的代码，不是数据之前。

什么实际粘住

不是语法。规则：每个指针要么指向某个真实的地方，要么它是NULL，要么它是垃圾，C永远不会告诉你哪个，所以你不得不。Python悄悄地保护你不曾需要想象那。C把整个责任递给你并主要走开，包括不读内存的责任立刻在你自由了它之后。

我在下一个问题集上会做不同的什么

从第一个工作版本运行valgrind，不只是一旦什么打破了。两个漏洞这里坐在对代码有一段看起来很好并通过随意测试在实际表面化之前。等待一个崩溃去找到那会更早抓住它的工具是一个习惯我想要在它花费我超过一个晚睡眠之前学习放弃。

我仍然不完全信任我自己的指针算术在数组上。那是一个以后问题集的问题。