COMS W3134 Lecture 12: Data Structures- Lecture 12

• School: Columbia University
• Department: Computer Science
• Course: COMS W3134
• Professor: Paul Blaer

Document Summary

I chapter 5 problem : collisions ! can happen when multiple things end up at the same location. Char at lili i t. tl 9 lousy function . issue : anagrams return hash val % table sive i. I return ( key . char atto) -127 * key . Char attu) 1% table size ; only looks at the first three chars. } so due to integer overflow good hash table size : prime insert example : ints hash ( x ) = x gives unique number. Table size insert 1571 (cid:15482) hash 1571=57 (cid:15482) 57%-15=7 insert 164 ) (cid:15482) hash ( 647=64 (cid:15482) 64%-15=4 contains g1 ) contains 177 ) (cid:15482) location 7- (cid:15482) insert 141 (cid:15482) hash 141=4 (cid:15482) 4%-15=4. 57 store linked list instead insert 1641 insert 141 cost : oln ) insert. We always have to check for already existing values because we can"t have duplicates o.