Assignment #5 - Maps

Objectives:

The main objectives of this assignment are:
• Continue to analyze data structures using @TimeComplexity annotations.
• Build more advanced data structures.
• Practice reusing code to save time and energy.
• Provide you with a data structure implemented three different ways which can be used later in the semester.
• Develop test cases to verify your own code.

The Assignment:

The Concept:

Write a Unordered Map, a Lookup Table, a Hash Table and a multimap. The first three does not allow duplicate keys. The put(k,v) method replace the value if k exists, otherwise it will insert. The multimap supports entries with duplicate keys.
• Unordered Map - Use ArrayList or DoublyLinkedList to store the data. Data in the list is unordered.
• LookupTable - Use ArrayList to store the data. Data in the array is ordered, binary search should be used to find a entry.
• HashTable - Use an array of Unordered Map to store the data. Pretty good at both insert and search. For this lab, use chaining method for collision-handling.
• Multimap - Allow multiple entries to have the same key. The multimap can be implemented based on the HashTable. In HashTable, each key has one value. For multimap, each key is associated with a list of values. Therefore a multimap can be viewed as a HashTable.

Your Job:

Code up a unsorted map, sorted map, a hash table, and a multimap.  You may use code from your previous assignments to complete these. You will be responsible for testing the code yourself, instead of being given a test platform.

Again, this assignment does not depends on previous assignments directly, but you will find some similar code from previous assignments that can be copy-pasted.

Getting Started (and Getting Finished):

1. Download and import the following zip file: Assignment5.zip. For Eclipse:
   1. Open Eclipse
   2. Choose "File → Import"
   3. Select the "General" category
   4. Pick "Existing Projects into Workspace"
   5. Click on "Next"
   6. Select the button for "Select Archive File" and browse to/select the zip file.
   7. Click on "Finish"
   8. A new project SimpleMap has been added to the workspace


2. The major files in the project SimpleMap
   1. UnorderedMap.java - you need to implement this MAP ADT.
   2. LookupTable.java - you need to implement this SortedMAP ADT.
   3. HashMap.java - you need to implement this MAP ADT.
   4. HashMultiMap.java - you need to implement this MAP that support entries with duplicate keys.


3. Complete the UnorderedMap by using ArrayList or DoublyLinked List.


4. Complete the LookupTable by using ArrayList


5. Complete the HashMap by using ArrayList instantiated with a fixed size - the size of your hash table. Finish UnorderedMap first before you start this one.


1. You can use either Division method or MAD method to create the hash value.
2. Use the chaining scheme to handle collision.
3. Each element in the ArrayList is an Unordered map.


6. Complete the HashMultiMap by using allowing multiple entries have the same keys. Finish the HashMap first before you work on this one.

Submission:

First, look at the following checklist:
1. Does the program compile on CS machines? (Programs that don't compile for us will not be graded)
2. Do not ever import from java.util. If so, be sure you only import allowed components (like Iterator, Exceptions, etc.). Unless the assignment specifically mentions it is permissible, you should never include any of java's native data structures.
3. Does the program meet all required interfaces?
4. Do all your methods have a @TimeComplexity indicator?
5. If any methods have a good amortized or expected cost, do they have both the @TimeComplexity and either @TimeComplexityAmortized or @TimeComplexityExpected
6. Do you provide adequate TCJ comments to prove your time complexity?
7. Is the indentation easily readable? You can have Eclipse correct indentation by highlighting all code and select "Source → Correct Indentation".
8. Have you removed any of the "cs2321" comments (/*#) that you may have accidentally copy/pasted?
9. Are comments well organized and concise?
If you have reviewed your code and all the criteria on the checklist are acceptable, follow the submission procedure.

Grading Criteria:

• An UnorderedMap,LookupTable, HashMap, andHashMultiMap using the code given, correctly implementing all methods and interfaces: 80 (20 points each)
• Correct documentation of time complexity: 10
• Clear concise code with good commenting: 10
• Getting program done early: 0 points, but you feel good about yourself

FAQ

• How to get hash code of any object? Use Math.abs(object.hashcode()).