What they're testing
Whether you think of complexity as an attack surface. This is where algorithms meet security.
The short answer~30 seconds
If the hash function has no secret key, an attacker can precompute thousands of strings landing in one bucket, send them as JSON keys, and each insert walks that bucket's whole chain — O(n²) for a single request. This is hash flooding, and it took down a swathe of web frameworks in 2011. Defences: a keyed hash randomised per process (SipHash), a cap on key count in the body, and a body size limit.
The long answer
The important part is why converting to a tree is a security measure rather than only a performance one. Java's HashMap since 8 treeifies long buckets, taking the worst case from O(n) to O(log n) — the attack cost rises sharply while the ordinary cost is unchanged. But it only works when the keys are Comparable; with non-comparable keys it stays a list.
The same shape of vulnerability appears elsewhere under other names: ReDoS is a regex that backtracks exponentially on user input; a zip bomb is a compression ratio; billion laughs is nested XML entities. The common pattern is "small input, large work", and the common defence is a hard limit at the BOUNDARY rather than trusting the data to be reasonable.
What they'll ask next
?How do you find ReDoS in an existing codebase?
Look for nested quantified groups ((a+)+, (\s*)*) applied to user input — that shape is nearly always exponentially backtrackable. Tools like safe-regex catch most of them; beyond that, a match timeout is the last line of defence.
These lose points
- Treating average complexity as sufficient when the input is externally controlled. With adversarial data, the worst case is the normal case.