Symbol Tables

The IMap interface defines a symbol table abstraction.

A symbol table maps each Key from a set to a Value.

• Get, Put, Delete - Fetch, place and delete key-value pairs from the table respectively
• Contains - Determines whether a key exists in the table
• Pairs - iterate through the key-value pairs of the table

Two implementations are available:

Implementation	Performance	Std. lib equivalent
HashMap	Constant (amortized)	Dictionary
TreeMap	Logarithmic	SortedDictionary

A HashMap forms an associative array abstraction by indexing keys into an array by their hash value. Hash collisions are dealt with by storing keys with the same hash in a linked list. The backing array is periodically resized to maintain constant time access to pairs.

The TreeMap wraps over a RedBlackTree, limiting the API to that of IMap. If you wish to use a richer API use an ITree instead.

Compared to a HashMap the performance profile of a TreeMap is consistent, but keys must be totally ordered.