CODEWITHSUNDEEP
javahashmap
auser
auser

Reputation: 7497

Other than heap size what would limit the number of elements a HashMap can hold

As per the title - what constrains the number of elements a HashMap can hold and what data structure could be used instead.

Upvotes: 0

Views: 142

Answers (6)

Jared Russell
Jared Russell

Reputation: 11342

With the exception of the heap size that you've already mentioned I do not believe there are any hard limits on the number of items you can place into a HashMap.

Internally HashMaps have an array of 'buckets', with each bucket being a linked list. When you add an item it is hashed to find the correct bucket, and is then added to the front of that linked list. As such, even if every bucket has one item in it, adding one more item will simply add the item to the linked list in the bucket.

The behaviour I've described above is the implementation of the HashMap class that comes with the Oracle JRE and may differ on other platforms, and so other platforms may have limitations on the number of items that can be placed into them.

It is also worth pointing out that if you are putting more than Integer.MAX_VALUE items into a HashMap, the lookup performance will degrade considerably because the HashMap will have to iterate over the list when trying to find the item.

Upvotes: 0

CodeBlind
CodeBlind

Reputation: 4569

The HashMap data structure is backed by an array for the hashtable under the hood. Because Java array sizes must be specified using integers, they are limited in size to Integer.MAX_VALUE (about 2 billion elements).

If constant-time lookups of more elements are necessary, I suppose you could wrap nested HashMaps in your own class definition, but you're also going to have to get around the fact that Java's Collection interface specifies an int size value - in a nutshell, it's possible to have a data structure that stores more than Integer.MAX_VALUE elements, but this is not truly supported by anything in the Collection interface.

Upvotes: 0

Johan Sjöberg
Johan Sjöberg

Reputation: 49187

One thing is the maximum array size, which in Java is Integer.MAX_VALUE.

If that's a limit to you, then you could create your own class which wraps a list of HashMap objects or use a LinkedHashMap.

Upvotes: 1

Daniel Mühlbachler-P.
Daniel Mühlbachler-P.

Reputation: 675

I don't really think there are limitations.

Firstly, an object's hashCode will fit always in the maximum array size as the largest int value gives the maximum array size.

Secondly, afaik a HashMap uses lists for their keys. Therefore, if two keys have the same hashCode (which may happen even if you insert only some values) they will be inserted anyway. Since a list can get as long as you want there are no real limitations besides the efficiency of it.

Upvotes: 0

Keith Randall
Keith Randall

Reputation: 23265

The fact that hashCode returns an int instead of a long also prevents HashMap from being efficient much beyond 2^32 entries.

Upvotes: 2

CrazyCasta
CrazyCasta

Reputation: 28302

The only constraint would be array size (2^31-1) and the number of unique values possible for your key type.

Upvotes: 0

Related Questions