[14일차] Hash (2)

오늘은 딱히 새로운 내용을 배우진 않았고, 대신 꽤나 큰 문제를 하나 풀었다. 이 문제도 주어진 명세에 맞게 API를 구현하는 문제였다. 데이터베이스를 관리하기 위해 삽입, 삭제, 수정, 검색 기능을 구현해야 했다. 

 

이전까지 이런 유형의 문제는 대부분의 함수는 쉽고 한두 개의 함수들만 빡 어려웠었는데, 아직 내가 해쉬에 익숙하지 않아서인지 이번 문제는 전체적으로 난도가 있었던 것 같다. 해쉬를 잘 관리하는 게 생각보다 쉽지 않았다. 막연하게 당연하지라고 생각했던 사실들을 이 문제를 풀면서 몸소 느꼈다.

 

1. 두 문자열의 해쉬 값이 같다고 해서 둘이 같은 문자열임을 보장할 수는 없다.

=> 그렇다고 충돌이 일어날 때마다 두 문자열을 검사하면 시간 복잡도가 폭발적으로 증가할 수 도 있다. 그래서 대충 맞다고 생각하거나 해쉬 함수를 여러 개 사용한다.

 

2. 해쉬 테이블의 크기가 작으면 시간&공간 복잡도가 감소하지만 답이 나오지 않을 수도 있다.

=> 실제로 이번 문제에서 해쉬 테이블을 2^11으로 잡으면 해결이 안 되는데 2^12으로 두면 문제가 풀렸다. 처음에 문제를 풀었을 때에는 해쉬 테이블의 크기가 2^18였다. 이때는 30MB, 900ms 였는데 2^12로 수정하니 20MB, 600ms로 확 줄어들었다. 

 

3. 원본 값이 수정되면 해쉬 값도 수정된다. 그러면 원본 값을 인덱싱하기 위해 해쉬 테이블도 바뀌어야 한다.

=> 이 부분을 간과하고 거의 두시간을 헤맸다...