Map is an abstract data type that maps value elements against unique data keys. The

following questions ask you to consider and evaluate aspects of different implementation

strategies for ADT Map.

A simple Map implementation involves using an underlying array of elements.

Describe how the operations put $(k,v)$ and get$(k$ would operate on an array$-$

backed map, and why this is often an undesirable implementation strategy.

Hash Map can often be an advantageous implementation; delivering several

benefits over a list$-$backed map. Identify and describe one of these advantages

when considering time complexity. Include a description of which ADT Map

operations this would significantly affect and why.

Considering the underlying operation of a Hash Map, describe the purpose and

typical operation of the hash and compress functions. Explain how they fit into the

operation of the hashtable and their expected behaviour.

The term collision is used in conjunction with Hash Map implementations.

Describe i$)$ its meaning and underlying cause, and ii$)$ what effect it has if left

unmanaged. Finally, iii$)$ select and explain an approach that a hash map mayuse

to manage a collision.