자료구조를 배우면서 가장 감명 깊게(?) 배웠던 자료구조가 바로 해시 테이블이라는 자료구조이다. 자료를 빠르고 효율적으로 저장하는 것이 자료구조를 연구하는 가장 큰 이유일 것이다. 자료구조의 효율은 자료구조를 이용하는 대표적인 행동인 "삽입", "검색", "삭제" 등의 시간 복잡도와 공간 복잡도를 계산하고 점근적 표기법을 이용하여 나타내면 된다. (주로 Big O 표기법을 사용한다) 자세한 사항은 여기를 통해 공부하기 바란다. 간단하게 말하면 Big O 안의 식의 미지수가 무한에 가까워질 때 즉, Big O 안에 있는 식의 극한값을 이용하여 효율을 나타내고 비교하게 된다. 보통 시간 복잡도를 이용하여 비교한다.
가장 짧은 시간이 걸리는 자료구조?
지난번에 배웠던 연결 리스트나 스택 같은 자료구조는 삽입하거나 검색을 할 때 시간 복잡도는 O(n)가 된다. 그러면 좀 더 효율적인 알고리즘이 없을까? 마법을 좀 쓰면 O(log n)이나 O(1) 같은 자료구조를 만들 수 있지 않을까? 해시 테이블이라는 자료구조가 바로 해시 함수라는 마법을 사용하여 시간 복잡도를 O(1)로 가지고 있는 자료구조이다. 어떤 마법을 부렸길래 자료의 개수에 상관없는 성능을 가지고 있을까?
해시 테이블 동작 방식
어떤 마법이길래 자료만 던져주면 그 자료가 어디에 있는지 바로 알 수 있는 것일까? 우리가 만약 자료를 찾을 때 그 자료가 정확하기 어디에 있는지 알게 되면 한 번에 자료를 찾을 수 있을 것이다. 해시 테이블은 이런 아이디어를 이용한다. 아래는 전화번호부를 해시 테이블을 이용하여 나타낸 그림이다.
해시 함수(Hash Function)가 이 자료구조의 핵심이다. 전화번호부에서 이름을 해시 함수를 이용하여 숫자화 시키고 그것을 배열의 인덱스(Index)로 사용하여 자료를 저장하는 방식이다. 그러면 이름과 해시 함수만 가지고 원하는 전화번호를 O(1)로 찾을 수 있다!
.
.
.
.
그럴 리가 없다. 해시함수를 어떻게 만드느냐에 따라 결과가 다르겠지만, 만약 "이혜주"라는 이름의 해시값과, "최 일지"라는 이름의 해시값이 같다고 하면 어떤 일이 벌어질까?! 저장소에 "최일지"라는 사람이 없는데도 "이혜주"라는 사람의 전화번호를 알려주게 된다. 그러면 어떻게 해결하면 좋을까? 이런 문제를 <해시 테이블 충돌 문제>라고 부르고 이 문제를 해결하는 방법은 크게 Close-addressing과 Open-addressing으로 나눌 수 있다. 이번 포스팅은 Close-addressing만 다루어 보려 한다. (Open-addressing은 다음 포스팅에....)
Close-addressing 기법
모든 키값을 1:1 대응시킬 수 있는 공간복잡도를 가졌다면 상관없겠지만, 현실은 그럴 수 없다. 따라서 충돌을 해결해야 한다. Close-addressing은 가장 간단한 해결기법으로, 후에 언급할 클러스터링에 거의 영향을 받지 않는다. 간단하게 설명하면, 주소(인덱스)를 변경하지 않는 방법이다. 만약 "이혜주"의 전화번호를 저장하고, "최일지"라는 사람을 저장하려 할 때 이미 주소가 겹쳐 충돌이 일어난다면 "이혜주"의 전화번호부 뒤에 연결 리스트처럼 이어나가는 방법이다. (Chaining 이라 고도한다.)
이 방법은 연결 리스트(Linked List)를 이용하여 쉽게 구현할 수 있다.
소스 코드
정말 옛날에 작성해서그런지 주석이 친절치 못하다... 좀 길지만, 간단하게 설명하자면 기본적으로 연결 리스트(Linked List)를 활용하였다. 그리고, Chained_Hash 클래스에 (이때는 클래스 이름도 지금 컨벤션이 아니네...) 테이블을 연결 리스트의 배열로 생성하고 있다. Main을 살펴보면, 테이블을 32크기로 생성하고 랜덤 숫자를 삽입, 삭제, 검색하고있다. 핵심은 Chained_Hash의 insert 메소드이다. 해시 함수로 인덱스를 구하고 해당 인덱스의 연결 리스트에 자료를 추가하고있다.