CSC301.01 2015F, Class 09: Hash Tables
======================================

_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
--------------------------------------------