Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

When constructing a HashSet, does the capacity argument take the load factor into account?

The .NET API gives the following remarks for the HashSet<T>(Int32) constructor:

Since resizes are relatively expensive (require rehashing), this attempts to minimize the need to resize by setting the initial capacity based on the value of the capacity [argument].

The phrase based on the value gives me faith that the constructor does something smarter than simply setting the underlying array capacity to capacity. But will I be guaranteed to be able to add capacity items to the set with no resize?

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

The underlying load factor is of course an implementation detail. I checked if it is exposed by any API method, and it apparently isn’t. So hopefully .NET is using its knowledge of the load factor the way I want it to in this constructor.

>Solution :

The implementation can be seen on GitHub by clicking the source link in the docs.

After skipping through a few method calls, and a guard where it throws if capacity < 1, we get to the interesting part.

/// <summary>
/// Initializes buckets and slots arrays. Uses suggested capacity by finding next prime
/// greater than or equal to capacity.
/// </summary>
private int Initialize(int capacity) {
  int size = HashHelpers.GetPrime(capacity);

So, it does not directly use the load factor in the calculation, but using the next prime instead is still a pretty desirable implementation, as discussed here.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading