Hashbased Maps

Background

In this assignment, will practice applying our knowledge of ADTs, maps, and hashing, to implement a pair of map ADTs which use relatively standard hashing techniques. Most likely, these will be the most conceptually complicated data types you have built. Provided for you is ChainMap: a sample implementation of a chaining approach to implementing a hash-based map. This ?le is similar to what is seen in the slides, but is more comprehensive and follows a Map interface. We will be implementing two techniques for hash-based maps:

TwoProbeChainMap: This technique is similar to the list chaining method that is covered in the slides and Appendix E. In a normal chaining approach, keys hash to exactly one index and the key/value pair must reside in the list at that particular index. In this new approach, we will instead calculate two hashes, that indicate two di?erent indices, and then add the new key/value to whichever of two lists, at the two indices, is the shortest. The result is that the chains (lists) will end up being shorter in general since we split in half where the key/value pairs are placed.

LinearProbingMap: This technique is covered in the text and slides under open addressing. The idea is that we hash to a speci?c index in the internal array. If the index is empty, we add the key/value pair to it. If occupied, we increment the index by 1 and try again. This repeats until an empty index is found.

Sample UML for these classes is shown in Figure 1. This is provided only as a hint. Your requirement is to follow the interface speci?cation, not the UML.

Figure 1: Sample Map Implementations UML see image.

This document is separated into four sections: Background, Requirements, Testing, and Submission. You have almost ?nished reading the Background section already. In Requirements, we will discuss what is ex- pected of you in this homework. In Testing, we give some basic suggestions on how the map implementations can be tested. Lastly, Submission discusses how your source code should be submitted on BlackBoard.

Requirements

In this assignment you will implement two types of hash-based maps. Download the attached Driver.java, Map.java. The ?rst ?le de?nes some tests for maps, the second is the map interface. Also included is ChainMap.java, which contains a sample implementation of a chaining hash-based map.

Write a class called TwoProbeChainMap that implements a two-probe chaining hash-based map. Two- probe hashing means that you will hash to two positions, and insert the key in the shorter of the two chains at those two positions. The easiest way to implement this class is to spend some time understanding ChainMap, and then redesign it to use the two probe technique.

• Proper hash calculations.
  • For the first hash function, use: hash(k)=(k.hashCode() & 0x7???f) % M.
  • For the second hash function, use: hash2(k)= (((k.hashCode() & 0x7???f) % M) * 31) % M.
• void put(Key key, Value val) - see interface.
• Value get(Key key) - see interface.
• void remove(Key key) - see interface.

Write a class called LinearProbingMap that implements a linear probe hash-based map.

• Proper hash calculations.
  • An decent way to structure the hash function is: hash(k, i) = ((k.hashCode() & 0x7???f) + i) % M, where k is the key and i is the number of collisions. Each time there is a collision, i should be incremented so that the hash increases by 1. An example hash sequence might look like: 587, 588, 589, 590, 581...
• LinearProbingMap() - a constructor that defaults to an array of size 997 .
• void put(Key key, Value val) - see interface.
• Value get(Key key) - see interface.
• void remove(Key key) - see interface.
• boolean contains(Key key) - see interface.
• boolean isEmpty() - see interface.
• int size() - see interface.
• Iterable< Key> keys() - see interface.
• There is no requirement to support array resizing.

Both classes must implement the provided Map interface.

Do not import any packages other than Queue or LinkedList in your map implementations.

No testing report is required this time - test as much or as little as it takes to convince yourself that the implementations work.

Testing

The provided driver ?le already contains several tests for the operations in the interface. Out of the box, the ChainMap implementation should pass these tests. Note that the tests require assertions to be enabled. The tests are designed to check not only the interface operations in isolation, but how they interact with each other. For example, they check that certain properties of the map are invariant over the operations. An invariant is something that does not change. Like the size of the ADT before and after checking if an element is contained. Figure 2 shows the expected output from the driver, once the two classes (TwoProbeChainMap, and LinearProbingMap) have been implemented. Initially, the driver won't compile since it depends on those two classes. Be aware that while a considerable number of operations are tested, what is provided is not comprehensive. For example, all tests use the String data type and do not check how well the ADT functions with other types (e.g., Integer, Double, a custom class, etc).

For this assignment, there is no testing write up required. However, you may want to do your own testing to verify the completeness of your implementation.

Figure 2: Tree UML Overview see image.