How do I properly calculate the load factor of a hash table that uses separate chaining?

c++ hashtable hash-collision load-factor
Adam G picture Adam G · Nov 11, 2018 · Viewed 13.7k times · Source

I'm working with hash tables that use separate chaining as a collision resolution technique.

I do know that the general formula is N/table_length, where N is the number of items currently in the table.

I'm a bit confused by the denominator. Would it be the size of the array + the number of chained elements, or simply the size of the array?

Answer

JaMiT picture JaMiT · Nov 12, 2018

The purpose of the load factor is to give an idea of how likely (on average) it is that you will need collision resolution if a new element is added to the table. A collision happens when a new element is assigned a bucket that already has an element. The chance that a given bucket already has an element depends on how many elements are in the container.

load factor = # of elements / # of buckets

(In your terminology: the number of items currently in the table divided by the size of the array.)

Related questions

Simple hashmap implementation in C++

I'm relatively new to C++. In Java, it's easy for me to instantiate and use a hashmap. I'd like to know how to do it in a simple way in C++, since I saw many different implementations and none of …

Read More
Super high performance C/C++ hash map (table, dictionary)

I need to map primitive keys (int, maybe long) to struct values in a high-performance hash map data structure. My program will have a few hundred of these maps, and each map will generally have at most a few thousand …

Read More
Hashtable in C++?

I usually use C++ stdlib map whenever I need to store some data associated with a specific type of value (a key value - e.g. a string or other object). The stdlib map implementation is based on trees which …

Read More