Symbol Table

Introduction

A symbol table is a relationship between a string (key) and a value of any datatype. A value can be an integer, such as the number of occurrences of a term in the dictionary, the meaning of a word, and so on.

Let’s look at some examples to understand symbol tables better.

Binary search tree (BST)

The easiest approach to create a symbol table is to use a BST. To compare two strings, use the simple string comparison method. If the tree is balanced and all keys are random, then a key lookup operation takes logarithmic time $O(log(n))$.

Let’s look at an illustration of a BST.