CMPSC 32 Lecture Notes - Lecture 7: Linked List, Double Hashing, Prime Number
Document Summary
Hashing = a more generalized way of indexing objects. Solution: if you know that the keys are multiples of some number, divide each key by that multiple and place it in that index. Compresses the range of inputs into smaller range of numbers. Downside: hashing collision = when a hash function outputs the same indices for two different keys. Open-address hashing = searches through locations until hashed index is found, or an unused index is found. Pro: guarantees you"ll never go over your range. Capacity is best chosen to be a prime number insert(key, value) find(cid:383)key, (cid:384) remove(key) Out-of-band-value problem = when a value is not in its natural range of return values. Out-of-band-value = character that never appears in the rest of the file. Out-of-band-value -1 indicates never used, -2 indicates previously used. If an index is used, go to the next one, until you find -1 or -2.
