# 15110 Fall 2012 [Touretzky/Kaynar]

## Lab 7 - Thursday, October 11, 2012

### Deliverables

1. experiments.txt
2. mean_bucket.rb
3. largest_bucket.rb
4. my_hash_function.rb (challenge)

Place these files in a lab7 folder. Before leaving lab, zip up the lab7 folder and hand the zip file in.

### RubyLabs Information

This lab uses facilities provided by RubyLabs. If you were not present for Lab 4 (with the time operation) or Lab 6 (with the Canvas), you will need to setup RubyLabs before beginning this lab.

### CA-Led Activities/Demonstration

• Review ASCII encoding and string indexing in Ruby 1.8.
• Hash Functions

### Hash Functions

The correct operation of a hash table relies on a hash function that maps keys (in our case, these are strings) to non-negative integers that indicate which bucket the key belongs to. The hash table will work as long as the hash function maps each key to a non-negative integer less than the size of the hash table, but it will only perform well if it distributes keys relatively uniformly across buckets.

Consider the following hash functions:

1. Perhaps, the simplest possible hash function is one that just ignores the key and always returns 0:

def h0(key,ht_size)
return 0
end

2. Another hash function obtains the ASCII code of the first character in the key, divides that code by the size of the hash table, and returns the remainder of that division. This can be coded in Ruby as:

def h1(key,ht_size)
return key[0] % ht_size
end

3. Another hash function totals up the ASCII codes of all of the characters in the key, divides that total by the size of the hash table, and returns the remainder of that division:

def h2(key,ht_size)
x = 0
for i in 0..key.length-1 do
ascii_code = key[i]
x = x + ascii_code
end
return x % ht_size
end

This scheme examines all the letters in the string, but is not sensitive to order. So the strings "act", "cat", and "tac" will all hash to the same value.

4. It is also possible to build a hash function that is position sensitive, based on the idea of treating each character of the string as a digit in a number. The most familiar way of representing a number is to use a radix-10 system with the Arabic numerals: "0", "1", "2", "3", "4", "5" "6", "7", "8", "9". So, for example, "52473" means $((((((5*10+2)*10)+4)*10)+7)*10)+3.$ One can, however, also represent numbers using other systems with different sets of symbols. For example, one could represent numbers using the letters "a" - "z" for the numbers 0 through 25 to obtain the Radix-26 system described in your textbook. Characters in the computer are often stored using 7-bit ASCII codes (with values 0-127). So we can treat a string of ASCII characters as a Radix-128 number.

To make this into a Ruby hash function, one need only convert the string into a Ruby integer and then take the remainder of division by the size of the hash table:

def h3(key,ht_size)
x = 0
for i in 0..key.length-1 do
ascii_code = key[i]
x = 128 * x + ascii_code
end
return x % ht_size
end


### Self-Directed Activities

1. Hash Functions

For each of the hash functions, h0, h1, h2, and h3. What is the result of hashing the following strings for a table of size 100,000.

1. "Hash table"
2. "Table hash"
3. "Towers of Hanoi"

Would you get any collisions (when a key is placed in a bucket that already has a key) if you were to insert these keys into hash tables using each of these hash functions?

Record the results in experiments.txt.

2. Hash Table Statistics

Our hash tables are implemented as Ruby arrays where each element is a bucket. That bucket is an array that holds the entries that hashed to that bucket's index. In order to evaluate the effectiveness of different hash functions it is useful to be able to gather some statistics about the hash table after we've inserted a bunch of entries.

1. Define a Ruby function largest_bucket(ht) in largest_bucket.rb that returns the maximum number of entries contained within any single bucket of the hash table ht. You can follow this algorithm:

1. Set max_so_far to 0.
2. For each element, bucket, in the hash table, do the following:
1. If the length of bucket is greater than max_so_far, then:
1. Set max_so_far to the length of bucket
3. Return max_so_far.

Example:

>> largest_bucket([["a","b"],[],["w","x","y","z"],["c"]])
=> 4

2. Define a Ruby function mean_bucket(ht) in mean_bucket.rb that returns the arithmetic mean of the number of entries in non-empty buckets of the hash table ht. You can follow this algorithm:

1. Set nonempty_buckets to 0.
2. Set entries to 0.
3. For each element, bucket, in the hash table, do the following:
1. If the length of bucket is greater than 0.
2. Add the length of bucket to entries.
4. Return $$\frac{\textit{entries}}{\textit{nonempty_buckets}}$$.

Example:

>> mean_bucket([["a","b"],[],["w","x","y","z"],["c"]])
=> 2.33333333333333

3. Hash Table Experiments