符号表的内存使用
| 方法 | N个元素所需的内存（引用类型） |
|---|---|
| 基于拉链法的散列表 | ~48N + 32M |
| 基于线性探测的散列表 | ？ 在~32N 和 ~128N之间 |
| 各种二叉查找树 | ~56N |
拉链法和线性探测法的详细比较取决于实现的细节和用例对空间和时间要求，即使基于性能考虑，选择拉链法而非线性探测法也不一定是合理的，在实践中，两种方法的性能差别主要是因为拉链法为每一个键都分配了一小块内存而线性探测则为了整个表使用了两个很大的数组
对于散列表来说，并非是包治百病的灵丹妙药，因为
- 每种类型的键都需要一个优秀的散列函数。
- 性能保证保证来自散列函数的质量
- 散列函数的计算可能复杂而昂贵
- 难以支撑有序性相关的符号表操作
符号表的比较
| 算法（数据结构） | 最坏情况下的运行时间的增长数量级（N次插入之后） | - | 平均情况下的运行时间的增长数量级（N次随机插入之后） | - | 关键接口 | 内存使用 |
|---|---|---|---|---|---|---|
| - | 查找 | 插入 | 查找命中 | 插入 | - | - |
| 顺序查询（无序链表） | N | N | N/2 | N | equals() | 48N |
| 二分查找（有序数组） | lgN | N | lgN | N/2 | compareTo() | 16N |
| 二叉树查找（二叉查找树） | N | N | 1.39lgN | 1.39lgN | compareTo() | 64N |
| 2-3树查找树（红黑树） | 2lgN | 2lgN | 1.00lgN | N/2 | compareTo() | 64N |
| 拉链法（链表数组） | <lgN | <lgN | N/(2M) | N/M | equals();hashCode() | 48N + 32N |
| 线性探测法（并行数组） | clogN | clgN | <1.5 | <2.5 | equals();hashCode() | 在32N和128N之间 |
如表可以知道，对于典型的应用程序，应该在散列表和二叉树之间进行选择。
相对于二叉查找树，散列表的优点在于代码更加简单，且查找时间最优（常数级别，只要键的数据类型是标准的或者简单到我们可以为他写出满足（或者近似满足）均匀性假设的高效散列函数即可）。
二叉查找树相对于散列表的优点在于抽象结构更简单（不需要设计散列函数），红黑树可以保证最坏情况下的性能且它能够支持的操作更多（如排位，选择，排序和范围查找）。