CS 225 Lecture Notes - Lecture 32: Hash Table, Quadratic Probing, Durian
18 Nov 2016
School
Department
Course
Professor
Document Summary
Explain the operations of a hash table: insert, find, delete. They are fast (o(1)) -- if you know where the data is. They are fixed size, it takes a long time (o(n)) to find something we put into it (unless we sort it), we can only index using an integer. A hash table is an array t together with a hashing function h. The hash function h(x) takes our data x and converts it into an integer i. We can tell where the data should go simply by looking at it, no need for comparisons. We assume that h(x) runs quickly (o(1)). We"ll talk about good hashing functions next time. Really cool thing you can do with has functions if it is strong enough, Don"t try to make one yourself if you haven"t seen one. 24 definition of hashing function x apple banana cherry durian eggplant fig grape.
