COMP 2140 Lecture 11: 10_10_recap.pdf
13 Aug 2014
School
Department
Course
Professor
Document Summary
Usually, looking up the entries by key (search/retrieve) is the most important operation for table. In many cases, we would like to be able to do it in o(1) time searching a table of 100 entries would take the same time as searching a table of 10000 entries. To allow fast searching for a key, sometimes we can use the key as the index into an array. It does not work for keys that are not numeric. 0 to n-1) in an array hash function maps keys to value in 0 to n 1 use hash function to determine which bucket an element belongs in and only searches/modifies this one bucket. If you directly use the key as array index, you are implicitly using a simple hash function keys are in 0, 1, 2, hash function: h(k)=k search, insert, delete would all take o(1) time in an array. Hash function example: compression map keys = integers.
