Symbol Table is a data structure used to store key-value stores, it is used by every compiler for almost every phase of compilation, starting with lexical analysis and continuing with optimization.
They are collection of key-value pairs, where we can insert a value with a specific key, and search for a value given it’s key. Also known as maps, dictionaries, or associative arrays. Primary operations of a symbol table are put, get, delete, contains and isEmpty.
A symbol table may be implemented in few different ways, unordered array, linked list, hash table, etc. Usually there are few assumptions made before implementing a symbol table:
- Generics – key and value should be a generic type
- Duplicates – no duplicates key can exists, only one value is associated with a key.
- Null – no null value is allowed, a null value means an in-existent item.
- Keys – depending on implementation key may require to be Comparable or equals() method can be used for checking if two keys are equal.
Unordered Symbol Tables means that keys are stored in an unsorted data structure and if using a double array ( storing key’s in one and value in another ) or using linked list – it may result in similar complexity:
- O(n) – add operation
- O(n) – get operation
- O(n) – delete
- O(n) – contains
- O(1) – isEmpty
Ordered Symbol Table is possible to implement using an ordered array ( Binary Search Tree can be implemented as an array and children of node k will be accessible at position 2k+1 and 2k+2 ) and performance will be better:
Unordered Vs Ordered Symbol Table Implementations Analysis — algs4.cs.princeton.edu
A good tutorial about Symbol Tables can be found on OmarElGabry Blog: https://medium.com/omarelgabrys-blog/symbol-tables-associative-arrays-ece1f52aa07f