Hashing Nelson Padua Perez Chau Wen Tseng Department of Computer Science University of Maryland College Park Hashing Approach Transform key into number hash value Use hash value to index object in hash table Use hash function to convert key to number Hashing Hash Table Array indexed using hash values Hash Table A with size N Indices of A range from 0 to N 1 Store in A hashValue N Hash Function Goal Scatter values uniformly across range Hash everything 0 Satisfies definition of hash function But not very useful Multiplicative congruency method Produces good hash values Hash value a int key N Where N is table size a N are large primes Hash Function Example hashCode apple 5 hashCode watermelon 3 hashCode grapes 8 hashCode kiwi 0 hashCode strawberry 9 hashCode mango 6 hashCode banana 2 Perfect hash function Unique values for each key 0 kiwi 1 2 3 banana watermelon 4 5 6 apple mango 7 8 9 grapes strawberry Hash Function Suppose now hashCode apple 5 hashCode watermelon 3 hashCode grapes 8 hashCode kiwi 0 hashCode strawberry 9 hashCode mango 6 hashCode banana 2 0 1 2 3 banana watermelon 4 5 6 hashCode orange 3 7 Collision 8 Same hash value for multiple keys kiwi 9 apple mango grapes strawberry Types of Hash Tables Open addressing Store objects in each table entry Chaining bucket hashing Store lists of objects in each table entry Open Addressing Hashing Approach Hash table contains objects Probe examine table entry Collision Move K entries past current location Wrap around table if necessary Find location for X 1 Examine entry at A key X 2 If entry X found 3 If entry empty X not in hash table 4 Else increment location by K repeat Open Addressing Hashing Approach Linear probing K 1 May form clusters of contiguous entries Deletions Find location for X If X inside cluster leave non empty marker Insertion Find location for X Insert if X not in hash table Can insert X at first non empty marker Open Addressing Example Hash codes H A 6 H B 7 H C 6 H D 7 Hash table Size 8 elements empty entry non empty marker Linear probing Collision move 1 entry past current location 1 2 3 4 5 6 7 8 Open Addressing Example Operations Insert A Insert B Insert C Insert D A 1 2 3 4 5 6 7 8 A B 1 2 3 4 5 6 7 8 A B C 1 2 3 4 5 6 7 8 D A B C 1 2 3 4 5 6 7 8 Open Addressing Example Operations Find A D A B C 1 2 3 4 5 6 7 8 Find B D A B C 1 2 3 4 5 6 7 8 Find C D A B C 1 2 3 4 5 6 7 8 Find D D A B C 1 2 3 4 5 6 7 8 Open Addressing Example Operations Delete A Delete C D B C 1 2 3 4 5 6 7 8 D B 1 2 3 4 5 6 7 8 Find D D B 1 2 3 4 5 6 7 8 Insert C D C B 1 2 3 4 5 6 7 8 Efficiency of Open Hashing Load factor entries table size Hashing is efficient for load factor 90 Chaining Bucket Hashing Approach Hash table contains lists of objects Find location for X Find hash code key for X Examine list at table entry A key Collision Multiple entries in list for entry Chaining Example Hash codes H A 6 H B 7 H C 6 H D 7 Hash table Size 8 elements empty entry 1 2 3 4 5 6 7 8 Chaining Example Operations Insert A 1 2 3 4 5 6 7 8 A Insert B 1 2 3 4 5 6 7 8 A B Insert C 1 2 3 4 5 6 7 8 C B A Chaining Example Operations Find B 1 2 3 4 5 6 7 8 C B Find A A 1 2 3 4 5 6 7 8 C B A Efficiency of Chaining Load factor entries table size Average case Evenly scattered entries Operations O load factor Worse case Entries mostly have same hash value Operations O entries Hashing in Java Collections hashMap hashSet implement hashing Objects Built in support for hashing boolean equals object o int hashCode Can override with own definitions Must be careful to support Java contract Java Contract hashCode Must return same value for object in each execution provided no information used in equals comparisons on the object is modified equals if a equals b then a hashCode must be the same as b hashCode if a hashCode b hashCode then a equals b a hashCode b hashCode Does not imply a equals b Though Java libraries will be more efficient if it is true
View Full Document
Unlocking...