Discussion on "Do hash tables really help in reducing time complexity ?"

PRASHANTH H N · 2019-05-23T15:59:30.395Z

Is hashing a real practical solution for finding, inserting and deleting elements with time complexity of O(1) ? If this question is in your mind then you are at the right spot. Please refer this page to get some basic idea of hash tables. Let's do ...

As far as i remember from university, it also depends on what you mean by 'finding' in your scenario.
If you need to retrieve a value by key lookup hashmaps are perfect, if you want to find within a range then there are other data structures like B+ trees.
Interesting comparison anyway! Seeing big-O notation made me feel at school again ;-)

The collisions affecting complexity is an interesting point.

But how big is the effect in reality?

If your hashes are 32 bits and have a good distribution, wouldn't you need somewhere in the order of 2^32 elements to get a lot of collisions and noticeably affect time complexity? Does it really already happen at 2% of 2^32 as used?

Meanwhile many array implementations are indexed with 32 bit integers, so they have a hard limit of 2^32 items. Easy to solve, but suggests the limit is rarely reached.

So while theoretically interesting, wouldn't it be safe in practise to consider O(1) complexity for 99.99% of cases?

Are you saying that there will be 2^32 buckets will be available? If yes, we can print out the bucket id ( i know only in c++). I would take the pleasure of doing it and try to get back with results. Also, I didn't get this point of yours - "So while theoretically interesting, wouldn't it be safe in practise to consider O(1) complexity for 99.99% of cases?".

PRASHANTH H N Thanks for the answer.

I didn't quite mean that there are 2^32 buckets, but that the number of buckets increases with the number of hashes that have been inserted.

So I'd personally think the performance only starts to degrade away from O(1) when there are so many elements that a substantial part of them are hash collisions

Which I would say happens when the number of elements gets close to 2^32 (for good hash functions). Because there are only 2^32 possible values for an int.

So I figured most hashmaps contain fewer than e.g. 2^30 items, so the time complexity will be pretty much O(1), as there are few collisions.

But of course there is a theoretical limit as you described. Just isn't reached much, I thought :-)

Discussion

Do hash tables really help in reducing time complexity ?

Responses(2)

Recent in Forum

Search Hashnode

Do hash tables really help in reducing time complexity ?

Responses(2)

Recent in Forum