I am writing a generic hash map in C ++ that uses a chain to resolve conflicts.
Let's say if I have a hash map with 11 buckets and I insert 8 elements. The hash function will distribute it as follows:
bucket[0] = empty
bucket[1] = 2 elements
bucket[2] = empty
bucket[3] = 1 element
bucket[4] = 1 element
bucket[5] = 3 elements
bucket[6] = empty
bucket[7] = 1 element
bucket[8] = empty
bucket[9] = empty
bucket[10] = empty
The calculation of the scatter across buckets is 5/8 = 0.625. But how to calculate the spread, taking into account the depth of the buckets?
I want to know this because: Let's say if I added 20 elements, and each bucket has 1 element, and in the last bucket 11 elements.
then the spread will be equal to 1 if I count it in a simple way, but this is obviously not true! (the table is resized to avoid this, of course, but I want to show the distribution). I want to use this information to configure hash functions.
Thanks in advance!