2cb9d434abc236a14e81d2b628f1716ae92a


해시테이블에서 해시 충돌은 피할 수 없다. 메모리는 한정돼있고 도메인은 그거보다 크기 때문.


이를 해결하기 위한 방법이 크게 두가지가 있는데


1. 오픈어드레싱 (잘안씀)

2. 체이닝

이 있다


오픈어드레싱엔 linear probing, quadratic probing, double hashing 등이 있다


linear probing은 단순히 한칸 다음에 넣는것임


어 해시 이미 쓰고있네? (=충돌) -> 다음칸. 다음칸도 쓰고 있다? 그럼 또 다음칸 (=무지성 프로빙)


quadratic도 이거랑 비슷한건데 아마 1+2+4+... 이런식으로 다음칸 움직였던걸로 기억함


더블해싱은 충돌났을때 hash(hash(x)) 이렇게 한번 더 돌리는거



오픈어드레싱의 문제는 충돌나서 다른곳에 처 넣었는데


이전값을 지우면 어떻게 하냐는것



그래서 그냥 충돌나면 버킷에 링크드리스트나 기타등의 방식으로 그 버킷에 값을 묶어놓는걸 체이닝이라고 한다


재수없어서 값들이 해시값이 다 0이어서 리스트로 쭉 매달리면 해시테이블 쓰는 의미가 없음 


그래서 버킷용량 일정량 넘어가면 rehash, 버킷 사이즈 조정하는 방식 등이 있음



C++ std::unordered_map 이 이런식으로 구현돼있음