Think Data Structures

Chapter 9. The Map Interface

In the next few exercises, I present several implementations of the Map interface. One of them is based on a hash table, which is arguably the most magical data structure ever invented. Another, which is similar to TreeMap, is not quite as magical, but it has the added capability that it can iterate the elements in order.

You will have a chance to implement these data structures, and then we will analyze their performance.

But before I can explain hash tables, I’ll start with a simple implementation of a Map using a List of key-value pairs.

Implementing MyLinearMap

As usual, I provide starter code and you will fill in the missing methods. Here’s the beginning of the MyLinearMap class definition:

public class MyLinearMap<K, V> implements Map<K, V> {

    private List<Entry> entries = new ArrayList<Entry>();

This class uses two type parameters, K, which is the type of the keys, and V, which is the type of the values. MyLinearMap implements Map, which means it has to provide the methods in the Map interface.

A MyLinearMap object has a single instance variable, entries, which is an ArrayList of Entry objects. Each Entry contains a key-value pair. Here is the definition:

    public class Entry implements Map.Entry<K, V> {
        private K key;
        private V value;
        
        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
        
        @Override
        public K getKey() {
            return key;
        }
        @Override
        public V getValue() {
            return value;
        }
    }

There’s not much to it; an Entry is just a container ...