讲解：CSCI 2110、Data Structures、Java、JavaR|Matlab

CSCI 2110 Data Structures and AlgorithmsAssignment N0. 4Assigned: Wednesday 20 NovemberDue: Wednesday 27 November23h55 (5 minutes to midnight)HashingThis assignment is designed to help you get familiar with hashing and Java’s HashMap.ReviewA hash table can be implemented as a simple array structure. When a key needs to be mapped to thehash table, a hash function is used to determine the index at which it should be stored. A commonhash function is:key % table sizeIf the table size is 10, then the keys 1008, 2540, 3467, and 789, would be mapped to locations 8, 0, 7and 9, respectively.It is possible for several keys may map to the same location. Using the simple function provided, thekeys 3467 and 2487 would both map to location 7. This is described as a hash collision. One way ofresolving these collisions is called separate chaining. Rather than storing the keys in the array, eacharray location contains a reference to a linked list. Keys are stored in the linked lists.If the table size is 10, then the keys 3527, 7013, 2681, 7866, 8044, 1688, 5877, 1422, 3194, 4614,2852, 155, 2111, 3691, and 378 would be mapped in the following way if separate chaining wereapplied to manage collisions:In the above example, there are 7 collisions. The longest linked list has a size of 3. We say that the hash tablehas a load factor of 15/10 = 1.5 (Load factor = number of keys mapped/table size).Exercise0:This exercise requires you to demonstrate experimentally the relationship between load factor andcollisions. Write a program called Exercise0.java that can create a hash table of arbitrary size, andmap an arbitrary number of integers to that table. Your program should accept input from a user(specifying two integers: t - table size and n - number of keys), and print a representation of theresulting hash table along with statistics related to table size, number of keys, load factor, number ofcollisions, and longest list.Follow these steps:1. Prompt a user for an integer: t.2. Declare an ArrayList of type LinkedList of size t.You may find the following code snippet useful:ArrayList> table = new ArrayList>(t);3. Prompt a user for an integer: n.4. Generate n unique, random integer keys in the range 1-10000. Store these keys in asecondary structure (an array or ArrayList).Note: You must generate n unique keys. There should be no duplicate keys.5. Determine how to map each key. Use the basic hash function discussed in your lectures:pos = key % table size6. Add each key to the appropriate LinkedList. (The LinkedList referenced by index pos in theArrayList.)7. After all the keys have been mapped and added to the hash table, print statistics.Test your program with a variety of inputs to ensure its proper operation. Do not hard code inputs.Save data from one test run in a text file.A sample run of your Exercise0.java program should look like this:What size hash table do you want to work with?Enter a positive Integer: 10How many keys do you want to generate?Enter a positive Integer: 10Hash Table created:emptyStatistics:Table size: 10Number of keys: 10Load factor: 1.0NumbeCSCI 2110代做、代写Data Structures、r of collisions: 3Longest list: 3Now test your program repeatedly with a table size of 10 and 10, 20, 30, 40, 50, 60, 70, 80, 90, and100 keys. Save statistical data from your test runs in a text file showing table size, number of keys,load factor, number of collisions, and the length of the longest list in five columns.Table size #Keys Load factor #Collisions Longest list10 10 1.0 3 310 20 2.0 12 510 30 3.0 20 5......Exercise1:This exercise is designed to help you get familiar with the HashMap structure provided as part of theJava standard libraries (https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html). Write aprogram called Exercise1.java, that implements a simple, simulated login system using a pair ofHashMaps. Your program should accept input from a user (specifying the name of an input file)and read a file formatted like the one described below (see also: Students.txt).The input file will will contain an arbitrary number of lines of user data. A user’s full name (first andlast), username, and password will be separated by tabs.Ichabod Crane icrane qwerty123Brom Bones bbones pass456!Emboar Pokemon epokemon password123Rayquazza Pokemon rpokemon drow456Cool Dude cdude gh456!32Trend Chaser tchaser xpxo567!Chuck Norris cnorris power332*Drum Dude ddude jflajdljfpedCapture data from the input file, creating 2 HashMaps:1. A HashMap with username as key and the password as value.2. Another HashMap with the username as key and full name as value.Note: This is a toy program. It is acceptable to store the passwords in plaintext.After reading the input file and building HashMaps, your program should prompt a user to enter alogin name and password. If the login is successful, print a welcome message. If the password isincorrect, give the user 2 more chances. After 3 unsuccessful login attempts, your program shouldprint a failure message and exit.Test your program with a variety of inputs to ensure its proper operation. Do not hard code inputs.Save data from one test run in a text file.A sample run of your Exercise1.java program should look like this:Login: rpokemonPassword: drow456Login successfulWelcome Rayquazza PokemonA negative case should look like this:Login: cdudePassword: trythisEither the username or password is incorrect. You have 2 more attempts.Login: cdudePassword: trythatEither the username or password is incorrect. You have 1 more attempt.Login: cdudePassword: 675rtht!Sorry. Incorrect login. Please contact the system administrator.Submission:All submissions are through Brightspace. Log on dal.ca/brightspace using your Dal NetId. Deadlinefor submission: Wednesday 27 November 23h55 (five minutes before midnight).What to submit:Submit one ZIP file containing all source code (files with .java suffixes) and output files.Your final submission should include the following files: Exercise0.java, Exercise1.java,Students.txt, Outputs.txt or labelled test outputs for each exercise.You MUST SUBMIT .java files that are readable by your TAs. If you submit files that areunreadable such as .class, you will lose points. Please additionally comment out package specifiers.转自：http://www.daixie0.com/contents/9/4382.html