CSE222-Homework 5 Solved

PART 1 

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 

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 Value
Key
Next
Hash Value
Key
Next
Hash Value
Key
Next
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 Value
Key
Next
Hash Value
Key
Next
Hash Value
Key
Next
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 Value
Key
Next
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 Value
Key
Next
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).