Key-Indexed Symbol Table
Consider the following special case:
- keys are integers in a relatively small range (e.g.
0..N-1 )
- symbol data implemented as array of
Item (e.g. Item a[N] )
- indexed by
Key values (mapped into valid index) (e.g. it = a[k] )
Leads to very efficient representation
- Cost(
insert ) = O(1), Cost(search ) = O(1),
- Cost(
newSTab ) = O(N), Cost(count ) = O(1),
- Cost(
get_ith ) = O(1), Cost(delete ) = O(1)
|