Follow the strategy described in section 15.4 to implement the Hash Map class, as you know it from Chapter 5.

Write hash Code functions for each of the primitive types.

Although the bucket-chaining approach described in the text works well in practice, other strategies exist for resolving collisions in hash tables. In the early days of computingwhen memories were small enough that the cost of introducing extra pointers was taken seriouslyhash tables often used a more memory-efficient strategy called open addressing, in which the key-value pairs are stored directly in the array, like this:

For example, if a key hashes to bucket #2, the open-addressing strategy tries to put that key and its value directly into the entry at array[2]. The problem with this approach is that array[3] may already be assigned to another key that hashes to the same bucket. The simplest approach to dealing with collisions of this sort is to store each new key in the first free cell at or after its expected hash position. Thus, if a key hashes to bucket #2, the put and get functions first try to find or insert that key in array [2]. If that entry is filled with a different key, however, these functions move on to try array[3], continuing the process until they find an empty entry or an entry with a matching key. As in the ring-buffer implementation of queues in Chapter 14, if the index advances past the end of the array, it should wrap around back to the beginning. This strategy for resolving collisions is called linear probing. Re-implement the String Map class so that it uses open addressing with linear probing. For this exercise, your implementation should simply signal an error if the client tries to add a key to a hash table that is already full.