Bob Tian
asked on
Hashing Algorithm
Hello, I was wondering if its possible to have m buckets, and n elements and finding the most filled bucket in O(1) time without any sorting. Searching through the buckets would take at least O(m) time, but is it possible to get O(1) without any sorting and using some algorithm based on hashing?
ASKER
Assuming there are M buckets and N elements, with N greater than M. Ideally it should work for any M and N, but can assume M <=125. I am expecting collision, and finding out which bucket has the most elements. Is it possible to process each element in O(1) expected time and lookup for the most filled bucket (ie. Bucket C has the most elements, return C, the name of the bucket) to also be in O(1) expected time.
My constraint is that it has to be done in some algorithm based on hashing and without any sort algorithm.
Currently I'm having trouble seeing how this can be done..
My constraint is that it has to be done in some algorithm based on hashing and without any sort algorithm.
Currently I'm having trouble seeing how this can be done..
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thanks guys, I figured it out!
Are you searching, sorting, or hashing?
Is m (the number of buckets) greater than n (the number of elements)? This is what you want for effective hashing.
But you also mentioned something about the "most filled bucket" which implies you are expecting some collisions.
Look-up performance for good hashing approaches O(1), although building the table is still O(n).
If all that matters is the location of the bucket with the most elements, you can keep track of that during the build phase so you won't have to search for it.