CSE logo University of Washington Computer Science & Engineering
 CSE326 Wet 2
  CSE Home     326 Assignments  About Us    Search    Contact Info 

Sample Input File

example.txt

Running this file should produce the following output (java program pictured, C++ would be similar). 

  $ java MyTestClass example.txt
  22.1
  $


Hash Functions

Below are C++ and Java implementations of a hash function that you can assume distributes its input uniformly over the integers. The function is of the form (see the code for the exact syntax) 

 Hash326(n, val : int) : int
For each n, Hash326(n, x) distributes x uniformly over the integers. Thus something like 
 idx = Hash326(0, val) mod table_size;
will give you a good hash index. Note that this alone does not mean your hash table will work well, for example, table_size must be large enough. If you you reasonable parameters with the rest of your hash table, using this hash function you may assume that hash finds and inserts take O(1) time.

Think of Hash326() as being a family of hash functions, indexed by the parameter n. This makes it easy to use for double hashing: Hash326(0, x) is your primary hash function, and Hash326(1, x) is your secondary hash function.

The code below is straightforward, but a little long. Feel free to copy and paste things into your own classes if it makes your life easier.

Let me know if there are any problems, or if it doesn't seem to be working. For the curious, I adapted the MD5 hash, which is a common cryptographic hash. See Chapter 9 in the Handbook of Applied Cryptograpy if you're curious.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to cary]