CSCI 2110代做、代写Data Structures、Java程序语言调试、Java代写代做

日期：2019-11-29 12:52

CSCI 2110 Data Structures and Algorithms

Assignment N0. 4

Assigned: Wednesday 20 November

Due: Wednesday 27 November

23h55 (5 minutes to midnight)

Hashing

This assignment is designed to help you get familiar with hashing and Java’s HashMap.

Review

A hash table can be implemented as a simple array structure. When a key needs to be mapped to the

hash table, a hash function is used to determine the index at which it should be stored. A common

hash function is:

key % table size

If the table size is 10, then the keys 1008, 2540, 3467, and 789, would be mapped to locations 8, 0, 7

and 9, respectively.

It is possible for several keys may map to the same location. Using the simple function provided, the

keys 3467 and 2487 would both map to location 7. This is described as a hash collision. One way of

resolving these collisions is called separate chaining. Rather than storing the keys in the array, each

array 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 were

applied 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 table

has 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 and

collisions. Write a program called Exercise0.java that can create a hash table of arbitrary size, and

map 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 the

resulting hash table along with statistics related to table size, number of keys, load factor, number of

collisions, and longest list.

Follow these steps:

1. Prompt a user for an integer: t.

2. Declare an ArrayList of type LinkedList<Integer> of size t.

You may find the following code snippet useful:

ArrayList<LinkedList<Integer>> table = new ArrayList<LinkedList<Integer>>(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 a

secondary 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 size

6. Add each key to the appropriate LinkedList. (The LinkedList referenced by index pos in the

ArrayList.)

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: 10

How many keys do you want to generate?

Enter a positive Integer: 10

Hash Table created:

-->empty

Statistics:

Table size: 10

Number of keys: 10

Load factor: 1.0

Number of collisions: 3

Longest list: 3

Now test your program repeatedly with a table size of 10 and 10, 20, 30, 40, 50, 60, 70, 80, 90, and

100 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 list

10 10 1.0 3 3

10 20 2.0 12 5

10 30 3.0 20 5

...

...

Exercise1:

This exercise is designed to help you get familiar with the HashMap structure provided as part of the

Java standard libraries (https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html). Write a

program called Exercise1.java, that implements a simple, simulated login system using a pair of

HashMaps. 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 and

last), username, and password will be separated by tabs.

Ichabod Crane icrane qwerty123

Brom Bones bbones pass456!

Emboar Pokemon epokemon password123

Rayquazza Pokemon rpokemon drow456

Cool Dude cdude gh456!32

Trend Chaser tchaser xpxo567!

Chuck Norris cnorris power332*

Drum Dude ddude jflajdljfped

Capture 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 a

login name and password. If the login is successful, print a welcome message. If the password is

incorrect, give the user 2 more chances. After 3 unsuccessful login attempts, your program should

print 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: rpokemon

Password: drow456

Login successful

Welcome Rayquazza Pokemon

A negative case should look like this:

Login: cdude

Password: trythis

Either the username or password is incorrect. You have 2 more attempts.

Login: cdude

Password: trythat

Either the username or password is incorrect. You have 1 more attempt.

Login: cdude

Password: 675rtht!

Sorry. Incorrect login. Please contact the system administrator.

Submission:

All submissions are through Brightspace. Log on dal.ca/brightspace using your Dal NetId. Deadline

for 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 are

unreadable such as .class, you will lose points. Please additionally comment out package specifiers.