HashingSlide 2Slide 3Hash FunctionSlide 5Slide 6Types of Hash TablesOpen Addressing HashingSlide 9Open Addressing ExampleSlide 11Slide 12Slide 13Efficiency of Open HashingChaining (Bucket Hashing)Chaining ExampleSlide 17Slide 18Efficiency of ChainingHashing in JavaJava ContractHashingNelson Padua-PerezChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkHashingApproachTransform key into number (hash value)Use hash value to index object in hash tableUse hash function to convert key to numberHashingHash TableArray indexed using hash valuesHash Table A with size NIndices of A range from 0 to N-1Store in A[ hashValue % N]Hash FunctionGoalScatter values uniformly across rangeHash( <everything> ) = 0Satisfies definition of hash functionBut not very usefulMultiplicative congruency methodProduces good hash valuesHash value = (a int(key)) % NWhere N is table sizea, N are large primesHash FunctionExamplehashCode("apple") = 5hashCode("watermelon") = 3hashCode("grapes") = 8hashCode("kiwi") = 0hashCode("strawberry") = 9hashCode("mango") = 6hashCode("banana") = 2Perfect hash functionUnique values for each key kiwibananawatermelonapplemangograpesstrawberry0123456789Hash FunctionSuppose nowhashCode("apple") = 5hashCode("watermelon") = 3hashCode("grapes") = 8hashCode("kiwi") = 0hashCode("strawberry") = 9hashCode("mango") = 6hashCode("banana") = 2hashCode(“orange") = 3CollisionSame hash value for multiple keyskiwibananawatermelonapplemangograpesstrawberry0123456789Types of Hash TablesOpen addressingStore objects in each table entryChaining (bucket hashing)Store lists of objects in each table entryOpen Addressing HashingApproachHash table contains objectsProbe examine table entryCollisionMove K entries past current locationWrap around table if necessaryFind location for X1. Examine entry at A[ key(X) ]2. If entry = X, found3. If entry = empty, X not in hash table4. Else increment location by K, repeatOpen Addressing HashingApproachLinear probingK = 1May form clusters of contiguous entriesDeletionsFind location for XIf X inside cluster, leave non-empty markerInsertionFind location for XInsert if X not in hash tableCan insert X at first non-empty markerOpen Addressing ExampleHash codesH(A) = 6 H(C) = 6H(B) = 7 H(D) = 7Hash tableSize = 8 elements = empty entry* = non-empty markerLinear probingCollision move 1 entry past current location12345678Open Addressing ExampleOperationsInsert A, Insert B, Insert C, Insert D12345678A12345678AB12345678ABC12345678DABCOpen Addressing ExampleOperationsFind A, Find B, Find C, Find D12345678123456781234567812345678DABCDABCDABCDABCOpen Addressing ExampleOperationsDelete A, Delete C, Find D, Insert C12345678123456781234567812345678DCB*D*BCD*B*D*B*Efficiency of Open HashingLoad factor = entries / table sizeHashing is efficient for load factor < 90%Chaining (Bucket Hashing)ApproachHash table contains lists of objectsFind location for X Find hash code key for XExamine list at table entry A[ key ]CollisionMultiple entries in list for entryChaining ExampleHash codesH(A) = 6 H(C) = 6H(B) = 7 H(D) = 7Hash tableSize = 8 elements = empty entry12345678Chaining ExampleOperationsInsert A, Insert B, Insert C12345678 A12345678AB12345678CBAChaining ExampleOperationsFind B, Find A12345678CBA12345678CBAEfficiency of ChainingLoad factor = entries / table sizeAverage caseEvenly scattered entriesOperations = O( load factor )Worse case Entries mostly have same hash valueOperations = O( entries )Hashing in JavaCollectionshashMap & hashSet implement hashingObjectsBuilt-in support for hashingboolean equals(object o)int hashCode()Can override with own definitionsMust be careful to support Java contractJava ContracthashCode() Must return same value for object in each execution, provided no information used in equals comparisons on the object is modifiedequals()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
View Full Document
Unlocking...