Held: Wednesday, 16 September 2015

Back to Outline 08 - Roles of Data Structures and Abstract Data Types. On to Outline 10 - An Introduction to Trees.

Summary

We consider hash tables, one of the more popular implementations of the dictionary ADT.

Related Pages

Overview

• Review of hash tables.
• Hash functions, revisited.
• Other uses of hash tables and hash functions.

Administrivia

• I'm still thinking about the best way to adapt to different backgrounds on hash tables.
• Homework 1 returned!
• Eyes closed exercise: How comfortable are you with proof by induction?

Upcoming Work

• For Friday:
  • Read Skiena 3.7
• For next Wednesday: HW 3a 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.
• For next Wednesday: HW 3b Design SetOfStrings Implementations
  • A SetOfStrings ADT provides
    • 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 and related issues.)
  • For each, indicate the asymptotic cost of each method. In writing this, reflect on both the size of the set (n,m) and the size of the string (s).
    • This is an informal analysis question; no proofs 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 or 6pm

Review of Hash Tables

With your group

• What do you see as the key ideas behind hash tables?
• What ADT do hash tables implement?
• What design options are there in building hash tables?

Hash Functions

With your group

• What makes a good hash function?
• 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))?
• How would you rewrite this hash function to deal with the issue that integer values are capped?

Other Uses of Hash Tables and Functions

Ideas stolen from Skiena

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

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