String and Collection Performance
Avoid the handful of string and collection mistakes that turn fast code quadratic or bloat the heap, and know which ones are not worth worrying about.
StringBuilder sb = new StringBuilder(expectedLength);
Set<String> seen = new HashSet<>(values); // O(1) contains
Map<String, User> byId = HashMap.newHashMap(expectedEntries);Most slow Java code is not slow because of the JVM. It is slow because it does far more work than needed, usually inside a loop over request data. A few patterns cause most of it.
Strings
Strings are immutable, so s += x in a loop copies the whole string every time. Building a 5,000-item CSV that way copies millions of characters; the cost grows with the square of the length. Use a StringBuilder, String.join or Collectors.joining.
A single expression such as "id=" + id + ", name=" + name is fine. Since Java 9, javac compiles it to an efficient invokedynamic call, and wrapping it in a StringBuilder by hand gains nothing.
Other common costs: String.format is much slower than concatenation in a hot path; String.split and replaceAll take regular expressions, so compile a Pattern once if you call them per request with a non-trivial pattern; and logging calls that build a message even when the level is off.
Collections
- Lookups in a list.
list.contains(x)checks every element. Calling it inside a loop over another list is quadratic. Put the values you search in aHashSetorHashMapfirst. - Queues on an
ArrayList.remove(0)shifts every remaining element. UseArrayDeque. LinkedList. It is slower thanArrayListandArrayDequefor almost every real workload and uses far more memory per element.- Boxing. A
List<Long>stores a separate object for each value. For millions of numbers, a primitive array such aslong[]is several times smaller and faster to scan. - Bad keys. A
HashMapkey whosehashCodereturns a constant, or whose fields change after insertion, turns lookups slow or loses entries.
Sizing
When you know the final size, say so. new ArrayList<>(n) and new StringBuilder(n) skip repeated growth and copying. For maps, new HashMap<>(n) sets the table capacity, not the number of entries it holds before resizing; HashMap.newHashMap(n), added in Java 19, sizes the map for n entries.
What not to worry about
Do not hand-optimise code you have not measured. Choosing for over a stream, or caching list.size(), rarely shows up next to a database round trip. Find the hot spot with a profiler such as JFR, fix the algorithm, then measure again.
Example
When to use it
- Replace a nested list.contains check in a CSV import with a HashSet so importing 50,000 rows takes seconds instead of minutes.
- Build a large JSON or CSV export with a presized StringBuilder instead of += in a loop.
- Keep a cache of numeric product prices in a primitive array indexed by position to shrink the heap of a pricing service.
More examples
Counting the work in list.contains
The list compares each new address with every one already kept, about half a million comparisons for just 1,000 items, and ten times the items means a hundred times the work. The set jumps straight to a bucket by hash code and only calls equals when hash codes match.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
static long equalsCalls = 0;
record Email(String value) {
@Override
public boolean equals(Object o) {
equalsCalls++;
return o instanceof Email e && e.value.equals(value);
}
@Override
public int hashCode() {
return value.hashCode();
}
}
void main() {
List<Email> incoming = new ArrayList<>();
for (int i = 0; i < 1_000; i++) {
incoming.add(new Email("user" + i + "@example.com"));
}
List<Email> uniqueList = new ArrayList<>();
for (Email e : incoming) {
if (!uniqueList.contains(e)) {
uniqueList.add(e);
}
}
IO.println("list: " + uniqueList.size() + " unique, " + equalsCalls + " equals calls");
equalsCalls = 0;
Set<Email> uniqueSet = new HashSet<>();
for (Email e : incoming) {
uniqueSet.add(e);
}
IO.println("set: " + uniqueSet.size() + " unique, " + equalsCalls + " equals calls");
}
// Output:
// list: 1000 unique, 499500 equals calls
// set: 1000 unique, 0 equals callsPrimitives instead of boxed numbers
The long array holds a million values in 8 MB, while the list needs about 16 bytes per Long object plus 4 bytes per reference, and the values are scattered across the heap. The difference matters for in-memory analytics and caches of numbers, not for a list of twenty DTOs.
import java.util.ArrayList;
import java.util.List;
void main() {
int n = 1_000_000;
List<Long> boxed = new ArrayList<>(n);
for (long i = 0; i < n; i++) {
boxed.add(i); // most values become a separate Long object
}
long boxedSum = 0;
for (Long v : boxed) {
boxedSum += v; // unboxed on every read
}
long[] primitive = new long[n];
for (int i = 0; i < n; i++) {
primitive[i] = i;
}
long primitiveSum = 0;
for (long v : primitive) {
primitiveSum += v;
}
IO.println(boxedSum + " " + primitiveSum);
}
// Output:
// 499999500000 499999500000Presizing and the right queue
Sizing the list and map up front avoids repeated growth and rehashing while loading 10,000 rows. ArrayDeque takes from the front in constant time, where ArrayList.remove(0) shifts every remaining element.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
record User(int id, String name) {}
void main() {
List<User> users = new ArrayList<>(10_000);
for (int i = 0; i < 10_000; i++) {
users.add(new User(i, "user" + i));
}
Map<Integer, User> byId = HashMap.newHashMap(users.size());
for (User u : users) {
byId.put(u.id(), u);
}
IO.println(byId.get(4_242).name());
Deque<String> jobs = new ArrayDeque<>();
jobs.addLast("resize-image");
jobs.addLast("send-email");
jobs.addLast("reindex");
IO.println(jobs.pollFirst() + ", then " + jobs.pollFirst() + ", left " + jobs.size());
}
// Output:
// user4242
// resize-image, then send-email, left 1
Discussion