해시 테이블 [Hash table] Part 2 : 빠르게 자료 넣고 찾자
2016. 8. 3.
지난번 포스팅까지는 해시 테이블에 대한 소개와 동작 방식, 충돌 문제를 해결하는 방법으로 Close-Addressing 기법인 Chaining을 소개했다. 이번 포스팅에서는 Open-Addressing 기법에 속하는 3가지 방법을 소개하고, 지금까지 소개했던 해결법들을 간단하게 비교해 본 뒤 해시 테이블의 장단점을 정리해 보도록 하려 한다. Open-Addressing?! Open-Addressing 기법은 해시 함수로 얻어낸 주소를 그대로 이용하지 않고 상황에 따라 변경할 수 있는 기법이다. 물론 추적 가능하게 변형하는 기법을 사용한다. 이 기법을 사용하면 Close-Addressing에서는 보지 못했던 "클러스터링 문제"가 발생하게 되고 클러스터가 많이, 크게 일어나면 성능상 문제가 생기기 때문에 그..