Homework 4

Due: Tuesday, 4/17/2022, by 8:00am

Overview

Do your own work for this assignment; do not work with others. Consult the resources provided and your professor for help if you need it. Please type your answers. Use good grammar, correct spelling, and complete sentences.

This assignment will be submitted on iLearn by the deadline and you will bring a physical printed copy at the beginning of class whenever that is for your section. Homework turned in after the deadline will not be accepted. Homework turned in after I have collected it will lose 20%. Please do not email late homework to your professor.

Any code you write should "just work" if the professor types it in and compiles and runs it.

Total points: 20. (not including the extra credit)

Assignment

  • 1. (10 points extra credit) Do problem 5.1 in your textbook. Insert the inputs in the given order. If any insertion fails, indicate that (but do not resize the table). The hash table size is implied by the hash function.

  • 2. (10 points extra credit) Do problem 5.2 in your textbook. Show the result for each of the four parts of the answer for 5.1. The hash table size should be a prime number at least as large as twice the original size, and the primary hash function should change to reflect the new table size.

  • 3. (20 points) Study the behaviors of different hashing and probing functions in an open-addressing hash table. Implement a limited-functionality hash table for strings, which keeps track only of whether a given slot is filled or empty. Then count the total number of probes required to insert all the words in the given dictionary for various methods and report those numbers. The number of probes to insert something that has no collisions is 1. The number of probes to insert something that has 3 collisions is 4, etc.

    Use the hash table sizes and functions given below. Note that some has table sizes are prime numbers (e.g. 1753) while others are not (e.g. 2048).

    Use the following hash functions for strings (you may need to make them static methods if called directly from main() ): 
    int hash_string_1(String key, int tableSize) {
  return (key.length() * key.length() * 4) % tableSize;
}

int hash_string_2(String key, int tableSize) {
  return   (key.charAt(0) + 
       27 * key.charAt(1) + 
      729 * key.charAt(2)) % tableSize;
}

int hash_string_3(String key, int tableSize) {
  // come up with your own hash function and see if you 
  // can do better on any of the test cases
}

    Provide your test code. Include it as part of your main document; all in one file: results, discussion, code, etc. Test your hash functions and table sizes on this dictionary (insert the words in the order given). Then report your results in a 12-by-6 table that displays the total number of probes required for each method. The columns for hash_string_1 and hash_string_2 are filled in so you can compare your results with your professor's. Your results should be the same as your professor for hash_string_1 and hash_string_2.

    PLEASE NOTE: some of the inserts may fail because the probes will overflow (especially quadratic probing — when the probe number is large, then its square will be too large to fit into a 32-bit integer). To deal with this, we will count up to N probes, where N is the table size, and then stop probing. So that insert will fail, but we will still count the N probes we used to find that it failed.

    Table Size Linear Probing with hash_string_1 Quadratic Probing with hash_string_1 Linear Probing with hash_string_2 Quadratic Probing with hash_string_2 Linear Probing with hash_string_3 Quadratic Probing with hash_string_3
    1753 175967 56546 2902 2077
    1786
    2039
    2048
    3067
    3072
    4093
    4096
    5119
    5120
    8191
    8192

    EXPLAIN your results. What do you notice about the different hash functions, table sizes, probing strategies, and why do you think they behave differently?