cs126 maps

What is a map?

• An ADT that models a searchable collection of key-value entries

• Also known as an associative array

• Each key is unique

What are some applications for a map?

• Mapping a student’s ID to the student’s record

• DNS maps a hostname to an IP address

• Computer graphics system maps a color to an RGB code

What does the map operation get(k) do?

If the map has an entry with key k, it returns its associated value; otherwise it returns null.

What does the map operation put(k,v) do?

• Inserts an entry (k, v) into the map

• If key k is not already in the map, it returns null

• Otherwise, it returns the old value associated with k

What does the map operation remove(k) do?

If the map has an entry with key k, it removes and returns its associated value, otherwise it returns null.

What does the map operation entrySet() do?

Returns an iterable collection of the entries in the map.

What does the map operation keySet() do?

Returns an iterable collection of the keys in the map.

What does the map operation values() do?

Returns an iterator of the values in the map.

Describe the performance of a list-based map.

• The basic methods put(), get() and remove() take O(n) time since in the worst case (when the item is not found) we traverse the entire sequence to look for an item with the given key

• It is effective only for maps of a small size