Home /
Expert Answers /
Computer Science /
please-show-all-steps-and-work-thank-you-a-common-hashing-function-that-is-used-to-assign-memory-ad-pa288
(Solved): Please show all steps and work. Thank you A common hashing function that is used to assign memory ad ...
Please show all steps and work. Thank you
A common hashing function that is used to assign memory addresses to records is Defined by where is an integer and is the number of memory locations. A collision occurs when any two inputs are sent to the same memory location (in other words, it has the same output). Let be a finite set of input records. Prove that if , then there must be at least one memory location with collisions using the above defined .
Expert Answer
To prove that if |S| > km, then there must be at least one memory location with k collisions using the hashing function h_m(k) = k mod m, we can use the Pigeonhole Principle.The Pigeonhole Principle states that if you distribute more than k items into k containers, then at least one container must contain more than one item.In this case, the memory locations act as containers, and the input records in set S act as items to be distributed.Let's assume that |S| > km. We need to show that there exists at least one memory location with k collisions.Since there are m memory locations and k possible outputs for each memory location (0, 1, ..., m-1), there are a total of m * k possible combinations of outputs.