---
title: "Comment by Mark on \"Do hash tables really help in reducing time complexity ?\" | Hashnode"
description: "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, woul"
url: "https://hashnode.com/posts/do-hash-tables-really-help-in-reducing-time-complexity/5ce6c3624accb1d47e53e58d/comment/5ce6d84ad7f87f143decb763"
---

[Discussion](https://hashnode.com/posts/do-hash-tables-really-help-in-reducing-time-complexity/5ce6c3624accb1d47e53e58d)

Comment [Do hash tables really help in reducing time complexity ?](https://hashnode.com/posts/do-hash-tables-really-help-in-reducing-time-complexity/5ce6c3624accb1d47e53e58d)

[Mark](https://hashnode.com/@mverleg)

[May 23, 2019](https://hashnode.com/posts/do-hash-tables-really-help-in-reducing-time-complexity/5ce6c3624accb1d47e53e58d/comment/5ce6d84ad7f87f143decb763)

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](https://hashnode.com/@prahashnode)

[May 24, 2019](https://hashnode.com/posts/do-hash-tables-really-help-in-reducing-time-complexity/5ce6c3624accb1d47e53e58d/comment/5ce6d84ad7f87f143decb763#reply-5ce75c57336a99f7673f8dd5)

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?".

[Mark](https://hashnode.com/@mverleg)

[May 24, 2019](https://hashnode.com/posts/do-hash-tables-really-help-in-reducing-time-complexity/5ce6c3624accb1d47e53e58d/comment/5ce6d84ad7f87f143decb763#reply-5ce79560f3a1c5da1bd5f32a)

[PRASHANTH H N](https://hashnode.com/@prahashnode) 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 :-)