Homework: Hashing and Implementing Mod

This homework is necessary preparation for the lab.

1. Provide an implementation for the following static method mod that computes the modulo function using "clock arithmetic".

   /**
    * Computes {@code a} mod {@code b} as % should have been defined to work.
    * 
    * @param a
    *            the number being reduced
    * @param b
    *            the modulus
    * @return the result of a mod b, which satisfies 0 <= {@code mod} < b
    * @requires b > 0
    * @ensures <pre>
    * 0 <= mod  and  mod < b  and
    * there exists k: integer (a = k * b + mod)
    * </pre>
    */
   public static int mod(int a, int b) {...}
   

   Note that, although you can use the remainder operator % in your solution, the following is not a correct implementation.

   public static int mod(int a, int b) {
       return a % b;
   }
   

   If you are not sure why not, see the CSE 2221 lab where this was discussed (Sections 3. Debugging Oddity and Additional Activities).

2. Consider the set of integer {432, 17, 54, –788, –101, 84, 0, –6, –195, 90} and a hash table of size 10. Answer the following questions.

   1. There are many implementations of hashCode that might seem reasonable when the argument type is Integer. For example, if you don't know anything in advance about the Integer values that might be likely to be hashed, then the implementation for hashCode that just returns the integer itself is quite reasonable (and, as it happens, this is the actual implementation provided by java.lang.Integer in the standard Java library). Show how the elements of the set above are distributed among the buckets by this hash function.

      Bucket	Integers Hashed
      0
      1
      2
      3
      4
      5
      6
      7
      8
      9

   2. Write any qualitatively different implementation of hashCode when the argument type is Integer that might seem "reasonable" (without thinking in advance about the particular elements of the set above). Then show how the elements of the set above are distributed among the buckets by this hash function.

      Bucket	Integers Hashed
      0
      1
      2
      3
      4
      5
      6
      7
      8
      9

Additional Questions

1. A student once wrote a solution to question 2.ii above that returns the square of the given Integer. Forget for a moment that this might overflow, and consider instead his astute observation: for a hash table of size 10, this hash function results in at least 4 of the 10 buckets remaining empty. The reason is that there is no square whose last digit is 2, 3, 7, or 8. Prove that, for any hash table of size greater than 2, this hash function will always leave some buckets empty.