Introduction
Syllabus
Guidelines for labs
Lab sections
Take quiz & check grades
 
Hashing Tables
 Motivation: If key can be used as index to array, search is O(1). 
 Keys as index may not be practical in several situations. 
Hash tables:
Try to achieve efficiency of arrays.
Hashing Functions:
map a key into an index for the array. If array has N entries, key should be mapped to
an integer between 0 and N1 (or 1 and N). Assume the key is an integer or may be treated
as an integer.
 Division Method: Using an array of size N, divide the key by N and take
the remainder as an index. Some values of N are better than others. Typically, use a prime
N. 
 Multiplication Method: Divide the key by a number A ( 0<A<1) and
take the fractional part of the number. Multiply this fractional part by the number of
elements in the array to obtain the index. 
 Universal Hashing: Use a collection of functions. Select one function
at run time. 
Collision:
Some keys will map to same index. How will you handle collisions?
 Linked list: Instead of array of records, use an array of linked lists of records.
 collision resolution by chaining 

 Open addressing: Use vacant positions of the
array for the colliding records 
Properties:
 number of elements stored: n 
 number of indexes in the array: m 
 load factor: (alfa= n / m) 
 simple uniform hashing: assume each element is equaly likely to hash into any of the m
slots 
Theorem 12.1:
Hash table with collisions handled by chaining, unsuccessful search takes Teta(1+alfa)
on the average.
Theorem 12.2:
Hash table with collisions handled by chaining, successful search takes Teta(1+alfa)
on the average.
