educative.io

Hash table overhead

Courses
,
#1

Hi there!!

In the Designing API rate limiter, Sliding Window Algorithm, they talk about hash table overhead of 20 bytes.
Can somebody explain where this memory (20 bytes) would be consumed?
Similarly there is sorted set overhead of 20 bytes. Where in sorted set this memory would be consumed?

Thanks.
Regards.

#2

Hello @Ashish_Srivastava
This memory would be consumed when we need to store all of the user data for the sliding window. Overhead of 20 bytes means that we are reserving 20 bytes overhead per element for hash table and for the sorted set as well.

Hope it will help, Happy learning :slight_smile:

1 Like
#3

@Muntha_Amjad Can you please clarify more? We are reserving 20 bytes for hashtable and 20 bytes for sorted set, but I am still not clear why we are reserving. Is it for pointers or some other data type?

#4

@Ashish_Srivastava
We have two pointers to maintain order among elements. One pointer to the previous element and one to the next element. On a 64bit machine, each pointer will cost 8 bytes. So we will need 16 bytes for pointers. We added an extra word (4 bytes) for storing other overhead. So overall we are reserving 20 bytes (16+4).

Hope it will help, Happy learning :slight_smile: