3.5 应用

3.5.1 符号表的选择

  • 散列表:对比BST,散列表代码简单,查找时间最优
  • BST:抽象结构简单,无需设计散列函数
  • 红黑树:可以保证最坏情况的性能
  • 一般情况下,不考虑有效操作,首先选择散列表,其次才是红黑树

符号表渐进性能总结

算法 最坏查找 最坏插入 平均查找命中 平均插入
顺序查找(无序链表) N N N/2 N
二分查找(有序数组) lgN N lgN N/2
BST N N 1.39lgN 1.39lgN
红黑树 2lgN 2lgN 1.00lgN 1.00lgN
拉链法 <lgN <lgN N/(2M) N/M
线性探测法 clgN clgN <1.5 <2.5

3.5.1.3 Java标准库

Java的TreeMap和HashMap分别是基于红黑树和拉链法散列表的符号表