충돌 없는 완벽한 해싱이 존재한다고 ? (퍼펙트 해싱 개념 및 사례, 최적화 방법에 대해서)
이 글의 탄생 배경, 이 글에 대해서코딩 스터디 중 해싱 챕터에서 시간 복잡도를 주제로 이야기할 때였다. 해싱하면 연상되는 이미지는 당연히 "빠르다"였고 나는 당연스럽게 O(1)이지! 라고 생각하며 대화를 이어나갔는데, 한 멤버가 질문했다."어... 해싱도 최악의 경우는 O(n) 아니에요?"어라, 순간 멈칫했다. 사실 해싱에서 최악의 경우는 O(n)이라는 걸 깜빡하고 있었다! 자바에서 해싱을 사용할 때는 충돌 문제를 자동으로 처리해주고, 또 key-value 스토어로서 레디스와 같은 저장소를 사용할 때, 단순히 "빠르다"는 이미지에만 노출되어 있다 보니 당연히 해싱은 O(1)이라고 생각했던 것이다. 문득 기억을 환기시키며 깨달았다. 앗,,, 해싱은 충돌이 없다면 O(1)이지만, 충돌이 발생하면 O(n)이..
2024. 11. 2.
