해시맵 쓰면 조회가 O(1)이라 빠르다고 해서 그냥 편하게 쓰고 있었는데, 얼마 전에 최악의 경우엔 O(n)까지 느려질 수 있다는 얘기를 듣고 좀 혼란스러워졌어요. O(1)이라며 왜 O(n)이 되는 건지.
제가 이해하기론 키를 해시 함수에 넣으면 배열 인덱스 같은 게 나오고, 거기다 값을 저장한다 이 정도인데,
index = hash(key) % 배열크기
table[index] = value
여기서 서로 다른 키인데 index가 똑같이 나오면 어떻게 되는 거예요? 그게 충돌이라는 건 알겠는데 그럼 먼저 있던 값은 덮어씌워지는 건 아닐 테고, 어떻게 둘 다 저장하고 나중에 제대로 찾아오는 건지 궁금해요.
정리하면,
1. 충돌 나면 값을 실제로 어떻게 저장하나요? 방법이 여러 개인가요
2. 어떤 상황에서 O(n)까지 느려지는 거예요
3. 실무에서 그 최악 경우를 걱정해야 될 정도인가요 아니면 그냥 써도 되나요
평소엔 아무 생각 없이 썼는데 원리를 알고 나니까 좀 무서워졌네요. 설명 부탁드립니다.