Solved

Hashing Algorithm

Posted on 2016-11-07
5
84 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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 27

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

Secure Your Active Directory - April 20, 2017

Active Directory plays a critical role in your company’s IT infrastructure and keeping it secure in today’s hacker-infested world is a must.
Microsoft published 300+ pages of guidance, but who has the time, money, and resources to implement? Register now to find an easier way.

Question has a verified solution.

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

Suggested Solutions

Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
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…

740 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