Solved

Hashing Algorithm

Posted on 2016-11-07
5
75 Views
Last Modified: 2016-11-07
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?
0
Comment
Question by:Bob Tian
  • 2
  • 2
5 Comments
 
LVL 27

Expert Comment

by:d-glitch
ID: 41877666
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
 

Author Comment

by:Bob Tian
ID: 41877731
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
 
LVL 27

Accepted Solution

by:
d-glitch earned 250 total points
ID: 41877747
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
 
LVL 26

Assisted Solution

by:Dr. Klahn
Dr. Klahn earned 250 total points
ID: 41877750
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
 

Author Closing Comment

by:Bob Tian
ID: 41877994
Thanks guys, I figured it out!
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

807 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question