공부리뷰 #해쉬테이블

항상 C#의 딕셔너리를 쓸때 Key, value 면 분명 내부는 해시로 되어있을텐데

어떻게 구현되어있을까 궁금한김에 알고리즘 책을 다시 폈다. 학부때 주의 깊게 안보기도 했고

지금처럼 현업에서 알고리즘과 자료구조에 대해 많이 알때 유리한점을 그때는 인지하지 못해서 관심도 깊게 두지 않았다.

그리고 가장큰 문제는 탑코더를 풀다가 막혔다는 것이다. 아.... 일단 문제를 어떻게 풀어야할지 방법조차 생각이 안난다.

그래서 기초를 다시한다.

어찌되었든, 해쉬함수는 소수가 필요하다 그리고 클러스터(Mod를 해도 같은 주소값을 나타내는 경우 충돌)를 방지하거나

여러방법들이 책들에 있었다. 

책은 학부때 봤던책 그대로 

'뇌를 자극하는 알고리즘', 박상현, 한빛미디어, 2012년2월10일 (오탈자가 좀 있긴한데 인터넷에 나와있어 고치면서했다)

순서는 

체이닝 - 해당 주소에 같은 연산주소값이 있을경우 링크드 리스트로 연결하는것 

단점 : 값 찾을때 순차탐색을 한다.. 이러면 해시쓰는 이유가 없다

보완 : 이진탐색트리, 레드블랙트리를 쓴다

개방주소법 - 고정폭으로 다음주소로 이동하는것, 선형탐사 제곱탐사

단점 : 클러스터가 발생하는것은 여전히 막을수 없다.

보완 : 2중 해싱 - 1차 해시함수로 나온주소값에 이미 값이 있다면 2차 해시 함수의 결과값에 저장한다.