calc7 — 哈希表符号表1. 概述本次迭代将 calc5 引入的线性查找符号表替换为哈希表实现大幅提升变量查找性能和容量上限。性能变化指标calc5/calc6线性数组calc7哈希表数据结构线性查找数组djb2 哈希 线性探测变量上限64256查找复杂度O(n)O(1) 平均动态内存分配无无静态数组外部 API不变不变2. 变更清单文件操作说明sym.h编辑SYM_MAX 64→SYM_BUCKETS 256sym.c重写线性查找数组 → 哈希表实现其余文件无需改动API 签名不变eval.c/main.c零改动3. 哈希表设计3.1 数据结构#defineSYM_BUCKETS256typedefstruct{charname[32];intvalue;intoccupied;/* 0 空槽1 已占用 */}SymEntry;staticSymEntry sym_table[SYM_BUCKETS];采用开地址法Open Addressing所有条目存储在静态数组中不引入malloc保持零动态内存分配。3.2 哈希函数djb2staticunsignedlonghash(constchar*str){unsignedlongh5381;intc;while((c(unsignedchar)*str))h((h5)h)(unsignedlong)c;returnh%SYM_BUCKETS;}djb2 由 Daniel J. Bernstein 设计以其良好的分布性和简单性著称适合字符串哈希场景。3.3 冲突解决线性探测当哈希值冲突时顺序检查下一个槽位直到找到同名条目或空槽unsignedlongidxhash(name);for(inti0;iSYM_BUCKETS;i){unsignedlongcur(idxi)%SYM_BUCKETS;if(!sym_table[cur].occupied){/* 空槽 → 写入新条目 */memcpy(sym_table[cur].name,name,n);sym_table[cur].valueval;sym_table[cur].occupied1;return;}if(strcmp(sym_table[cur].name,name)0){/* 已存在 → 更新值 */sym_table[cur].valueval;return;}}3.4 API 实现对比操作线性数组实现哈希表实现sym_set遍历全表查找同名再找空槽哈希定位 → 线性探测sym_get遍历全表匹配哈希定位 → 线性探测sym_print遍历 sym_count 个条目遍历 256 个桶检查 occupiedsym_clearsym_count 0memset(sym_table, 0, sizeof(sym_table))4. 目录结构calc/ ├── Makefile ├── parse.h / parse.c ├── eval.h / eval.c ├── sym.h / sym.c # 哈希表实现 ├── main.c ├── test.expr # 24 个测试用例 ├── doc/ │ ├── calc1.md # tokenizer 基础 │ ├── calc2.md # 取模、负号区分、测试套件 │ ├── calc3.md # 表达式求值器 │ ├── calc4.md # 交互式 REPL │ ├── calc5.md # 变量绑定 增强错误提示 │ ├── calc6.md # 测试覆盖增强 │ └── calc7.md # 本次构建哈希表符号表 └── build/ └── calc5. 测试验证$maketestcalc — 测试套件PASS[1](90-18)/315 →39PASS[2]10%3 →1PASS[3]-53 →-2PASS[4]3-5 →-2PASS[5](-3)→-3PASS[6](-820)%-3 →0PASS[7]35→8PASS[8]35*2 →13PASS[9](35)*2 →16PASS[10]10/23 →8PASS[11]10%3*2 →2PASS[12]--5→5PASS[13]-3*2 →-6PASS[14]12345 →15PASS[15]((35)*2)→16PASS[16]35 → error PASS[17]3/0 → error PASS[18]3%0 → error PASS[19](35 → error PASS[20]35)→ error PASS[21]35 x → error PASS[22]empty→ error PASS[23]x5→ error PASS[24]y10→ error24passed,0failed,24total内部实现变更对外行为不变24/24 回归测试全部 PASS。
