CS 2420 Lecture Notes - Lecture 11: Linked List, Memory Address, Binary Tree

• School: University of Utah
• Department: Computer Science
• Course: CS 2420
• Professor: H.Jamesde St.Germain

Document Summary

Items (keys) are saved in a key-indexed table, so location or index becomes a function computed from the key. Collisions: handling 2 keys (since they would hash to the same index/location. With no space limitation: just use key as index (n^2 memory) With no time limitation: use same index then sequential search/sort. Each table index is equally likely for each key. Ex: for phone numbers, using first 3 is bad (many same area codes) All java classes inherit method: hashcode() which returns 32-bit int, Default implementation is memory address of x (as key) for x. hashcode() Horner"s method: for hashing strings, uses ascii value of each char in string and adds (31. Since hash code is between -2^31 and 2^31-1, and we need to return value between 0 and m-1 (array index) Use prime (usually) for m in return statement. These are aromatized (averaged) over all operations, due to possible collisions in add operation leading to probing.