CODEWITHSUNDEEP
javacollectionshashset
Nilay Dhamecha
Nilay Dhamecha

Reputation: 83

When the initial capacity of the HashSet (i.e 16) gets filled up how is the new capacity is calculated? What is the formula?

When the initial capacity of the HashSet (i.e 16) gets filled up how is the new capacity is calculated? What is the formula?

for example: as the size of array list increases by the formula New capacity = (current capacity * 3/2) + 1

and for vectors it is New capacity = (current capacity * 2)

Upvotes: 9

Views: 10298

Answers (4)

Neha Vari
Neha Vari

Reputation: 492

HashSet is implemented using HashMap, wherein all values of HashMap points to single object and keys of HashMap comprise HashSet Values.

Initial Capacity of HashSet = 16, Load Factor = 0.75, Threshold = 75% of capacity

Which means whenever a new value is added to HashSet, it's size is checked against threshold and if size exceeds threshold HashSet goes for resizing. Resizing makes table size double of current size. Thus, capacity is doubled and threshold is set to 75% of new capacity.

Which indicates whenever size of HashSet equates or goes beyond 75% of its capacity, Resizing occurs.

Upvotes: 1

thegauravmahawar
thegauravmahawar

Reputation: 2823

The HashSet capacity is doubled when the load factor (0.75) is reached.

As the documentation explains:

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

Example:

The initial capacity of HashSet is 16. When the load factor (0.75) is reached, i.e. 16 * 0.75 = 12; on the insertion of the 12th element the capacity is doubled, i.e. it becomes 32.

Upvotes: 11

aditya
aditya

Reputation: 11

As hashset uses hashmap internally so every time it put it will check the threshold of the entry array which is by default 

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

and it resizes it on the load factor 

int capacity = roundUpToPowerOf2(toSize);

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];

Upvotes: 1

Jim Garrison
Jim Garrison

Reputation: 86774

A HashSet is backed by a HashMap. According to grepcode, the size doubles each time an increase is needed. Here's the code for the addEntry method, which is the internal method called to actually add a new entry into the table.

 void addEntry(int hash, K key, V value, int bucketIndex) {
     Entry<K,V> e = table[bucketIndex];
     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
     if (size++ >= threshold)
         resize(2 * table.length);
 }

Note that this is an implementation detail and could change at any time.

Note also that looking at the source should ALWAYS be your first resource when you have questions about how some library class works if the information you need is not in the Javadoc (i.e. an implementation detail).

Upvotes: 0

Related Questions