Rust

이 글은 Rust hash iteration+reinsertion 글과 관련 Rust 이슈/PR을 제가 이해한 대로 정리한 글입니다. 원문이 정확한 소스이니, 정확한 내용은 원문을 확인해주세요. Rust의 HashMap에서 발생했던 흥미로운 버그를 하나 소개하려고 합니다. 겉보기에는 지극히 평범한 코드인데, 특정 조건이 갖춰지면 O(n)이어야 할 연산이 O(n²)으로 폭발합니다. 버그 재현 다음 코드를 보겠습니다. 첫 번째 해시맵(one)에 1부터 5,000,000까지의 값을 삽입한 뒤(T1), 그 해시맵을 순회하면서 두 번째 해시맵(two)에 값을 그대로 재삽입(T2)하는 것이 전부입니다. use std::collections::hash_set::HashSet; fn main() { println!("inserting..."); let mut one = HashSet::new(); for i in 1..5000000 { one.insert(i); } println!("reinserting..."); let mut two = HashSet::new(); for v in one { two.insert(v); } } T1과 T2 모두 원소를 하나씩 삽입하는 동작이니, 둘 다 O(n)이어야 할 것 같습니다. 그런데 실제로 실행해보면 T1은 예상대로 O(n)에 끝나지만, T2는 O(n²)에 가까운 시간이 걸립니다. 같은 일을 하는 코드인데 왜 이런 차이가 발생할까요? ...