Design an algorithm that uses roll over hashing and analyze

Design an algorithm that uses roll over hashing and analyze its run time.

Solution

Hash table – implements a dictionary, by spreading items over an array – uses hash function h: Universe of keys (huge) Buckets (small) – Collisions: Multiple items may fall in same bucket – Chaining Solution: Place colliding items in linked list, then scan to search • Simple Uniform Hashing Assumption (SUHA): h is “random”, uniform on buckets – Hashing n items into m buckets expected “load” per bucket: n/m – If chaining used, expected search time O(1 + n/m)

Binary search on maximum match length L; to check if a length works: – Insert all length-L substrings of S in hash table – For each length-L substring x of T • Look in bucket h(x) to see if x is in S

Runtime Analysis • Binary search cost: O(log n) length values L tested • For each length value L, here are the costly operations: – Inserting all L-length substrings of S: n-L hashes • Each hash takes L time, so total work ((n-L)L)= (n2 ) – Hashing all L-length substrings of T: n-L hashes • another (n2 ) – Time for comparing substrings of T to substrings of S: • How many comparisons? • Under SUHA, each substring of T is compared to an expected O(1) of substrings of S found in its bucket • Each comparison takes O(L) • Hence, time for all comparisons: (nL)= (n2 ) • So (n2 ) work for each length • Hence (n2 log n) including binary search

Analysis: – n substrings to size-n table: average load 1 – SUHA: for every substring x of T, there is 1 other string in x’s bucket (in expectation) – Comparison work: L per string (in expectation) – So total work for all strings of T: nL = (n2 )

Application • Hash substrings to size n table • But store a signature with each substring – Using a second hash function to [1..n2 ] • Check each T-string against its bucket – First check signature, if match then compare strings – Signature is a small number, so comparing them is O(1