A hash table is a data structure that offers very fast insertion and searching operations. In this lab, we'll see the Hash Workshop applets demonstrate linear probing, double hashing, quadratic probing, and also separate chaining.
At the end of this lab, you need to submit a word document including some text answers and screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start->All Programs->Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).
1. Operations on Hash.html
To execute an applet, perform the following steps.
(1.) Click Start > Windows System -> Command Prompt. Use command "cd" to move into the directory where you run the applet, such as cd C:\COSC3333\Chap11\Hash. Then use the command appletviewer Hash.html to run the application, see Figure 1. see image.
(2.) Fill 30 in the blank of Enter number, and click New to initialize a 30 elements Hash table.
(3.) Fill 20 in the blank of Enter number, and click Fill to randomly initialize 20 elements into the hash table, we have Figure 2 (yours may be different since the numbers are randomly selected). The range of keys runs from 0 to 999, and the hash function is arrayIndex = key % arraySize; Q1: Depending on the Figure 2 showing below, 571 is inserted first or 301 inserted first? Why? see image.
(4.) Fill 96 in the blank of Enter number, and click Ins to insert this element, we have Figure 3 after it is inserted. see image.
(5.) Insert some more elements, 216, 156, and 426, finally you have Figure 4. Q2: What is the insertion process of the hash table with linear probing? Where it tries to insert the element if there is a collision? see image.
(6.) Fill 96 in the blank of Enter number, and click Find to search this element. Try again using 426, we have Figure 5 after it is found. Q3: What is the find process of the number 426? When to stop? see image.
(7.) Fill 96 in the blank of Enter number, and click Del to delete it and we have Fig. 6. Q4: What is the flag "*Del*" showing in the table, what is it used for? Delete again with number 426. see image.
2. Operations on HashDouble.html
(1.) Change directory by type the command "cd ..\HashDouble", then use the command appletviewer HashDouble.html to run the application.
(2.) Fill 30 in the blank of Enter number, and click New to initialize a 30 elements Hash table.
(3.) Fill 20 in the blank of Enter number, and click Fill to randomly initialize 20 elements into the hash table, we have Figure 7 (yours may be different since the numbers are randomly selected). see image.
(4.) Fill 96, 216, 156, and 426, in the blank of Enter number, and click Ins to insert all elements, we have Figure 8 after it is inserted. Q5: What is the insertion process of the hash table with double hashing? The 2 nd hash function is stepSize = 7- (key %7); see image.
(5.) Fill 30 in the blank of Enter number, and click New to initialize a 30 elements Hash table, select Button Quad this time before you create it. Fill 20 in the blank of Enter number, and click Fill to randomly initialize 20 elements into the hash table, we have Figure 9 (yours may be different since the numbers are randomly selected). see image.
(6.) Fill 96, 216, 156, and 426, in the blank of Enter number, and click Ins to insert all elements, we have Figure 10 after it is inserted. Q6: What is the insertion process of the hash table with quadratic probing? What happen if there is a collision? see image.
3. Operations on HashChain.html
(1.) Change directory by type the command "cd ..\HashChain", then use the command appletviewer HashChain.html to run the application.
(2.) Fill 10 in the blank of Enter number, and click New to initialize a 10 elements Hash table.
(3.) Fill 20 in the blank of Enter number, and click Fill to randomly initialize 20 elements into the hash table, we have Figure 11 (yours may be different since the numbers are randomly selected). see image.
(4.) Fill 96, 216, 156, and 426, in the blank of Enter number, and click Ins to insert all elements, we have Figure 12 after it is inserted. Q7: What is the insertion process of the hash table with a separate chaining? see image.
(8.) Fill 96 in the blank of Enter number, and click Find to search this element. We have Figure 13 after it is found. Q8: What is the find process of the Hash Table with a Separate Chaining? see image.
Q1: Depending on the Figure 2 showing below, 571 is inserted first or 301 inserted first? Why?
Q2: What is the insertion process of the hash table with linear probing? Where it tries to insert the element if there is a collision?
Q3: What is the find process of the number 426 with Linear Probing? When to stop?
Q4: What is the flag "*Del*" showing in the table, what is it used for?
Q5: What is the insertion process of the hash table with double hashing? The 2 nd hash function is stepSize = 7- (key %7);
Q6: What is the insertion process of the hash table with quadratic probing? What happen if there is a collision?
Q7: What is the insertion process of the hash table with a separate chaining?
Q8: What is the find process of the Hash Table with a Separate Chaining?
Submit the screenshots for Figure 2, Figure 4 to Figure 13 (totally 11 figures) through Blackboard. (Don't forget to include your name in the program). (At the end of this lab, you need to submit a word document including some screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start->All Programs- >Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).