C Academy · 课时

调整大小与负载因子

Q: 「调整大小与负载因子」这节课中我会学到什么？

性能调优 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

性能调优

调整大小与负载因子 是 CoddyKit 上的免费 C Academy 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

什么是负载因子

负载因子是已存储条目数与桶数之比：alpha = size / capacity。它用于衡量哈希表的填充程度，并直接影响性能。

负载因子为何重要

随着负载因子升高，桶中的链会变长（或者探测位置会发生聚集），因此操作速度会变慢。

较低的 alpha：速度快，但浪费内存
较高的 alpha：结构紧凑，但速度慢

链接法中常见的目标值是0.75。

计算负载因子

将其计算为浮点数比值，以便与阈值进行比较。

#include <stdio.h>

int main(void) {
    unsigned size = 12, capacity = 16;
    double alpha = (double)size / capacity;
    printf("load factor = %.2f\n", alpha);
    return 0;
}

何时调整大小

每次插入后，检查负载因子是否超过阈值。如果超过，就扩容哈希表（通常将容量加倍），然后重新哈希。

#include <stdio.h>

int should_grow(unsigned size, unsigned cap) {
    return (double)size / cap > 0.75;
}

int main(void) {
    printf("%d\n", should_grow(13, 16)); /* 0.8125 -> 1 */
    printf("%d\n", should_grow(10, 16)); /* 0.625  -> 0 */
    return 0;
}

重新哈希的原理

不能直接复制桶，因为每个键的索引取决于容量。重新哈希会根据新容量重新计算每个键对应的桶，并将其重新插入。

调整大小函数

分配一个更大的新桶数组；遍历旧数组中的每个节点，根据新容量将其移动到新数组；然后交换两个数组。下面是重新计算索引的核心代码。

#include <stdio.h>

unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

int main(void) {
    const char *key = "session";
    unsigned old_cap = 8, new_cap = 16;
    printf("old slot = %lu\n", djb2(key) % old_cap);
    printf("new slot = %lu\n", djb2(key) % new_cap);
    return 0;
}

移动节点而不重新分配

使用链接法时，可以将已有节点移动到新数组中，而不分配新节点。逐个分离节点，重新计算其桶索引，然后将其插入链表头部。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; struct Node *next; } Node;
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

int main(void) {
    Node *old[2] = {0};
    Node *a = malloc(sizeof *a); a->key = strdup("x"); a->next = NULL; old[0] = a;
    Node *new_b[4] = {0};
    /* move node a */
    unsigned i = djb2(a->key) % 4;
    a->next = new_b[i]; new_b[i] = a;
    printf("moved to slot %u\n", i);
    return 0;
}

增长策略

将容量加倍可以使摊销插入成本保持为 O(1)：虽然一次调整大小需要 O(n)，但发生得足够少，因此每次插入的平均成本仍保持不变。

容量为 2 的幂时，还可以使用快速的 AND 掩码。

#include <stdio.h>

int main(void) {
    unsigned cap = 8;
    for (int i = 0; i < 4; i++) {
        printf("capacity = %u\n", cap);
        cap *= 2;
    }
    return 0;
}

缩容

在多次删除后，如果负载因子降得过低（例如低于 0.1），可以选择缩容。缩容能够回收内存，但会增加重新哈希的成本，因此应谨慎执行，以避免频繁调整。

开放寻址法与负载因子

开放寻址哈希表对负载因子敏感得多。当 alpha 接近 1 时，性能会崩溃，因此通常在0.5 到 0.7时调整大小，这低于链接法的 0.75。

摊销成本演示

模拟在负载因子达到 0.75 时将容量加倍的插入操作，并统计总工作量，展示平均成本如何保持较低。

#include <stdio.h>

int main(void) {
    unsigned cap = 4, size = 0;
    long work = 0;
    for (int i = 0; i < 100; i++) {
        size++; work++; /* the insert */
        if ((double)size / cap > 0.75) { work += size; cap *= 2; } /* rehash */
    }
    printf("inserts=%u total_work=%ld avg=%.2f\n", size, work, (double)work/size);
    return 0;
}

快速检查

测试您对调整大小的理解。

回顾

您学会了如何调整哈希表的性能。

负载因子 = 大小 / 容量
超过阈值时调整大小（链接法通常约为 0.75）
由于索引取决于容量，因此需要重新哈希
容量加倍可使插入操作达到摊销 O(1)

常见问题解答

「调整大小与负载因子」课时是免费的吗？

是的 — 「调整大小与负载因子」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「调整大小与负载因子」这节课中我会学到什么？

性能调优你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 4 节课，共 4 节。

「调整大小与负载因子」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C Academy