Accidental Quadratic Hashmap Iteration
This post is my own write-up of Rust hash iteration+reinsertion and the related Rust issue/PR, written the way I understood them. The original is the authoritative source, so check it directly for the exact details. I want to walk through an interesting bug that showed up in Rust’s HashMap. The code looks completely ordinary, yet under the right conditions, an operation that should be O(n) blows up to O(n²). Reproducing the Bug Look at the code below. It inserts values 1 through 5,000,000 into a first hash map (one, that’s T1), then iterates over one and reinserts every value into a second hash map (two, that’s T2). Nothing fancy. ...