一、符号表：编译器的“通讯录”

说到哈希表在编译器中的应用，最经典的就是符号表了。你可以把符号表想象成编译器的通讯录——它记录了每个变量、函数、结构体等标识符的详细信息。

我个人习惯把符号表看作一个“名字→属性”的映射。名字就是你在代码里写的变量名、函数名，属性则包括类型、作用域、存储类别、地址等等。编译器在解析代码时，会频繁地查这个表。

举个例子，当你写：

int age = 25;

编译器会做两件事：

• 把 age 插入符号表，记录它的类型是 int，初始值是 25
• 后续遇到 age 时，从符号表查出它的类型和地址

你想想看，如果不用哈希表，而是用线性表来存符号，每次查找都要遍历——一个大型项目几千个变量，编译速度会慢得让人抓狂。哈希表把查找时间降到了 O(1)，这才是编译器能快速处理百万行代码的关键。

二、C语言符号表的实现思路

在C语言里实现符号表，我通常会选链地址法（拉链法）来解决哈希冲突。为什么？因为符号表经常需要插入和删除（作用域进出时），链地址法对这两种操作都很友好。

2.1 基本结构定义

#define TABLE_SIZE 1024

// 符号表条目
typedef struct Symbol {
    char *name;           // 标识符名字
    int type;             // 类型（int, float, 函数等）
    int scope_level;      // 作用域层级
    int address;          // 地址或偏移量
    struct Symbol *next;  // 拉链法，指向下一个冲突条目
} Symbol;

// 哈希表本体
typedef struct {
    Symbol **buckets;     // 桶数组，每个桶是一个链表头
    int size;             // 桶的数量
} SymbolTable;

这里我用了 scope_level 字段，后面讲作用域时会用到。每个符号都记录自己属于哪一层作用域，这样退出作用域时就能快速清理。

2.2 哈希函数选择

哈希函数的选择直接影响性能。我推荐用 BKDR 哈希，它在处理字符串时分布很均匀：

unsigned int hash(const char *str, int table_size) {
    unsigned int seed = 131;  // 31, 131, 1313 都可以
    unsigned int hash_val = 0;
    while (*str) {
        hash_val = hash_val * seed + (*str++);
    }
    return hash_val % table_size;
}

为什么选 131？其实这是个经验值。我在项目中试过 31、131、1313，发现 131 对C语言标识符（字母+数字+下划线）的分布最均匀，冲突最少。

2.3 插入与查找

// 插入符号
void symbol_insert(SymbolTable *st, const char *name, int type, int scope) {
    unsigned int idx = hash(name, st->size);
    Symbol *sym = (Symbol*)malloc(sizeof(Symbol));
    sym->name = strdup(name);
    sym->type = type;
    sym->scope_level = scope;
    sym->next = st->buckets[idx];  // 头插法
    st->buckets[idx] = sym;
}

// 查找符号
Symbol *symbol_lookup(SymbolTable *st, const char *name) {
    unsigned int idx = hash(name, st->size);
    Symbol *cur = st->buckets[idx];
    while (cur) {
        if (strcmp(cur->name, name) == 0) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;  // 没找到
}

三、作用域与哈希表的配合

作用域是符号表里最让人头疼的部分。C语言有全局作用域、函数作用域、块作用域（花括号内的局部作用域）。同一个名字在不同作用域可以代表不同变量。

我曾经在维护一个老项目时，遇到一个bug：两个不同函数里都用了 i 作为循环变量，结果一个函数里改了 i 的值，另一个函数的循环也跟着乱了。原因就是符号表没处理好作用域隔离。

3.1 作用域栈

解决方法是维护一个 作用域栈。每进入一个作用域，就创建一个新的哈希表（或者用同一个表但标记层级）。退出时，删除该层所有符号。

typedef struct Scope {
    SymbolTable *table;    // 当前作用域的符号表
    int level;             // 层级，从0开始
    struct Scope *parent;  // 指向外层作用域
} Scope;

// 当前作用域指针
Scope *current_scope = NULL;

// 进入新作用域
void enter_scope() {
    Scope *new_scope = (Scope*)malloc(sizeof(Scope));
    new_scope->table = create_table(256);
    new_scope->level = current_scope ? current_scope->level + 1 : 0;
    new_scope->parent = current_scope;
    current_scope = new_scope;
}

// 退出作用域
void exit_scope() {
    if (!current_scope) return;
    Scope *old = current_scope;
    current_scope = old->parent;
    free_table(old->table);  // 释放整个哈希表
    free(old);
}

3.2 查找时的作用域规则

查找符号时，要从当前作用域开始，逐层向外查找。这符合C语言的规则：内层变量覆盖外层同名变量。

Symbol *scope_lookup(const char *name) {
    Scope *s = current_scope;
    while (s) {
        Symbol *sym = symbol_lookup(s->table, name);
        if (sym) return sym;
        s = s->parent;
    }
    return NULL;  // 所有作用域都没找到
}

嗯，这里要注意：如果只在当前作用域查找，就找不到外层变量。而逐层查找能正确处理嵌套作用域。

四、符号表的核心流程

下面这张图展示了编译器处理符号表的核心流程：

五、避坑指南

六、总结

符号表是编译器的心脏，哈希表是让这颗心脏高效跳动的关键。说白了，就是三个要点：

• 用链地址法实现哈希表，处理冲突
• 用作用域栈管理嵌套作用域
• 查找时逐层向外，插入时记录层级

掌握了这些，你就能自己实现一个轻量级的符号表了。下次写编译器或者解释器时，直接复用这套代码就行。

---