Solved

Hashing Algorithm

Posted on 2016-11-07
5
52 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 24

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

This algorithm (in C#) will resize any image down to a given size while maintaining the original aspect ratio. The maximum width and max height are both optional but if neither are given, the original image is returned. This example is designed t…
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…
This tutorial gives a high-level tour of the interface of Marketo (a marketing automation tool to help businesses track and engage prospective customers and drive them to purchase). You will see the main areas including Marketing Activities, Design …
Windows 10 is mostly good. However the one thing that annoys me is how many clicks you have to do to dial a VPN connection. You have to go to settings from the start menu, (2 clicks), Network and Internet (1 click), Click VPN (another click) then fi…

920 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

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now