The array holds MapEntry objects. The put operation creates a new MapEntry object using the arguments provided by the client code. It then performs a brute force search of all the current keys in the array to prevent key duplication. If a duplicate key is found, then the associated MapEntry object is replaced by the new object and its value attribute is returned. For example,

map.put('C', "cow");

Otherwise, the new object is simply added at the “end” of the array, that is, in the first available array slot. For example:

map.put('B', "bat");

Like put, the get, remove, and contains operations would all require brute force searches of the current array contents, so they are all O(N).

A sorted array is the same as an unsorted array except the entries are maintained in sorted order by key. Depending on the implementation details, clients may be required to use Comparable keys or provide a Comparator object. With this approach the binary search algorithm can be used, greatly improving the efficiency of the important get and contains operations. Although it is not a requirement, in general it is expected that a map will provide fast implementation of these two operations.

As with the unsorted array, a brute force search of the linked list is required for most operations. Therefore, there is no time efficiency advantage to using an unsorted linked list as compared to an unsorted array. The put operation, for example, looks much the same as the put operation for the unsorted array. The following figure depicts what happens when a key is reused to put a second value into the map.

When a new key is put into a map, the map still must be searched to make sure there are no duplicates. Then, the new entry is placed in an “easy” location, probably either the front or the rear of the linked list. There is conceivably some benefit to using the front of the array for insertion of a new key/value pair, as for many applications, an entry recently inserted into a map is highly likely to be searched for soon afterward.

In terms of space, a linked list grows and shrinks as needed so it is possible that some advantage can be found in terms of memory management, as compared to an array. Do not forget, however, that a linked list uses an extra memory reference, to hold the link, for each element.

Even though a linked list is kept sorted, it does not permit use of the binary search algorithm as there is no efficient way to inspect the “middle” element. So there is not much advantage to using a sorted linked list to implement a map, as compared to an unsorted linked list. It is possible to make use of the sorted nature of the list to discontinue a search for a given key once a key with a higher value has been encountered. Although helpful, this approach does not provide a faster order of growth efficiency.

If a map can be implemented as a balanced binary search tree, then all of the primary operations (put, get, remove, and contains) can exhibit efficiency O(log₂N). The tree may use the key of each entry for comparison purposes and so, as with the sorted array approach, clients would be required to use Comparable keys or provide a Comparator object. The time efficiency benefits depend on the tree remaining balanced:

We provide an implementation of a map using an ArrayList of MapEntry objects as the internal representation. The ArrayList is unsorted so the analysis above in the subsection “Unsorted Array” applies. This implementation, although not a good example of an efficient approach, does clearly show the relationships among the various operations and the use of the helper class MapEntry.

//---------------------------------------------------------------------------
// ArrayListMap.java          by Dale/Joyce/Weems                   Chapter 8
//
// Implements a map using an ArrayList.
//
// A map provides (K = key, V = value) pairs, mapping the key onto the value.
// Keys are unique. Keys cannot be null.
//
// Methods throw IllegalArgumentException if passed a null key argument.
//

// Values can be null, so a null value returned by put, get, or remove does
// not necessarily mean that an entry did not exist.
//---------------------------------------------------------------------------
package ch08.maps;

import java.util.*;  // Iterator, ArrayList

public class ArrayListMap<K, V>  implements MapInterface<K,V>
{
  protected ArrayList<MapEntry<K, V>> map;

  public ArrayListMap()
  {
    map = new ArrayList<MapEntry<K, V>>();
  }

  public ArrayListMap(int initCapacity)
  {
    map = new ArrayList<MapEntry<K, V>>(initCapacity);
  }

  public V put(K k, V v)
  // If an entry in this map with key k already exists then the value
  // associated with that entry is replaced by value v and the original
  // value is returned; otherwise, adds the (k, v) pair to the map and
  // returns null.
  {
    if (k == null)
      throw new IllegalArgumentException("Maps do not allow null keys.");

    MapEntry<K, V> entry = new MapEntry<K, V>(k, v);

    MapEntry<K,V> temp;
    Iterator<MapEntry<K,V>> search = map.iterator(); // Arraylist iterator
    while (search.hasNext())
    {
      temp = search.next();
      if (temp.getKey().equals(k))
      {
        search.remove();
        map.add(entry);
        return temp.getValue(); // k found, exits method
      }
    }

    // No entry is associated with k.
    map.add(entry);
    return null;
  }

  public V get(K k)
  // If an entry in this map with a key k exists then the value associated
  // with that entry is returned; otherwise null is returned.
  {
    if (k == null)
      throw new IllegalArgumentException("Maps do not allow null keys.");

    for (MapEntry<K,V> temp: map)   // uses ArrayList iterator
      if (temp.getKey().equals(k))
        return temp.getValue();     // k found, exits method

    // No entry is associated with k.
    return null;
  }

  public V remove(K k)
  // If an entry in this map with key k exists then the entry is removed
  // from the map and the value associated with that entry is returned;
  // otherwise null is returned.
  {
    if (k == null)
      throw new IllegalArgumentException("Maps do not allow null keys.");

    MapEntry<K,V> temp;
    Iterator<MapEntry<K,V>> search = map.iterator(); // Arraylist iterator
    while (search.hasNext())
    {
      temp = search.next();
      if (temp.getKey().equals(k))
      {
        search.remove();
        return temp.getValue();    // k found, exits method
      }
    }

    // No entry is associated with k.
    return null;
  }

  public boolean contains(K k)
  // Returns true if an entry in this map with key k exists;
  // Returns false otherwise.
  {
    if (k == null)
      throw new IllegalArgumentException("Maps do not allow null keys.");

    for (MapEntry<K,V> temp: map)
      if (temp.getKey().equals(k))
        return true;     // k found, exits method

    // No entry is associated with k.
    return false;
  }

  public boolean isEmpty()
  // Returns true if this map is empty; otherwise, returns false.
  {
    return (map.size() == 0);   // uses ArrayList size
  }

  public boolean isFull()
  // Returns true if this map is full; otherwise, returns false.
  {
    return false;  // An ArrayListMap is never full
  }

  public int size()
  // Returns the number of entries in this map.
  {
    return map.size();   // uses ArrayList size
  }

  public Iterator<MapEntry<K,V>> iterator()
  // Returns the Iterator provided by ArrayList.
  {
    return map.iterator();  // returns ArrayList iterator
  }
}

A few notes about the implementation:

• Two constructors are provided, one for which the client indicates the original capacity and one that uses the default capacity of an ArrayList, 10, for the original capacity.

• Since an ArrayList is unbounded, our ArrayListMap is unbounded and the isFull method simply returns false.

• Within the code, in order to determine if an entry with a particular key exists, we create an iterator on the ArrayList and walk through it, checking the keys of the map entries. Alternately, if an equals method is defined for our MapEntry class which returns true if two MapEntry objects have the same key attribute, then it is possible to use the contains method of the ArrayList class (which in turn would use the MapEntry equals method). Although this would make the code for our ArrayListMap class simpler, it does not improve efficiency since in either case the ArrayList entries must be traversed.

• For the iterator method we simply return the Iterator provided by the ArrayList class. This same approach could be used by any other implementation approach that uses a wrapped Iterable object as its internal representation of the map.

• Because we also make use of the built-in ArrayList iterator method within our put method implementation, put does not act exactly like the aforementioned put operation for an unsorted array approach. Can you see the difference? If we attempt to put an entry that duplicates a previously entered key, rather than replacing its associated value, we remove the entry altogether (which causes the remaining entries to be shifted) and insert a new entry at the end of the list.

By now you are probably objecting to this scheme on the grounds that it does not guarantee unique array locations for each key. For example, unique ID numbers 01234 and 91234 both “compress” to the same location: 34. This is called a collision. The problem of minimizing such collisions is the biggest challenge in designing a good hashing system and we discuss it in Section 8.5, “Hash Functions.”

Assuming that some collisions occur, where should the entries be stored that cause them? We briefly describe several popular collision-handling algorithms next. Whatever scheme is used to find the place to store an entry will also need to be used when trying to find the entry. The choice of collision-handling algorithm also impacts entry removal options.

In our discussion of collision resolution policies, we will assume use of an array info to hold the information, and the int variable location to indicate an array/hash-table slot.

Linear Probing

A simple scheme for resolving collisions is to store the colliding entry into the next available space. This technique is known as linear probing. In the situation depicted in Figure 8.5, we want to add the employee entry with the key ID number 77003. The compression function returns 03. But there already is an entry stored in this hash table slot, the record for employee 50003. The location is incremented to 04, and the next hash table slot is examined. Because info[04] is also in use, location is incremented again. This time a slot that is empty is found, so the new entry is stored into info[05].

What happens if the last index in the hash table is reached and that space is in use? The hash table can be considered to be a circular structure so searching for an empty slot can continue at the beginning of the table. This approach is similar to our circular array-based queue presented in Chapter 4.

How do we know whether a hash table slot is “empty”? Assuming we have an array of objects, this is easy—just check whether the value of the array slot is null.

To search for an entry in support of the get and contains operations using this collision-handling technique, the compression function is evaluated on the target key, and the result is used to obtain an entry from the table. The target key is compared to the key of the entry from the table. If the keys do not match, linear probing is used, beginning at the next slot in the hash table. Searching continues until either a matching entry is found (a successful search) or a null entry is found (an unsuccessful search).

There is a boundary-case issue or bug with our search approach. If searching for an entry that is not contained in the hash table and the hash table is full, the code will continuously wrap around, fruitlessly searching forever. We can solve this issue by storing the original location returned by the compression function and then discontinuing the search if it returns to that location. In practice this is not an issue—as we will discuss later, most hashing schemes increase the size of the underlying array if their load factor (the percentage of array slots being used) rises above a preset threshold. In that case, the array will never be full and we need not worry about the infinite loop.

Entry Removal

Although we have discussed the insertion and retrieval of entries in the hash table, we have not yet mentioned how to remove an entry. Look at an example. Consider Figure 8.6. Suppose we remove the entry with the key 77003 by setting info[05] to null. A subsequent search for the entry with the key 42504 would begin at info[04]. The entry in this slot is not the one being searched for, so the code next tests info[05]. This slot, which formerly was occupied by the entry that was removed, is now empty (contains null), but the search cannot be terminated—the record being searched for is in the next slot.

Not being able to assume that an empty array slot indicates the end of a linear probe severely undermines the efficiency of this approach. Even when the hash table is sparsely populated, every location must be examined before determining that an entry is not present. Because the primary goal of a hashing approach is to provide fast search, this is not a tenable solution. What else can we do?

One approach is to indicate, with a special reserved value stored in a hash table slot, that the slot once held an entry, but that the entry has been deleted. For example, if we use the value 00000 as the special value, then the hash table in Figure 8.7 shows what the hash table from Figure 8.6 contains after removal of the entry with key 77003.

With this approach, when searching the hash table to support get, contains, or remove, any hash table slot containing the special value is skipped over. The add operation, on the other hand, upon seeing the special value, acts as if it has seen a null and uses the slot for the new entry. After all, the location is available and can be used to hold real information. Note that with this approach, when searching for a key, the code can terminate the search (unsuccessfully) when a null value is encountered. For example, if checking to see if the hash table pictured in Figure 8.7 contains the key 17203, the code would inspect hash table slots 03 (not a match), 04 (not a match), 05 (special value), 06 (not a match), and 07 (null).

For the special value approach to work we must assume that no entry actually uses the value as its key. A similar approach does not suffer from this restriction. If an additional value, for example, a boolean value, is associated with each hash table slot, it can be used to indicate whether or not the slot previously held a value (see Figure 8.8). This is essentially the same as the special value approach except the code checks the boolean value instead of looking for the special value.

Another approach to this issue is to disallow removal of entries. Make remove an illegal operation. Although this may seem like a drastic approach there are many situations where it is not an issue. Collections are often used to store static information for fast retrieval, in which case, the remove operation is not needed.

Quadratic Probing

One problem with linear probing is that it results in a situation called clustering. Suppose keys end up being distributed randomly, resulting in a uniform distribution of used indices throughout the hash table’s index range. Initially, entries are added throughout the hash table, with each slot being equally likely to be filled. Over time, after a number of collisions have been resolved, the distribution of entries in the hash table becomes less and less uniform. The entries tend to cluster together, as multiple keys begin to compete for a single location. This phenomena happens even with a good random distribution of keys. Why?

Consider the hash table in Figure 8.6. Only an entry whose key produces the compression value 08 would be inserted into hash table slot [08]. However, any entries with keys that produce a compression value of 03, 04, 05, 06, or 07 would be inserted into hash table slot [07]. That is, hash table slot [07] is five times more likely than hash table slot [08] to be filled. As soon as there is a collision or two entries otherwise end up beside each other in the hash table, the probability that the two of them viewed as a unit are “hit” is twice as high as any other slot in the hash table. And this probability-driven effect escalates as more entries are added, resulting in clusters of used locations throughout the hash table. Clustering results in inconsistent efficiency of collection operations and makes the use of a load threshold for the underlying array even more important when linear probing is used.

Clustering is a side effect of linear probing. Another collision resolution approach, called quadratic probing, reduces the cluster effect. In linear probing, the code adds the constant value 1 to the location until it finds an open hash table slot. With quadratic probing the value added at each step is dependent on how many locations have already been inspected. The first time it looks for a new location it adds 1 to the original location, the second time it adds 4 to the original location, the third time it adds 9 to the original location, and so on—the ith time it adds i².

Because we jump ahead more and more spaces, each time a “probe” fails to find an available slot, the clustering effect is reduced. The example shown in Figure 8.9 makes the difference clear to see. We must take care with this approach, however, because we could find ourselves in an infinite loop of probes even though there are empty slots in the hash table. We can solve this issue by keeping track of how many probes have been attempted and if the count reaches the size of the hash table, discontinuing our search. Even better we can maintain a load threshold below 50% and use a hash table size that is a prime number. Theorists have proven that the degenerate, infinite loop situation will not occur as long as we meet those conditions.

Buckets and Chaining

Another, perhaps better, alternative for handling collisions is to allow entries to share the same location. One approach lets each computed location contain slots for multiple entries, rather than just a single entry. Each of these multientry locations is called a bucket. Figure 8.10 shows an example with buckets that can contain three entries each. Using this approach, we can allow collisions to produce duplicate entries at the same location, up to a point. When the bucket becomes full, we must again deal with the problem of determining a new location.

Another solution, which avoids this problem, is to store a linked list of entries at each location. Each hash table slot accesses a chain of entries. Figure 8.11 illustrates this approach. The entry in the hash table at each location contains a reference to a linked list of entries.

To search for a given entry, we first apply the compression function to the key and then search the indicated chain for the entry. Searching is not eliminated, but it is limited to entries that actually share a compression value. By contrast, with linear probing we may have to search through many additional entries if the slots following the location are filled with entries from collisions on other locations.

One way to minimize collisions with a hash system is to use an array that has significantly more space than is actually needed for the number of entries, thereby increasing the range of the compression function. This extra space reduces the negative impact of collisions by providing a wide range of target values.

Selecting the array size involves a space versus time trade-off. The larger the range of array indices, the less likely it is that two keys will end up at the same location. However, allocating an array that contains too large a number of empty slots wastes space. In most cases though, we prefer to err on the side of using too much space, because in most cases, space is not an issue.

Hash systems will often monitor their own load—the percentage of array indices being used. Once the load reaches a certain level, for example 75%, the system is rebuilt using a larger array. This approach is similar to the one we used to create unbounded array-based ADTs in previous chapters, although in those cases we only executed the private enlarge method when the underlying structure was full, and in this case we enlarge it preemptively, when it is 75% full, to help ensure efficient operation. This approach is used within the Java Library hash-based classes and is also the approach we use for the map implementation we present in the next section. This approach is often called rehashing because after the array is enlarged all of the previous entries have to be “rehashed”, that is they have to be reinserted into the new array—they cannot just remain in their previous locations.

In the discussion of hashing systems so far we have been assuming that our keys are integral and that when these keys are fed to the compression function the result will be a nice spread of target hash table locations. These assumptions allowed us to concentrate on the processes of a hash system, but it is not difficult to see that neither assumption is well founded:

• Key information might not be integral. For example, it is not unusual for a string to be used as a key—perhaps a person’s full name, the name of a country, a word in a glossary, an identifier in a computer program, a Web URL, and so on.

• Even if the key information within a certain domain is integral, it might not be well suited for use as input to the compression function. Imagine, for example, an encoding system for cities that assigns a nine-digit code to each city in the world, with the first four digits representing a city’s name, the next two digits representing a city’s region, and the last three digits representing the city’s country:

  

  Such a system is capable of assigning unique nine-digit keys to up to 10,000 cities in each of up to 100 regions, in each of up to 1,000 countries. But if you used this key to store information about the cities, in a hash system with an underlying array of size 1,000 that used buckets of linked lists to resolve collisions, you will likely end up with an inefficient system. For example, if your data set consists of 5,000 cities from China your array will consist of 999 empty slots and one slot, slot [038], that holds a 5,000-entry linked list. This is not what we hope for when we decide to use hash-based storage.

The solution to these issues is to add another level of transformation that takes us from key value to the hash table location. This new transformation is provided by a function called the hash function and occurs before applying the compression function. The hash function accepts a key as input and produces an integer as output (in our case, using Java, it produces an int). It does this whether or not the key is integral. The int produced by the hash function is called the hash code for the key, and is passed to the compression function so that the final result represents an index in the target hash table as shown below. Synonyms for “hash code” include “hash value,” and sometimes we just use the word “hash.”

A good hash function minimizes collisions by generating hash codes, which ultimately lead to a uniform spread of entries throughout the hash table. We say “minimizes collisions” because it is extremely difficult to avoid them completely.

So, how do we create a hash function and more importantly, how do we create a good hash function?

Java provides good support for hashing. The Java library includes two important hash-based collection classes—the HashMap, which we discuss in Section 8.7, “Map Variations,” and the HashSet which uses a hash table approach to implementing a set (see Section 5.7, “Collection Variations,” for a definition of the Set ADT). More importantly for the current discussion, the Java Object class exports a hashCode method that returns an int hash code. Because all Java objects ultimately inherit from Object, all Java objects have an associated hash code. Therefore, just as we can assume that all objects in Java support the toString and equals methods, we can assume that all objects support the hashCode method.

Similar to the way the Object class treats equals and toString, the standard Java hashCode for an object is a function of the object’s memory location. As a consequence, it cannot be used to relate separate objects with identical contents. For example, even if circleA and circleB have identical attribute values, it is very unlikely that they have the same hash code. Of course, if circleA and circleB are aliases, if they both reference the same object, then their Object-based hash codes are identical because they hold the same memory reference.

For most applications, hash codes based on memory locations are not useful. Therefore, many of the Java classes that define commonly used objects (such as String and Integer) override the Object class’s hashCode method with one that is based on the contents of the object. Just as we override the Object class’s toString and equals methods when defining a class whose objects may need to support those methods, we should override the hashCode method as necessary. In fact, it is good programming practice to always override the equals and hashCode methods together, if you intend to override either one. It is important that these two methods are consistent with one another.

In Chapter 5 we defined a FamousPerson class. An object of this class has String attributes firstName, lastName, and fact, and an int attribute yearOfBirth. The equals method for this class is based on names only, that is two FamousPerson objects are considered equal if and only if both their first and last names are equal. Any definition of the hashCode method for this class should therefore be based strictly on the first and last name attributes. Here is an example:

@Override
public int hashCode()
// Returns a hash code value for this FamousPerson object.
{
  return Math.abs((lastName.hashCode() * 3) + firstName.hashCode());
}

As you can see, the above method makes use of the predefined hashCode method of the String class. The call to the absolute value method of the Math class ensures that it will return a positive result. Here is an example of what this method returns for a sample of famous people:

Edsger Dijkstra:      1960658654
Grace Hopper:         2019100524
Alan Turing:          1038687573

We began our discussion of hashing by trying to find a collection implementation where the addition, removal, and most importantly, the discovery of entries had a complexity of O(1). If our hash function is efficient and never produces duplicates, and the hash table size is large compared to the expected number of entries in the collection, then we have reached our goal. In general, this is not the case.

Clearly, as the number of entries approaches the array size, the efficiency of the algorithms deteriorates. This is why the load of the hash table is monitored. If the table needs to be resized and the entries all need to be rehashed, a one-time heavy cost is incurred.

A precise analysis of the complexity of hashing depends on the domain and distribution of keys, the hash function, the size of the table, and the collision resolution policy. In practice it is usually not difficult to achieve close to O(1) efficiency using hashing. For any given application area, it is possible to test variations of hashing schemes to see which works best.

Here is the HMap code listing. The listing is followed by some discussion and examples of how to use the HMap.

//---------------------------------------------------------------------------
// HMap.java                by Dale/Joyce/Weems                     Chapter 8
//
// Implements a map using an array-based hash table, linear probing collision
// resolution.
//
// The remove operation is not supported. Invoking it will result in the
// unchecked UnsupportedOperationException being thrown.
//
// A map provides (K = key, V = value) pairs, mapping the key onto the value.

// Keys are unique. Keys cannot be null.
//
// Methods throw IllegalArgumentException if passed a null key argument.
//
// Values can be null, so a null value returned by put or get does
// not necessarily mean that an entry did not exist.
//---------------------------------------------------------------------------
package ch08.maps;

import java.util.Iterator;

public class HMap<K, V> implements MapInterface<K,V>
{
  protected MapEntry[] map;

  protected final int DEFCAP = 1000;     // default capacity
  protected final double DEFLOAD = 0.75; // default load

  protected int origCap;  // original capacity
  protected int currCap;  // current capacity
  protected double load;

  protected int numPairs = 0;    // number of pairs in this map

  public HMap()
  {
    map =  new MapEntry[DEFCAP];
    origCap = DEFCAP;
    currCap = DEFCAP;
    load = DEFLOAD;
  }

  public HMap(int initCap, double initLoad)
  {
    map = new MapEntry[initCap];
    origCap = initCap;
    currCap = initCap;
    load = initLoad;
  }

  private void enlarge()
  // Increments the capacity of the map by an amount
  // equal to the original capacity.

  {
    // create a snapshot iterator of the map and save current size
    Iterator<MapEntry<K,V>> i = iterator();
    int count = numPairs;

    // create the larger array and reset variables
    map = new MapEntry[currCap + origCap];
    currCap = currCap + origCap;
    numPairs = 0;

    // put the contents of the current map into the larger array
    MapEntry entry;
    for (int n = 1; n <= count; n++)
    {
      entry = i.next();
      this.put((K)entry.getKey(), (V)entry.getValue());
    }
  }

  public V put(K k, V v)
  // If an entry in this map with key k already exists then the value
  // associated with that entry is replaced by value v and the original
  // value is returned; otherwise, adds the (k, v) pair to the map and
  // returns null.
  {
    if (k == null)
      throw new IllegalArgumentException("Maps do not allow null keys.");

    MapEntry<K, V> entry = new MapEntry<K, V>(k, v);

    int location = Math.abs(k.hashCode()) % currCap;
    while ((map[location] != null) && !(map[location].getKey().equals(k)))
      location = (location + 1) % currCap;

    if (map[location] == null)  // k was not in map
    {
      map[location] = entry;
      numPairs++;
      if ((float)numPairs/currCap > load)
        enlarge();
      return null;
    }
    else    // k already in map

     {
       V temp = (V)map[location].getValue();
       map[location] = entry;
       return temp;
     }
  }

  public V get(K k)
  // If an entry in this map with a key k exists then the value associated
  // with that entry is returned; otherwise null is returned.
  {
     if (k == null)
       throw new IllegalArgumentException("Maps do not allow null keys.");

    int location = Math.abs(k.hashCode()) % currCap;
    while ((map[location] != null) && !(map[location].getKey().equals(k)))
      location = (location + 1) % currCap;

    if (map[location] == null)  // k was not in map
      return null;
    else                        // k in map
      return (V)map[location].getValue();
  }

  public V remove(K k)
  // Throws UnsupportedOperationException.
  {
     throw new UnsupportedOperationException("HMap does not allow remove.");
  }

  public boolean contains(K k)
  // Returns true if an entry in this map with key k exists;
  // Returns false otherwise.
  {
    if (k == null)
      throw new IllegalArgumentException("Maps do not allow null keys.");

    int location = Math.abs(k.hashCode()) % currCap;
    while (map[location] != null)
      if (map[location].getKey().equals(k))
        return true;
      else
        location = (location + 1) % currCap;

     // if get this far then no current entry is associated with k
     return false;
  }

  public boolean isEmpty()
  // Returns true if this map is empty; otherwise, returns false.
  {
    return (numPairs == 0);
  }

  public boolean isFull()
  // Returns true if this map is full; otherwise, returns false.
  {
    return false;  // An HMap is never full
  }

  public int size()
  // Returns the number of entries in this map.
  {
    return numPairs;
  }

  private class MapIterator implements Iterator<MapEntry<K,V>>
  // Provides a snapshot Iterator over this map.
  // Remove is not supported and throws UnsupportedOperationException.
  {
    int listSize = size();
    private MapEntry[] list = new MapEntry[listSize];
    private int previousPos = -1; // previous position returned from list

    public MapIterator()
    {
      int next = -1;
      for (int i = 0; i < listSize; i++)
      {
        next++;
        while (map[next] == null)
          next++;
        list[i] = map[next];
      }
    }

    public boolean hasNext()

     // Returns true if iteration has more entries; otherwise returns false.
     {
       return (previousPos < (listSize - 1));
     }

     public MapEntry<K,V> next()
     // Returns the next entry in the iteration.
     // Throws NoSuchElementException - if the iteration has no more entries
     {
       if (!hasNext())
         throw new IndexOutOfBoundsException("illegal invocation of next " +
                            " in HMap iterator.
");
       previousPos++;
       return list[previousPos];
     }

     public void remove()
     // Throws UnsupportedOperationException.
     // Not supported. Removal from snapshot iteration is meaningless.
     {
       throw new UnsupportedOperationException("Unsupported remove attempted "
                                             + "on HMap iterator.
");
     }
  }

  public Iterator<MapEntry<K,V>> iterator()
  // Returns a snapshot Iterator over this map.
  // Remove is not supported and throws UnsupportedOperationException.
  {
    return new MapIterator();
  }
}

The three operations (put, get, and contains) that must determine if the map holds a given key k, all follow the same general pattern exemplified by the following code:

int location = Math.abs(k.hashCode()) % currCap;
while ((map[location] != null) && !(map[location].getKey().equals(k)))
   location = (location + 1) % currCap;

First, location is set using the hashCode method of the key class. Then linear probing is used until either an empty array slot is found (one where map[location] == null) or a MapEntry object with key k is found (note that we make use of the short-circuit property of the Java && operation to protect ourselves from using a null reference). If the object with key k is found then the appropriate action takes place— replacement for the put operation, return for the get operation, and return true for the contains operation. Otherwise, in the case of a location containing null being found, again the appropriate action takes place—insertion for the put operation, return null for the get operation, and return false for the contains operation.

The private enlarge method deserves some discussion. Because put is the only way to add information to the map it is the only place where enlarge is invoked:

if (map[location] == null)  // k was not in map
{
  map[location] = entry;
  numPairs++;
  if ((float)numPairs/currCap > load)
    enlarge();
  return null;
}

The enlarge method first stores all of the current entries of the map by creating an Iterator. It then instantiates a new array of MapEntry objects of the appropriate size. Finally, it “walks through” the saved Iterator, adding each of the MapEntry objects into the new array using the put operation. The put operation spreads the entries across the newly enlarged array.

Overall, enlarge is a costly operation, especially if an expensive hash function is in use. Although enlarge only executes on a rare basis and we can amortize its cost across the large number of put operations that must precede its invocation, the actual cost does all occur at once. If you are designing a system where consistent rapid response is a requirement you need to be aware of this and consider how you can originally allocate enough space to your hash table to avoid the use of enlarge.

Finally, we should note why we did not use an anonymous inner class to provide the required Iterator object that is returned by the iterator method, as we have done for previous ADT implementations. For the hash table–based map, our approach to iteration is to search through the entire underlying map array, creating a new array, list, that holds references to only the non-null entries. In other words, the list array will hold a “snapshot” of the MapEntry entries that have been stored so far, without all of the intervening null entries.

The list array is then used to provide the hasNext and next operations. The remove operation is not supported. In any case, in order to set up the list array we need to perform some initial processing, when the Iterator object is created. This processing must take place in a constructor. But constructors are not supported by anonymous classes— after all, an anonymous class does not have a name, so there is no way to “name” the constructor. Thus, we use a “regular” inner class in this case to support iteration.

We can use the HMap class in the same way we used our ArrayListMap class. For example, to use the HMap class to support the StringPairApp application presented in Section 8.3, “Application: String-to-String Map,” all we need to do is change the line

MapInterface<String, String> pairs = new ArrayListMap<String, String>();

to

MapInterface<String, String> pairs = new HMap<String, String>();

It might be interesting to see how HMap performs on the Text Analysis experiment we used in both Chapter 5, “The Collection ADT,” and Chapter 7, “The Binary Search Tree ADT.” You may recall that our application, VocabularyDensity, reads a given text file and computes the ratio of its number of unique words to total number of words. We used the application to analyze a collection of texts including, among others, the Complete Works of Shakespeare and an edition of the Encyclopaeda Brittanica. Perhaps the most interesting text file analyzed was one we called “Mashup,” which consisted of a concatenation of 121 files from the Gutenberg site including novels, “complete works,” dictionaries, and technical manuals, plus Spanish, French, and German language texts in addition to the English. What happens if we “hash the mash”?

The VocDensMeasureHMap application can be found in package ch08.apps. As before, the application reads through the words from the input text, checking each word to see whether or not it already exists in the map. If not, the word is added, and if so, the word is skipped. In either case we increment the number of total words. When finished we simply divide the number of words in the map by the total number of words. Because we are only interested in the words themselves, which are used as the keys, we use null values when putting information into the map. We set the initial capacity to 2,404,198, which is exactly twice the number of unique words in the mashup.txt file. How do the results compare to previous attempts, in terms of execution time? (Times are approximate):

• Unsorted Array: 10 hours

• Sorted Array (uses binary search): 7 minutes, 10 seconds

• Binary Search Tree: 100 seconds

• Hash Map: 66 seconds

Well, that is a little disappointing although requiring 66% of the time needed by the binary search tree is some improvement. But wait—there is quite a bit of overhead associated with just reading the input file word by word. Experimentation shows that the cost of this activity, which is unavoidable for our application yet is not directly related to the storage/retrieval mechanism, is approximately 51 seconds. We can relist our last two results, subtracting out this overhead cost, and get (approximately):

• Binary Search Tree: 50 seconds

• Hash Map: 15 seconds

Now we can state that the hash map approach only takes about 30% of the time of the binary search tree result, a more satisfying result.

We have seen how a hash table, under the right conditions, supports fast storage and retrieval of information. Suppose we have a situation where we need fast storage and retrieval, but we also need to be able to iterate through the stored entries in the order in which they were placed into the collection. The only structures that we have studied so far that support such an iteration are the unsorted array (assuming the remove operation is implemented carefully) and the unsorted linked list (assuming we insert entries at the end of the list)—but neither of these provide efficient storage and retrieval. They are both O(N) for these operations.

Is there some way we could use a hash table to solve our problem?

The problem is that a hash table spreads things all across the underlying array in no particular order. Suppose we create a map with the following declaration:

HMap<Character, String> animals = new HMap<Character, String>;

and then execute:

animals.put('A', "ant"); animals.put('B', "bat"); animals.put('C', "cat");

The result might look something like this:

As you can see, the entries are spread around and there is no way to recapture the original order of insertion. If we expand the contents of the internal data to hold a count of how many entries have been entered so far, and associate the value of that count with each entry as it is stored in the array, then at least we have saved the order of insertion for later use. The result might look like this:

Now at least we have captured the entry order information and can, with a bit of work, create the desired iteration. To do this we need to look through the entire internal array, find the entries, and then sort them in increasing order of entry. Seems like a lot of work to reclaim information that was already available to us. Is there a better way?

What if we maintain a second internal array named list, with references into the map array, kept in the desired order:

Now we are getting somewhere. The hashing scheme works as before so this approach supports fast storage and retrieval, and when we need to iterate on insertion order we can just use values from the list array to access the entries in the map array in the desired sequence.

But what happens when an entry is removed? Maintaining the information correctly after a remove operation is going to be difficult and costly. When the remove operation is invoked it is not difficult to find the entry in the map array—we just use the hash function and collision resolution approach. Once the entry is found the contents of the map array at that index can be set to null. But the list array also needs to be updated. Because there is no link back to the list array from map, we need to search the list array to find the correct location to update—and once found in order to remove the information at that location we need to shift all remaining entries to the “left” one slot. So, if we use this approach we have transformed remove from an expected efficiency of O(1) to a best case efficiency of O(N). For some systems this might be too high a cost.

Let us try one more time. We need a support structure that supports fast addition. We need to be able to iterate through the entries in the order in which they are inserted into the map. And we need a reasonably quick remove operation. A doubly linked list (see Section 4.7, “Queue Variations”) supports fast removal. If we embed the list within the map entries themselves then we have the desired relationship between the map entries and the list elements.

The result might look something like this:

Although the figure looks complex, this approach meets our requirements. It is a hash table–based map with an embedded doubly linked list. This is very similar by the way, to a Java Library class—the LinkedHashMap.

The Java Library includes a Map interface. Like our maps, the maps in the library use two generic parameters—K for the types of keys and V for the types of values. A nested class, Entry, fulfills the role of our MapEntry class. The interface, being a part of a professional API, is more complex than our MapInterface. It defines 25 abstract methods, has eight subinterfaces, and is implemented by 19 classes within the library. Nevertheless, in terms of its core functionality, it is equivalent to our map interface.

Of the 19 implementing classes, of special note to us is the HashMap class. The HashMap class permits null keys. Other than that it is very similar to our HMap class (or perhaps we should state that the other way around—our HMap class is similar to the library class!). HashMap provides both a default capacity and load factor, and allows the client to set these through a constructor if they wish, just like our HMap. And like our HMap, assuming a reasonably well-behaved hash function and distribution of keys, HashMap provides constant time storage, removal, and retrieval. The library’s hash map provides more operations than our version does; in fact it implements 24 operations in addition to the 12 it inherits from its ancestors. Professional Java programmers typically make heavy use of the HashMap class to support their work.