Virtual machine access globals by index or hash

Question

I am creating my own class based language and virtual machine. It is statically scoped and I am trying to evaluate pros and cons about using an array versus an hash table to represents slots in a global table. I know that using an array would be much faster than using an hash table by I am wondering in terms of flexibility what could be the advantages of the hash table implementation.

For example, the code var a = 1; can be represented at runtime as:

PUSH 1;
SET_GLOBAL 0;

where 0 in the SET_GLOBAL instruction can represent an index inside a global array or an index inside a constant pool for the identifier "a" (an hash table would be used in this case). My question was about pros/cons of the array/hash usage in this particular case...

Answer 1

First of all let's see what are the requirements of the symbol/global table.

Symbol/Global Table Requirements :- // taken from this link

1. fast lookup.

2. flexible in structure.

3. efficient use of space.

4. handle characteristics of language (e.g., scoping, implicit declaration)

You're incorrect in assuming I know that using an array would be much faster than using an hash table. Arrays are OK for languages which are very small and don't need dynamic behaviour implementation.

Nowadays,almost all of the high-level language compilers implement their symbol table using HashTable.

The main points where Array will lag behind HashTable are

1. no flexibility to add new identifiers

2. upto some extent slower lookup than in hashing

3. in case of global variables, chaining will take proper care by referencing to the older entry.