CODEWITHSUNDEEP
javahashset
IUnknown
IUnknown

Reputation: 9827

Hashset size operation

How is the size operation of a HashSet constant time operation?
I read that the contains and size operation is constant time.
Although I understand how contains is a constant-time operation, wouldn't size operation be proportionate (not linear) with number of elements?

Upvotes: 1

Views: 742

Answers (2)

David Ehrmann
David Ehrmann

Reputation: 7576

HashSet internally stores how many elements it has.

wouldnt size operation be proportionate(not linear) with number of elements?

If this weren't stored in a field for record keeping, size() would be proportionate to the size of the backing hash table, not the number of elements, since you'd have to scan over all entries to see if something's there. These tend to be the ~same (within 2x), except for when the hash table was either allocated to be significantly too big or a lot of elements were deleted.

Upvotes: 2

Mureinik
Mureinik

Reputation: 311808

The short answer - it's cached.

The longer answer: HashSet is a Set implementation that holds a HashMap, where all the values are the same "dummy value". It's size() method just returns the map's size(). If you look into HashMap's implementation, you'll see it has a size member. Adding elements to the map (e.g., by using put or putAll) increase the size and removing elements from it reduce the size. This way, as size is always kept up to date, it can simply be returned when size() is called, guaranteeing a constant time execution.

Upvotes: 3

Related Questions