2016-05-20

posted May 20, 2016, 8:41 AM by Samuel Konstantinovich   [ updated May 20, 2016, 9:17 AM ]
If I were to give a quiz on Monday on Hash Tables... It would Look like this:

381. Which of the following scenarios leads to linear running time for a random search hit in a linear-probing hash table?
a) All keys hash to same index
b) All keys hash to different indices
c) All keys hash to an even-numbered index
d) All keys hash to different even-numbered indices
e) None of these.

583. What is the best definition of a collision in a hash table?
A. Two entries are identical except for their keys.
B. Two entries with different data have the exact same key.
C. Two entries with different keys have the same exact hash value.
D. Two entries with the exact same key have different hash values.

207. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?
A. 256
B. 511
C. 512
D. 1024
E. There is no maximum.

402. An open addressed hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?
A. 256
B. 511
C. 512
D. 1024
E. There is no maximum.

481. Draw a hash table with open addressing and linear probing with a size of 9. Use the hash function k%9. Insert the keys: 5, 29, 20, 0, 27 and 18 into your table (in that order). The values can all be null, they do not matter.

999. Draw a hash table with chaining and a size of 9. Use the hash function k%9. Insert the keys: 5, 29, 20, 0, 27 and 18 into your table (in that order). The values can all be null, they do not matter.

4810. You are writing code for the remove member function of a chained hash table. Fill in the blanks in this pseudocode with the two missing statements. You may use pseudocode yourself!

public class HashTable{

  public void remove(int key)  {
        Node cursor;//a double linked node with set/get Key/Value/Prev/Next

        int i;

        i = hash(key);

        //Make cursor point to the node that contains an item with the given key
        //(or set it to NULL if there is no such node).

        if (cursor != NULL){



         }
   }
}

Comments