CHC5223 Data Structures and Algorithms Assignment 1: Hash Table
CHC5223 Data Structures and Algorithms 2022–2023 Semester 2 Assignment 1 Value 35% of Coursework Individual work Learning outcomes Students will be able to understand 1.1 Data structures 1.2 The applications of data structures 1.3 Object-oriented programming concepts 1.4 Methods for program testing Students will have acquired skills in: 2.1 Data abstraction 2.2 The use of data structures 2.3 Programming at a more advanced level in a high-level object-oriented language 2.4 Program testing and documentation Students will have acquired skills in: 3.1 Self-management 3.2 Learning 3.3 Communication 3.4 Problem solving 3.5 Information technology Process and what submit to Student Website The assignment submitted should be compressed into a .zip file, the following files should be contained in the compressed file: • a report as a Microsoft Word document containing the text of all your classes. filename format: 12345678_CHC5223_CW1_Report.docx • a .zip file containing the project: the runnable jar file (if available) and all the program’s source texts (.java), including those provided filename format: 12345678CHC5223 CW1_Files.zip General requirements All your programming must conform to “Java Conventions and Programming Guidelines” You must paste the source code of all your classes into your report, as text, not images. Introduction The topic of this assignment is hash table. This assignment requires you to implement two Java classes (one is provided as a general framework in Appendixes). The class LinearProbingHashTable is structured by methods for implementing a hash table based on an array and should achieve collision resolution by using linear probing way. The class ChainingHashTable should be structured for implementing a hash table based on an array which should achieve collision resolution by using the chaining way. You must implement LinearProbingHashTable as a hash table for Assignment 1. You must implement ChainingHashTable as a hash table for Assignment 1. 1 of 9
CHC5223 Data Structures and Algorithms 2022–2023 Semester 2 Requirements Task 1 You must create one project in the developing environment based on the codes provided in the appendix. One Java class should be defined in the .java file respectively. Task 2 2 marks You must complete the class LinearProbingHashTable based on the codes provided in the appendix. You must use a Java array for implementing the hash table (not an array list or other collection class). You must not encapsulate existing implementations of collections in your submission. Failure to comply with this will result in zero marks for this part. You must complete the constructor and the methods set already in the provided codes for this class. Include explanations of your implementations of these methods in your report. 6 marks Task 3 You must devise your own hash function that will work well for strings. You must not use the Java built-in hashCode method, though you can experiment with it. You will need to perform some experiments to devise one hash function which is easy to lead to collisions and devise one hash function which can cater to the collision for well. Design examples for the hash functions you devised and contrast the results. Indicate and analyze the results brought by different hash functions in your report. Make an explanation of your collision- resolution strategy and your experiments in your report. Tip: Take care to avoid numeric overflow when calculating your hash function. This can be done by applying a mod (%) operation at the early stages of the calculation, rather than just at the end. 4 marks Task 4 You must create the class ChainingHashTable which is implemented as a hash table based on an array and achieves the collision resolution by using the changing way. You must use a Java array for implementing the hash table (not an array list or other collection class). You must not encapsulate existing implementations of collections in your submission. Failure to comply with this will result in zero marks for this part. The class ChainingHashTable should contain methods similar to those specified in the class LinearProbingHashTable. Tip: You need to consider how to implement a chain structure based on a Java array where each node contains a string. You need to make a linear search within the chain. 8 marks Make an explanation of your collision resolution strategy, a reflection of your encoding work on achieving the chaining way, and your experiments in your report. 5 marks 2 of 9
CHC5223 Data Structures and Algorithms 2022–2023 Semester 2 Task 5 You must modify the provided main program to make it applicable to the objects of both the class LinearProbingHashTable and the class ChainingHashTable. 2 marks Task 6 Your class must keep track of the ‘load factor’ of the hash table and display this after each insertion or deletion. Note that with chaining the load factor can exceed 100%. 2 marks Task 7 There are some potential risks/bugs in the provided codes, you should try your best to find out and fix them. Make explanations of the reasons for the risks/bugs generated and your experiments of fixing in your report. 4 marks Task 8 You must state honestly which of the requirements of Assignment 1 you have successfully fulfilled, citing evidence. Also, comment on the time efficiency and space efficiency of your implementation of the hash table. 2 marks total 35 marks Relevant quotation “There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.” Professor Sir Tony Hoare 1980 Turing Award Lecture; Communications of the ACM 24 (2), (February 1981): pp. 75-83 Please try to do this the first way. Obtaining help It is always permissible to request advice on what is required for this assignment. Please try to do this during normal contact time and avoid asking for such help in the last week before the deadline. You can discuss the requirements and the material covered in the assignment with others but what you create must be all your own work. Be careful to avoid collusion. Declare in your report any help you have received other than that from the module teaching team. 3 of 9
CHC5223 Data Structures and Algorithms 2022–2023 Semester 2 Feedback In addition to the written feedback that we aim to provide within the normal interval, you will be able to obtain fast, brief, verbal formative feedback and help on correcting your work at your practical classes. 4 of 9
CHC5223 Data Structures and Algorithms 2022–2023 Semester 2 Appendix 1: // menu is popped to user to perform desired action import java.util.Scanner; public class chc5223test { // Main driver method public static void main(String[] args) { // Creating a scanner object // to take input from user Scanner scan = new Scanner(System.in); // Display messages System.out.println("Hash Table Test"); System.out.println("Enter size"); // maxSizeake object of LinearProbingHashTable LinearProbingHashTable lpht = new LinearProbingHashTable(scan.nextInt()); char ch; // Do-while loop // Do part for performing actions Do // Menu is displayed // LinearProbingHashTable operations performed as // per keys Users enter 'y' to continue 'n' if // entered by user , the program terminates { // Menu // Display messages System.out.println("\nHash Table Operations"); System.out.println("1. insert "); System.out.println("2. remove"); System.out.println("3. get"); System.out.println("4. clear"); System.out.println("5. size"); // Reading integer using nextInt() int choice = scan.nextInt(); // Switch case switch (choice) { // Case 1 case 1: // Display message System.out.println("Enter value"); lpht.insert(scan.next()); 5 of 9
CHC5223 Data Structures and Algorithms 2022–2023 Semester 2 // Break statement to terminate a case break; // Case 2 case 2: // Display message System.out.println("Enter value"); lpht.remove(scan.next()); // Break statement to terminate a case break; // Case 3 case 3: // Print statements System.out.println("Enter key"); System.out.println("Value = "
- lpht.get(scan.next())); // Break statement to terminate a case break; // Case 4 case 4: lpht.makeEmpty(); // Print statement System.out.println("Hash Table Cleared\n"); // Break statement to terminate a case break; // Case 5 case 5: // Print statement System.out.println("Size = "
- lpht.getSize()); break; // Default case // Executed when mentioned switch cases are not // matched default: // Print statement System.out.println("Wrong Entry \n "); // Break statement break; } // Display hash table 6 of 9
CHC5223 Data Structures and Algorithms 2022–2023 Semester 2 lpht.printHashTable(); // Display message asking the user whether // he/she wants to continue System.out.println( "Do you want to continue (Type y or n)"); // Reading character using charAt() method to // fetch ch = scan.next().charAt(0); } while (ch == 'Y' || ch == 'y'); } } 7 of 9
CHC5223 Data Structures and Algorithms 2022–2023 Semester 2 Appendix 2: // Java Program to Implement Hash Tables with Linear Probing //class - LinearProbingHashTable class LinearProbingHashTable { // Member variables of this class // Constructor of this class public LinearProbingHashTable(int capacity) { } // Method 1 // Function to clear hash table public void makeEmpty() { } // Method 2 // Function to get the size of the hash table public int getSize() { } // Method 3 // Function to check if the hash table is full public boolean isFull() { } // Method 4 // Function to check if the hash table is empty public boolean isEmpty() { } // Method 5 // Function to check if the hash table contains a value public boolean contains(String value) { } // Method 6 // Function to get the hash code of a given string 8 of 9
CHC5223 Data Structures and Algorithms 2022–2023 Semester 2 private int hash(String value) { } // Method 7 // Function to insert value public void insert(String value) { } // Method 8 // Function to get value for the given key public String get( key ) { } // Method 9 // Function to remove the value public void remove(String value) { } // Method 10 // Function to print the whole HashTable public void printHashTable() { } } 9 of 9
