Which operation has minimum time complexity!
Hye, everyone! Does anyone know which operation has minimum complexity and why?
Chaining or Linear probing or Quadratic probing??
Chaining or Linear probing or Quadratic probing??
the hash function used, data, table size vs data size, implementations, and collision approach all play a factor.
lets say your table size is 10, and you have 12 items.
both probes need to discover that the table is full and quit. this takes at least O(N) if you were not tracking the # of items vs table size on the side. (I assume quadratic eventually hits all slots. If you just run out to the end of the array once and give up, its less, but easy to figure out). Chain just stuffs the item in its bucket. If you tracked the number its O(1) to give up, of course. This isn't related to the probes but the implementation.
lets say you have table size 10 and 9 items in it.
the 2 probes have to find the empty hole. You can figure out for yourself how long that might take. Chain just inserts it in the bucket.
lets say your hash function is crap and always returns zero. Table size 1 million, 500k items. How long does it take the 2 probes to find the next open slot?
the bucket just grows. If the bucket is a sorted vector in c++, you pay O(1) to insert, about O(N) to sort it after inserting (look up the performance of the sort on data where it is pre-sorted such that most items are already in place) and Lg(N) to binary search the bucket inside.
Those 3 scenarios should show you a mix of worst case scenarios and time taken.
I am a strong advocate of chains via vectors (sorted or not). Your inserts are always O(1)**, your fetches are at worst N/tablesize assuming a uniform hash that evenly distributes the buckets.
**I assume you have optimized the buckets to avoid vector resize problems for large amounts of data.
lets say your table size is 10, and you have 12 items.
both probes need to discover that the table is full and quit. this takes at least O(N) if you were not tracking the # of items vs table size on the side. (I assume quadratic eventually hits all slots. If you just run out to the end of the array once and give up, its less, but easy to figure out). Chain just stuffs the item in its bucket. If you tracked the number its O(1) to give up, of course. This isn't related to the probes but the implementation.
lets say you have table size 10 and 9 items in it.
the 2 probes have to find the empty hole. You can figure out for yourself how long that might take. Chain just inserts it in the bucket.
lets say your hash function is crap and always returns zero. Table size 1 million, 500k items. How long does it take the 2 probes to find the next open slot?
the bucket just grows. If the bucket is a sorted vector in c++, you pay O(1) to insert, about O(N) to sort it after inserting (look up the performance of the sort on data where it is pre-sorted such that most items are already in place) and Lg(N) to binary search the bucket inside.
Those 3 scenarios should show you a mix of worst case scenarios and time taken.
I am a strong advocate of chains via vectors (sorted or not). Your inserts are always O(1)**, your fetches are at worst N/tablesize assuming a uniform hash that evenly distributes the buckets.
**I assume you have optimized the buckets to avoid vector resize problems for large amounts of data.
Last edited on
"Write a program to Find the Number in the HASH table with minimum
complexity, Make Sure you your code have minimum complexity."
This is a question assigned to me. So I think it's talking about searching a number in a hash table.
complexity, Make Sure you your code have minimum complexity."
This is a question assigned to me. So I think it's talking about searching a number in a hash table.
any details on what number means? Double? Int? Char? 256 bit bignum?
how many you will get? etc? I said it depends. So you need more info.
Or just do the best you can?
how many you will get? etc? I said it depends. So you need more info.
Or just do the best you can?
Last edited on
you do not seem to get it.
to have a perfect hash means to KNOW YOUR DATA.
if you want to maximize its performance, there is no shortcut to that.
you want to store and fetch integers. ok, lets work off that and say its type c++ int and can be any value in that type, input via a uniform distribution.
How many ints do you want your table to be able to work with at top speed?
lets assume you will do what I recommended and your hash table looks like
vector<vector<int> > htab(10000); //check the syntax, you want size (10000 here) rows of vectors of ints, and I avoid 2-d constructs usually, so this may need correction.
and that for starters you just use hash = input%tablesize.
is that good enough? Use push-back to add your data to each bucket. Just search the relevant bucket with iteration to start with, after hashing to that bucket upon a query.
Code that up and see if you need to do more to it ... is it good enough?
to have a perfect hash means to KNOW YOUR DATA.
if you want to maximize its performance, there is no shortcut to that.
you want to store and fetch integers. ok, lets work off that and say its type c++ int and can be any value in that type, input via a uniform distribution.
How many ints do you want your table to be able to work with at top speed?
lets assume you will do what I recommended and your hash table looks like
vector<vector<int> > htab(10000); //check the syntax, you want size (10000 here) rows of vectors of ints, and I avoid 2-d constructs usually, so this may need correction.
and that for starters you just use hash = input%tablesize.
is that good enough? Use push-back to add your data to each bucket. Just search the relevant bucket with iteration to start with, after hashing to that bucket upon a query.
Code that up and see if you need to do more to it ... is it good enough?
Last edited on
| Write a program to Find the Number in the HASH table with minimum complexity. |
Topic archived. No new replies allowed.