Comment by Mark on "Do hash tables really help in reducing time complexity ?"

CommentDo hash tables really help in reducing time complexity ?

Mark

May 23, 2019

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?

PRASHANTH H N

Software Developer

May 24, 2019

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 :-)

Search Hashnode