Computer Engineering Homework 5 Solution

PART 1 - 40 pts:

Write a custom iterator class MapIterator to iterate through the keys in a HashMap data structure in

Java. This class should have the following methods:

    • next(): The function returns the next key in the Map. It returns the first key when there is no not-iterated key in the Map.

    • prev(): The iterator points to the previous key in the Map. It returns the last key when the iterator is at the first key.

    • hasNext(): The method returns True if there are still not-iterated key/s in the Map, otherwise returns False.

    • MapIterator (K key): The iterator should start from the given key and still iterate though all the keys in the Map. The iterator starts from any key in the Map when the starting key is not in the Map or not specified (zero parameter constructor).



PART 2 – 60 pts:

Implement KWHashMap interface in the book using the following hashing methods to organize hash table:

    • Use the chaining technique for hashing by using linked lists (available in the text book) to chain items on the same table slot.

    • Use the chaining technique for hashing by using TreeSet (instead of linked list) to chain items on the same table slot.

    • Use the Coalesced hashing technique. This technique uses the concept of Open Addressing to find first empty place for colliding element by using the quadratic probing and the concept of Separate Chaining to link the colliding elements to each other through pointers (indices in the table). The deletion of a key is performed by linking its next entry to the entry that points the deleted key by replacing deleted entry by the next entry. See the following illustration as an example:

Input = {3, 12, 13, 25, 23, 51, 42}

Hash function = data % 10
Insert 3:



insert 12:


insert 13:












Hash
Key
Next

Hash
Key
Next

Hash
Key
Next
Value



Value



Value













0

NULL

0

NULL

0

NULL











1

NULL

1

NULL

1

NULL











2

NULL

2
12
NULL

2
12
NULL











3
3
NULL

3
3
NULL

3
3
4











4

NULL

4

NULL

4
13
NULL











5

NULL

5

NULL

5

NULL











6

NULL

6

NULL

6

NULL











7

NULL

7

NULL

7

NULL











8

NULL

8

NULL

8

NULL











9

NULL

9

NULL

9

NULL











Insert 25:



insert 23:


insert 51:












Hash
Key
Next

Hash
Key
Next

Hash
Key
Next
Value



Value



Value













0

NULL

0

NULL

0

NULL











1

NULL

1

NULL

1
51
NULL











2
12
NULL

2
12
NULL

2
12
NULL











3
3
4

3
3
4

3
3
4











4
13
NULL

4
13
7

4
13
7











5
25
NULL

5
25
NULL

5
25
NULL











6

NULL

6

NULL

6

NULL











7

NULL

7
23
NULL

7
23
NULL











8

NULL

8

NULL

8

NULL











9

NULL

9

NULL

9

NULL












Insert 42:

Hash
Key
Next

Value







0

NULL





1
51
NULL





2
12
6





3
3
4





4
13
7





5
25
NULL





6
42
NULL





7
23
NULL





8

NULL





9

NULL





Delete 13:







Hash
Key
Next

Value







0

NULL





1
51
NULL





2
12
6





3
3
4





4
23
NULL





5
25
NULL





6
42
NULL





7

NULL





8

NULL





9

NULL








Test all the three hash table implementations empirically. Use small, medium, and large-sized data and hash tables in suitable sizes for testing. Perform different tasks over the tables to compare their performance results (like accessing existing/non-existing items or adding/removing items).
RESTRICTIONS:

    • Can be only one main class in project

    • Don’t use any other third part library

GENERAL RULES:

    • For any question firstly use course news forum in Moodle, and then the contact TA.

    • You can submit assignment one day late and will be evaluated over sixty percent (%60).

TECHNICAL RULES:

    • You must write a driver function that demonstrates all possible actions in your homework. For example, if you are asked to implement an array list and perform an iterative search on the list then, you must at least provide the following in the driver function:

o Create an array list and add items to the list. Append items to head, tail, and kth index of the list.

o Perform at least two different searches by using two items in the list and print the index of the items.

o Perform another search with an item that isn’t in the array list and inform the user that the item doesn’t exist in the array list.

o  Delete an existing item from the list and repeat the searches.

o Try to delete an item that is not on the array list and throw an exception for this situation.

The driver function should run when the code file is executed.

    • Implement clean code standards in your code;

    o Classes, methods and variables names must be meaningful and related with the functionality.

    o Your functions and classes must be simple, general, reusable and focus on one topic. o Use standard java code name conventions.

REPORT RULES:

    • Add all javadoc documentations for classes, methods, variables …etc. All explanation must be meaningful and understandable.

    • You should submit your homework code, Javadoc and report to Moodle in a “studentid_hw5.tar.gz” file.

    • Use the given homework format including selected parts from the table below:


Detailed system requirements

The Project use case diagrams (extra points)

Class diagrams

Other diagrams

Problem solutions approach
X


Test cases

Running command and results




GRADING :

-
No OOP design:
-100
-
No interface:
-95
-
No method overriding:
-95
-
No error handling:
-50
-
No inheritance:
-95
-
No polymorphism:
-95
-
No javadoc documentation:
-50
-
No report:
-90
-
Disobey restrictions:
-100
-
Cheating:
-200

X

X

    • Your solution is evaluated over 100 as your performance.

CONTACT:

    • Teaching Assistant: Mehmet Burak Koca

    • b.koca@gtu.edu.tr