CSC263H1 Lecture 9: CSC263-Notes-02-02-2015
Document Summary
Problem 1: read a text le, keep track of number of occurences of each character (ascii codes 0 - 127). Solution direct-access table: store number of occurences of each character in array with 128 positions. Problem 2: read a data le, keep track of each integer value (from 0 to 232 1). Solution wasteful: use array with 232 positions as above. Time is (1) but memory required is huge. , m 1}, h(k) maps keys to buckets. Strategies for collision resolution (a) pointer to new locatation / over ow (b) rule to nd the over ow. Each location of t stores linked list of items that hash to this location. It is equally likely for a key to go into any bucket. (cid:88) x u,h(x)=i. P [x] = for i = 0, 1, . De ne load factor = expected number of items in each bucket, = n m. N (x) = number of elements examined on search for x.
