A symbol table is an associative array.
It’s a good idea to make the keys orderable for performance reasons (it also opens up more options for implementations). It’s also a good idea to make the key immutable.
Implementations
- Linked List: This is unordered and each element is the pair of key and its value. To insert an element, first scan through and if no match is found, add to the front of the list. Not a great implementation. Everything is \(O(N)\).
- Binary search in an ordered array. Insertion is still a problem as you have to shift all the elements on the right. Search is \(O(\lg N)\).
- Binary Search Trees: Let the information be stored as a binary search tree. All operations are now \(O(h)\) (the height of the tree).
- Hash Functions: Construct a hash table using hashes. The keys must be hashable, and we lose any ordering.
Hashing vs Binary Search Tree
- Whenever a hash function is used, there is a possibility of an attack occurring. BSTs will not have this problem.
- Ordering may have its benefits depending on the application.
- Hashing may be faster for simply types.