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?
Bob TianAsked:
Who is Participating?
 
d-glitchConnect With a Mentor Commented:
You have to process N items.
Presumably you will have some hashing algorithm to select a bucket for each item.
If you keep a counter for each bucket, you can increment it each time you assign an item.
If you can keep a list of the fullest buckets (this will be hard at the beginning when they are all tied), you will know which bucket is fullest without searching.
1
 
d-glitchCommented:
Not exactly clear what you are trying to do, or what your actual question is?

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.
0
 
Bob TianAuthor Commented:
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..
0
 
Dr. KlahnConnect With a Mentor Principal Software EngineerCommented:
Finding the most filled bucket without sorting is trivial.  Adapt the search algorithm to look at the current bucket, and keep track of the most filled bucket and how many records are in it.  Compare and update on each access.  This adds slight overhead at each access but much less than searching the database.
1
 
Bob TianAuthor Commented:
Thanks guys, I figured it out!
0
All Courses

From novice to tech pro — start learning today.