CSC263H1 Lecture Notes - Lecture 5: Universal Hashing, Linked List, Linear Probing
18 Oct 2017
School
Department
Course
Professor
Document Summary
Csc 263 lecture summary for week 5 winter 2017. Problem 1: read a text file, keep track of number of occurrences of each character (with values 0 - 255, assuming 8-bit encoding). Direct-address table: store number of occurrences of each character in array with 256 positions (one for each character). Problem 2: read a data file, keep track of number of occurrences of each integer value (from 0 to 2^{32}-1). Wasteful: use array with 2^{32} positions, as above. Time theta(1) but memory required is huge, especially when data files relatively small (say approx. Instead, allocate array with 10,000 positions (for example), and figure out how to map each integer to one positions -- hashing. Universe of keys u (set of all possible keys). Hash table t = array with m positions (m depends on application); each array location called slot or bucket. Hash function h : u -> {0,1,,m-1} maps keys to array positions.
