Programming Task 2: Hash Hash Hash

Reviewed October 8th, 2014


The Programming tasks for this assignment:

  1. Input: A sequence of m lines each with an n length ascii character string

    The input will come from stdin. Here n changes from line to line and is not provided to you.

    Output: m lines each with an integer between -k and k, for some k of your choosing with k \(\leq 2^{32}\) (you may ignore the ability to use negatives).

    Constraints: Your function is a hash function. Your choice of k can be defended to me. I encourage you to look at popular hashing techniques (here is a list on wikipedia). I am looking for a good uniform spread of the outputs (in particular the printable ascii characters). Implement the hashing yourself, don't just call someone else's hash function.

    Sample instance:

          CaT iN hAt
  2. Input:A line to stdin with the integer m. Then m lines of key value pairs to stdin. Each key-value line consists of two character strings separated by four spaces (neither string contains four sequential spaces). Then you will be given a line of three asterisks followed with a line consisting of one key character string.

    Output: Print a single line containing the second character string from the line which started with the final character string or if no such line was given print NONE.

    Constraints: I want you to use your hashing function from problem 1 to create a hash table in this problem. Hash the keys, then store the data and key, in an array of length 2*k. Discuss the cost of your implementation for large values of m

    Sample instance:
          key1    value1
          key2    value2