CSC263H5 Lecture Notes - Lecture 5: Spell Checker, Prime Number, Bit Array

• School: UTM
• Department: Computer Science
• Course: CSC263H5
• Professor: Sushant Sachdeva

Document Summary

Csc263h5s - software programming and tools (winter 2018) Week 5 - hash tables (february 2, 2018) Python dict is implemented using hash table. Spell checkers: just modify one letter of the wrong word at a time, and lookup a dictionary implemented by hash table. Hash table is used for a quick lookup. Problem: read a grade file, keep track of number of occurrences of each grade (int 0~100) The fastest way: create an array t[0100] where t[i] stores the number of occurrences of grade i. Directly using the key as the index of the table. This is different than the hash we are referring to. The hash function on python converts the integer but not map the number of slots. Universe of keys u - the set of all possible keys. Hash table t: an array with m positions, each position called a slot or a bucket Hash function h: a function maps u to {0, 1, , m-1}