Maximum size of HashSet, Vector, LinkedList

by

There is no specified maximum size of these structures.

The actual practical size limit is probably somewhere in the region of Integer.MAX_VALUE (i.e. 2147483647, roughly 2 billion elements), as that’s the maximum size of an array in Java.

  • A HashSet uses a HashMap internally, so it has the same maximum size as that
    • A HashMap uses an array which always has a size that is a power of two, so it can be at most 230 = 1073741824 elements big (since the next power of two is bigger than Integer.MAX_VALUE).
    • Normally the number of elements is at most the number of buckets multiplied by the load factor (0.75 by default). However, when the HashMap stops resizing, then it will still allow you to add elements, exploiting the fact that each bucket is managed via a linked list. Therefore the only limit for elements in a HashMap/HashSet is memory.
  • A Vector uses an array internally which has a maximum size of exactly Integer.MAX_VALUE, so it can’t support more than that many elements
  • A LinkedList doesn’t use an array as the underlying storage, so that doesn’t limit the size. It uses a classical doubly linked list structure with no inherent limit, so its size is only bounded by the available memory. Note that a LinkedList will report the size wrongly if it is bigger than Integer.MAX_VALUE, because it uses a int field to store the size and the return type of size() is int as well.

Note that while the Collection API does define how a Collection with more than Integer.MAX_VALUE elements should behave. Most importantly it states this the size() documentation:

If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Note that while HashMap, HashSet and LinkedList seem to support more than Integer.MAX_VALUE elements, none of those implement the size() method in this way (i.e. they simply let the internal size field overflow).

This leads me to believe that other operations also aren’t well-defined in this condition.

So I’d say it’s safe to use those general-purpose collections with up to Integer.MAX_VLAUE elements. If you know that you’ll need to store more than that, then you should switch to dedicated collection implementations that actually support this.

More Related Contents:

  1. How do I remove repeated elements from ArrayList?
  2. What are the reasons why Map.get(Object key) is not (fully) generic
  3. Sorting an ArrayList of objects using a custom sorting order
  4. Why should the interface for a Java class be preferred?
  5. Sorting a collection of objects [duplicate]
  6. How to remove duplicates from a list?
  7. How to convert a Map to List in Java?
  8. Big-O summary for Java Collections Framework implementations? [closed]
  9. Most efficient way to increment a Map value in Java
  10. How to make a new List in Java
  11. Lambda expression to convert array/List of String to array/List of Integers
  12. Combine multiple Collections into a single logical Collection?
  13. Why we can’t do List mylist = ArrayList(); [duplicate]
  14. Java Ordered Map
  15. Difference between Arrays.asList(array) and new ArrayList(Arrays.asList(array))
  16. Map.clear() vs new Map : Which one will be better? [duplicate]
  17. Java – generate Random range of specific numbers without duplication of those numbers – how to?
  18. Iterating through a list in reverse order in java
  19. How to Serialize a list in java?
  20. How to iterate over a PriorityQueue?
  21. How to sort a Collection?
  22. Java Stream: divide into two lists by boolean predicate
  23. Printing HashMap In Java
  24. Is there a no-duplicate List implementation out there?
  25. Rule of thumb for choosing an implementation of a Java Collection?
  26. Java collections convert a string to a list of characters
  27. Arrays.asList give UnsupportedOperationException [duplicate]
  28. Difference between Java Enumeration and Iterator
  29. How to create ArrayList (ArrayList) from array (int[]) in Java
  30. Is there an insertion order preserving Set that also implements List?

Leave a Comment