CMPS 12B Lecture 11: Class 11 - Guest Speaker: Ahmed: Further Hashing

4 Pages
Unlock Document

University of California - Santa Cruz
Computer Science
Darrell Long

CMPS 12B Lecture 11 5112017 (3:204:55) Guest Speaker Ahmed Sorting names in a school class o Seats and the people sitting in them are like a data structure o hash function = tells you where to sit restrict bits, (in the case of 10 bits, 10^24) nonreversible hash numbers, since all data is numbers. On hashing: o On reversibility: X 12 = 8, X < 24. Whats X? Could be 8 or 20. We dont know. Mapping something that is in a broad range to a fixed range. You map everything to a number, even if its a charstring If its a charstring, you have to have a fixed number for that charstring. Each letter corresponds to ASCII or some other system o On sorting, arrays If you want the largest value in an array, its O(1), since with arrays you can access any element at any time. o Convert name to number, Find everyone who has key value 42 into position 42. For every conceivable salary put them in brackets (lookup table) When key isnt unique, you overwrite. This also creates falsepositives. The point is though you want to create unique keys. This is hashing o On Collisions Hashing takes a large range of possible values and compresses it into a small range of possible values Use that as index of array to create hash table o hash function:
More Less

Related notes for CMPS 12B

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.