- 作业标题：CSCI 2110 - Data Structures and Algorithms - Assignment No.5
- 课程名称：Dalhouse University CSCI 2110 Data Structures and Algorithms
- 完成周期：1天
描述
This assignment is on hash tables and hashing.
Review of hashing (from the lectures): A hash table is a simple array structure. Whenever a key needs to be
mapped onto the hash table, it uses a hash function. A common hash function used is key%table_size.
For example, if the table_size is 10 keys are 1008, 2540, 3467 and 789, they get mapped to locations 8, 0, 7 and
9, respectively.
However, multiple keys may map to the same location. For instance, in the above example, 3467 and 2487, will
both map to location no. 7. A hash collision is said to occur. One way of resolving a hash clash is called
separate chaining. Rather than storing the keys in the array, each array location contains a linked list. The keys
are stored in the linked list.
The following is an example in which 15 keys 3527, 7013, 2681, 7866, 8044, 1688, 5877, 1422, 3194, 4614,
2852, 155, 2111, 3691, and 378 are mapped onto a table of size 10:
In the above example, the number of times a collision has occurred is 7. 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. Note that this is not integer division).
Exercise 1:
This is an experimental exercise on hashing. Your task is to write a program that creates a hash
table of various sizes and various numbers of keys and collect statistics on the load factor, number of collisions
and the longest list length. Follow these steps.
- Prompt the user to enter the table_size.
- Declare an arraylist of linked lists of that size. Assume that the linked list store integer objects.
- Prompt the user to enter the number of keys to be hashed. Generate that many random keys in the range 1 to
- You need to generate non-duplicate keys. You can store the keys in another array or arraylist.
- For each key generated, determine where it should be mapped (pos = key%table_size).
- Go to the arraylist index pos and add the key into the linked list in that position.
- After all the keys have been added, determine the number of collisions and the longest list length.
- Run the program a number of times, experimenting with different number of keys (10,100, 500, 1000) and
different table sizes (10, 20, 30). Create a table showing your experimental values.
NOTE: A starter program HashTableExperiment.java has been given to you. Download this as well as
LinkedList.java and Node.java (the generic LinkedList and Node classes). This program first creates an
arraylist of linkedlist of integers, displays the empty linked list, then hashes a few keys, and displays them
again. It uses the generic LinkedList and Node classes that we developed before.
Please run the above program and see the output.
If you enter the size of the table to be 10, you should see the following output:
。。。
What to submit:
Your source code (HashTableExperiment.java), sample runs of the program in a text file, and the table of
experimental results in a text file.
Exercise 2:
The objective of this exercise is to create a simple hash map using the Java HashMap data
structure.
First review the HashMapDemo.java program given next to you. Run this program using the students.txt file
(also given).
Your friend is starting up a new web site that is going to have users register as members. He asks you to help
implement an application that would validate a member’s login.
Your task is to write a program that reads a file containing the full name, username, and password for each user.
Create a hashmap with the username as key and the password as value. Create another hashmap with the
username as key and
。。。
