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

CSCI 2110作业代做、代写Data Structures作业
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.

如有需要，请加QQ：99515681或 微信：codehelp