1. Basic Concepts 2. The Standard Library Container Class 3. Vectors and Component Reuse 4. Lists: A Dynamic Data Structure 5. Stacks and Queues

6. Sets and Multisets 7. Trees 8. Hashing

Hashing

1. Introduction
   number of possible keys > amount of space available for table

   e.g. keys are words with 8 letters
   # of possible keys = 26⁸ ~ 2 x 10¹¹ ~ 200 Giga

   names → table sparse

   SMITH
   CHEN

   hash function which transforms a key to an index may map different keys to same index → collision

2. Hash Functions

   Hashing functions must be

   1. fast to compute
   2. evenely distributed the keys across the range of indices
   a) Truncation ignore part of the key
   

   ↑

   ↑

   ↑

   e.g.

   6	2	5	3	8	1	9	4
   ↑				↑		↑

   yeilds 3 1 4

   fast but may not be even

   b) folding

   divide and combine

   e.g.     625 | 381 | 94

   625

   381

   94

   --------

   1100

   may need to truncate to 100

   spread the keys better

   c) Modular Arithmetic

   convert key to integer X

   take the modulo of it with respect to table size n ( i.e. range of indices )

   i.e. i = x mod n ( e.g. if x = 20, n = 17, then i = 20 mod 17 = 3 )

   modules need to be a prime in order to spread the keys evenly

3. An example: The calendar problem

   R -- list contains 3-letter month name and number of days

   R = { ( JAN, 31 ), ( FEB, 28 ), ( MAR, 31 ), ( APR, 30 ),

   ( MAY, 31 ), ( JUN, 30 ), ( JUL, 31 ), ( AUG, 31 ),
   ( SEP, 30 ), ( OCT, 31 ), ( NOV, 30 ), ( DEC, 31 ) }

   month -- key

   given a key K, we want to find the # of days in the month
   e.g. K = 'AUG', &rarr 31

   Searching methods

   • linear search
     average # of comparisons N = ( 12 + 1 ) / 2 = 6.5

   • binary search
     N 3.1
     but R must be sorted ( time consuming ).
     insert, delete, update -- expensive

   • Using hash functions

     h (KEY ) -- convert first and second letters to ASCII codes, add them, and mod 13

     h(JAN)	= ( ASCII ( J ) + ASCII ( A ) ) mod 13
     	= ( 74 + 65 ) mod 13
     	= 139 mod 13
     	= 9

     Thus record with key JAN goes to location 9

     h(AUG)	= ( 65 + 85 ) mod 13
     	= 150 mod 13
     	= 7

     Thus record goes to location 7

     h(FEB)	= ( 70 + 69 ) mod 13
     	= 139 mod 13
     	= 9

     collide with key JAN
     so put that into next available empty position

     keys map to same integer are called synonyms
     ( JUN, JUL, OCT ), ( AUG, DEC ), ( JAN, FEB, SEP )

     index i	KEY	h(KEY)	# comparisons
     0	MAY	12	2
     1	NOV	1	1
     2	APR	2	1
     3	JUN	3	1
     4	JUL	3	2
     5	OCT	3	3
     6
     7	AUG	7	1
     8	DEC	7	2
     9	JAN	9	1
     10	FEB	9	2
     11	SEP	9	3
     12	MAR	12	1

     Average # of comparisons 1.67

     it depends on table density and quality of hashing function rather than size