개요일반적으로, 우리는 자바 HashMap이 평균적으로 O(1)의 시간 복잡도를 가진다고 배웁니다. 하지만 “해시 충돌(Hash Collision)”이 심해지면 성능이 급격히 떨어질 수 있다는 사실은 자칫 놓치기 쉽습니다. 또한, CPU 캐시 구조와 “참조 지역성(Reference Locality)”을 이해하면, 왜 이 문제가 현실에서 더 크게 체감되는지 알 수 있습니다. 이 주제는 백준 7453 번 문제를 풀다가 경험하게 되었는데https://www.acmicpc.net/problem/7453 C++,C 에서는 기존의 방법처럼 2개씩 쌍으로 묶어서 계산한다음에 한쪽 값을 해시 맵에 넣어두고 0을 만들기 위한 보수가 존재하는지 hash key 탐색으로 풀렸지만 자바의 경우에는 그렇지 않았다. 탐색 길이인..
