[prev] [index] [next]

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)