符号表

什么是符号表

符号表就是一种「以键值对方式」存储数据的数据结构。人类使用的几乎所有数据集都可以表示为「键值对」，其中，键要保持唯一性。

接口设计

• 插入键值对
• 通过「键」查找键值对
• 通过「键」删除键值对
• 其它辅助性函数方法

行为测试

测试设计好的数据结构的行为表现能否与预期一致。

性能测试

测试设计好的数据结构的各种行为的性能表现。

具体实现

要么是以数组为原型，要么是以链式结构为原型，要么是以两者混合的结构为原型。

整个计算机世界，是以少数几个非常优秀的数据结构和算法为基础支撑的。

链表实现：无序的顺序符号表

链表

基于有序数组实现，两个数组

递归的二分查找 迭代的二分查找

结合链式结构和二分查找：二叉查找树实现符号表

简单，但有效，但性能表现不够稳定

平衡查找树

2-3 查找树，稍微复杂，但是性能表现稳定。

2-3 查找树的具体实现使用「红黑二叉查找树」，高效稳定。

散列表

基于 hash 函数，将「键值对」映射为「地址-值对」。

总结

纵览全局，学习的同时能够从全局的高度来连贯性理解。