符号表
定义
定义:符号表是一种存储键值对的数据结构,支持两种操作:插入(put),将一组新的键值对存入表中;查找(get),根据给定的键值的到对应的值。
一种有序的泛型符号表的API实现的对字符表的操作
字符表的实现
无序链表实现无序字符表
1 |
|
基于链表的实现及顺序查找是非常低效的
向一个空表中插入N个不同的键需要~N*N/2次比较
基于有序数组的二分查找实现有序字符表
1 | public class BinarySearchST<Key extends Comparable<Key>,Value> { |
算法分析:
有序数组二分查找的各个操作的成本:
BinarySearchST的算法实现了最优的查找效率~lgN,但是插入操作很慢~N,无法保证高效的查找和插入操作。