Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Review of hash tables.
• Hash functions, revisited.
• Other uses of hash tables and hash functions.

Preliminaries

Admin

• I'm still thinking about the best way to adapt to different backgrounds on hash tables.
• Homework 1 returned!
• Please use a monospace font when we print code.

Upcoming Work

• For Friday:
  • Read Skiena 3.7
• HW for next Wednesday: Implement chained/bucketed hash tables
  • In Scheme
  • With strings as keys
  • An arbitrary values as values
  • That grow when more than 50% full
  • And use the Skiena "sum of powers" for the hash function
  • Ideally, parameterize the "constructor" to allow changing some of these policies.
  • Ideally, with unit tests.
• HW for next Wednesday:
  • A SetOfStrings ADT provides the methods: add(set,val), remove(set,val), contains(set,val), union(set,set), subtract(set,set)
  • Describe three different reasonable implementations of SetOfStrings. (You need not write code; just describe memory arrangement.)
  • For each, indicate the asymptotic cost of each method. In writing this, reflect on both the size of the set and the size of the string. No formal proof necessary.

Extra Credit

Academic

• No CS Table next Tuesday
• CS Extras, Wednesday, Jonathan Wellons '04 from Google
• Convo Thursday at 11 am in JRC 101: Mike Latham

Peer

• Soccer today at 4pm (yay NBB!) or 6pm (yay EE!)
• EE show at Smith, starting Monday

HW2 Issues

• Eyes closed exercise: How comfortable are you with proof by induction?
  • 1/3 very comfortable
  • 1/3 very uncomfortable
  • 1/3 okay
  • May be more the context than induction itself
    • With a new notation - Big-O
    • And with inequalities
  • Strong induction is similar but new

Questions

Review of hash tables

What do you see as the key ideas of hash tables?

• Every entry is a key/value pair - An implementation of the Dictionary ADT
• There is a "hash function" that converts each key to an integer
• Ideally, two separate inputs will give you two separate values
  • If ints are 8 bytes, there are 2^64 different integers
  • If strings can be only be 100 characters long, there are 26^100 or 128^100 or ...
• We use those integers to store key/value pairs in an array (usually at hash(key) % array.size)
• This gives constant time set/get

• We will get duplication: Two key/values will try to fit into the the same slot in the array. What do we do?

  • Probed - Look elsewhere in the table (increment by 1 or 2 or use a different hash function or ...)
  • Bucket/Chained - Store a linked list in each cell of the array, and just add to the linked list

• Do we still get expected constant time get/set?

  • Worst case: O(n), where n is the number of elements
  • Expected case: O(1)
    • Good hash function
    • Lots of space in the hash table
    • Beautiful math next time

What are some design choices you have to make in implementing hash tables?

• What hash function do you use?
• What size of table do you make?
• When do you increase the size of the table
• How much do you increase the size of the table

Hash functions, revisited

With your group

• What makes a good hash function?
  • Distributes values well
• What does the following hash function do?

Function borrowed from Skienna p. 89; expects arbitrary-precision integers

#define alpha SOME_LARGE_PRIME
int hash(char *s)
{
  int len = strlen(s);
  int code = 0;
  for (int i = 0; i < len; i++)
    {
      code += s[i] * expt(alpha, len-(i+1))
    } // for
  return code;
} // hash

• Suppose we have a really long string. What the difference between hash(substring(str, 0, k)) and hash(substring(str, 1, k+1))? E.g., hash(substring(str, 0, 6) vs hash(substring(str, 1, 7))
  • (hash(substring(str,0,6)) - str[0]*expt(alpha,6))*alpha + str[7]
• How would you rewrite this hash function to deal with the issue that integer values are capped? (use modulo)

Other Uses of Hash Tables and Functions

Ideas stolen from Skiena

How could you use hash functions or tables to help you ...

• Detect plagiarism
• Determine if string a is a substring of string b?

Other uses of hash tables and hash functions