Solved

Hashing Algorithm

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

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

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

Suggested Solutions

Title # Comments Views Activity
Binary Search Tree: How many trees of height 3 possible with 5 nodes 14 365
math problem distance of x 24 243
Lowest common IP of a range of IPs 6 303
How to build an APP for tablets 1 273
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
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…

739 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