지금까지 배웠고 또 앞으로 배울 검색 알고리즘들은 모두 자료수 N이 커지면 검색 시간도 더 걸리는 성능을 보여줍니다. 또한 이것이 자연스럽습니다. 이들 알고리즘들은 O(N) 혹은 O(logN)의 성능을 보여 줍니다.그런데 오늘 배울 검색 알고리즘인 해쉬(Hash)는 자료수 N과 무관하게 일정한 검색 성능을 보여줍니다. O(1)의 성능입니다. 실로 놀라운 검색 알고리즘입니다. 그런데 알고보면 그 원리는 매우 간단합니다.
입력된 자료가 수치형이든, 스트링이든, 복합 데이터 타입이든 그것을 정수로 변환하는 함수만 정의하면 됩니다. 이 함수를 해쉬 함수라 하며, 입력 자료를 해쉬 함수에 넣어 나온 결과를 해쉬값이라고 합니다.
입력자료에 대해 고른 분포의 해쉬값이 나오는 해쉬함수가 있다면 매우 효율이 높은 해쉬 검색을 구현할 수 있습니다. 하지만 이런 이상적인 경우는 현실에 존재하지 않기 때문에 다른 입력자료가 같은 해쉬값이 나오는 경우가 빈번하게 발생합니다.
이에 대한 대처 방법은 여러가지가 있지만 여기서는 선형탑사법(Linear Probing)법과 연결법(Separate Chaining)에 대해서 살펴볼 것입니다.
해쉬는 단순하지만 검색 성능이 매우 좋기 때문에 실제 업무에서도 매우 사용빈도가 높은 검색구조이므로 그 원리와 구현에 대해 확실히 알아두는 것이 좋습니다.
강의 자료
강의 동영상
16.0 해쉬(Hash) - 시작 : 해쉬는 단순하면서도 매우 효율적인 검색법으로 실제 여러분야에서 많이 쓰입니다. 입력되는 데이터를 잘 분산시킬 수 있는 해쉬함수를 만드는 것이 핵심입니다. 해쉬에 대해서 자세히 알아봅니다.
16.1 해쉬의 개념 : 해쉬의 핵심은 해쉬 함수(Hash Function)입니다. 해쉬 함수는 입력된 키를 수치로 변환하는 함수로서 고른 분포로 분산되어야 좋습니다. 입력된 키에 대응하는 위치를 해쉬 함수로 단번에 알아내기 때문에 검색 성능은 이론적으로 O(1) 즉 상수입니다. 이렇게 좋은 해쉬의 단점이라면 충분한 메모리 공간이 필요하다는 점과 충돌이 발생할 수 있다는 점입니다.
16.2 선형탐사법의 개념 : 해쉬의 충돌을 해결하는 방법은 여러가지 있습니다. 그 중 가장 단순한 것은 충돌했을때 다시 다른 빈 곳을 찾는 것으로 이를 오픈 어드레싱(Open Addressing)이라고 합니다. 오픈 어드레싱 중에서 충돌된 곳에서 가장 가까운 빈 곳을 찾는 방법을 선형탐사법(Linear Probing)이라고 합니다. 이 절에서는 선형탐사법의 개념과 한계를 알아보고 개선법도 알아봅니다.
16.3 선형탐사법의 구현 : Java의 경우 검색 구조에서 해쉬를 사용한 HashMap이라는 클래스를 제공합니다. C++로 비슷하게 만들어 봅니다.
16.4 HashMap 사용법 : 앞서 만든 HashMap 클래스는 실전에서 유용하게 쓰일 수 있습니다. HashMap 클래스를 사용하는 방법에 대해 알아봅니다.
16.5 연결법(Separate Chaining)의 개념 : 선형탐사법은 해쉬 함수가 입력 데이터를 잘 흩어주지 못하거나, 메모리 공간에 제약이 있을 경우 충돌이 빈번히 발생해 효율이 떨어집니다. 이를 개선하기 위해 해쉬 테이블의 각 항목을 연결리스트로 만든 것이 "연결법(Separate Chaining)"입니다. 연결법의 개념에 대해 알아봅니다.
16.6 연결법의 구현 : 앞서 연결리스트에 대해 구현해 보았으므로, 해쉬 연결법의 구현은 매우 쉽습니다. 코드를 재사용하는 쾌감을 느낄 수 있습니다.
16.7 해쉬 비교 분석 : 해쉬를 구현하는 방법으로 선형탐사법과 연결법 두가지를 살펴 보았습니다. 이 두 방법에 대해 공간복잡도와 시간복잡도를 분석해 봅니다.
16.9 해쉬(Hash) - 결론 : 살펴 보았듯이 해쉬는 간단하면서도 매우 효율적인 검색 구조입니다. 이 장에서 배웠던 내용을 정리해 봅니다.
관련글 |
- C++로 배우는 알고리즘
- 15장 : 이진트리 검색 (Binary Tree Search)
- 17장 : 기수 검색 (Radix Search)
댓글 없음:
댓글 쓰기