CSE 15 Lecture Notes - Lecture 11: Hash Table, Lookup Table, Bloom Filter
Document Summary
What"s x: could be 8 or 20. We don"t know: mapping something that is in a broad range to a fixed range, you map everything to a number, even if it"s a char/string. If it"s a char/string, you have to have a fixed number for that char/string. Each letter corresponds to ascii or some other system: on sorting, arrays. If you want the largest value in an array, it"s o(1), since with arrays you can access any element at any time: convert name to number, find everyone who has key value 42 into position 42. For every conceivable salary put them in brackets (look-up table: when key isn"t unique, you overwrite. 3 is empty, however, but that"s because someone was sitting and 3 and left: so, first time you come across a truly empty spot, you can give up. but if you get a spot had just been emptied. Each seat also has values -1 and -2.
