编译处理时，涉及变量及属性（如：变量类型）的管理：
- 插入：新变量定义
- 查找：变量的引用
编译处理中对变量管理：动态查找问题
利用 查找树（搜索树）进行变量管理？
两个变量名（字符串）比较效率不高
是否可以先把字符串转换为数字，再做处理？
- 目前已知的几种查找方法：
- 顺序查找：
- 二分查找（静态查找）：
- 二叉搜索树：，为二叉搜索树的高度 平衡二叉树：
- 查找的本质：已知对象找位置
- 有序安排对象：全序、半序；
- 直接“算出”对象位置：散列
- 散列查找法的两项基本工作：
- 计算位置：构造散列函数确定关键词存储位置；
- 解决冲突：应用某种策略解决多个关键词位置相同的问题
- 时间复杂度几乎是常量：，即查找时间与问题规模无关
散列表（哈希表）
- 类型名称：符号表（
SymbolTable）
- 数据对象集：符号表是“名字（
name）-属性（Attribute）”对的集合
- 操作集：
TableSymbolTable，NameNameType，AttrAttributeType
- 装填因子（Loading Factor）：设散列表空间大小为，填入表中元素个数是，则称为散列表的装填因子。
- “散列（Hashing）”的基本思想是：
- 以关键字
key为自变量，通过一个确定的函数（散列函数），计算出对应的函数值，作为数据对象的存储地址 - 可能不同的关键字会映射到同一个散列地址上，即，称为“冲突（collision）”——需要某种冲突解决策略
散列函数的构造方法
- 一个“好” 的散列函数一般应考虑一下两个因素：
- 计算简单，以便提高转换速度；
- 关键词对应的地址空间分布均匀，以尽量减少冲突。
数字关键词的散列函数构造
- 直接定址法：取关键词的某个线性函数值为散列地址，即（、为常数）
- 除留余数法：散列函数为，如
- 数字分析法：分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址。
- 比如：取11位手机号码的后4位作为地址，散列函数为：
在这里，
key实际上是个字符串，key+7是地址的偏移，如下图：
int atoi( char* s ) ：将类似“5678”的字符串转换为整数5678- 折叠法：把关键词分割成位数相同的几个部分，然后叠加。
- 平方取中法：把这个数先平方，再取中间几位。
字符关键词的散列函数构造
- 一个简单的散列函数——ASCII码加和法。 对字符型关键词定义散列函数如下：
- 简单的改进——前3个字符移位法
- 缺点：
- 仍然冲突：string、street、strong、structure等；
- 空间浪费：
- 好的散列函数——移位法：设计关键词所有个字符，并且分布的很好：
比如，我们可以考虑32进制（这样考虑的两个原因：1.，可以表示所有数字；2.32也就是左移5位）：
更简便的算法：
处理冲突方法：
- 常用处理冲突思路：
- 换个位置：开放地址法
- 同一位置的冲突对象组织在一起：链地址法
- 开放地址法：（Open Addressing）：一旦产生了冲突（该地址已有其他元素），就按某种规则取寻找另一空地址。
- 若发生了第
i次冲突，试探的下一个地址将增加，基本公式是： - 决定了不同的解决冲突方案：线性探测（），平方探测（），双散列（）