해시 테이블은 궁극의 탐색 알고리즘이라고 불린다. 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해싱(hashing)하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것이 기본적인 컨셉이다. 해시 테이블은 한마디로 공간을 팔아 성능을 얻어내는 것이다. 해시값으로의 접근은 다음과 같은 방식으로 이루어진다.
Table[3819] = 123817;
데이터는 해시 함수를 거치면 다음 그림처럼 테이블 내의 주소(즉, 인덱스)로 변환된다.
해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다. 그렇지 않으면, collision 현상이 발생한다. 통계적으로 해시 테이블의 공간 사용률이 70%~80%에 이르면 성능 저하가 나타나기 시작한다.
다른 배열 형식의 자료 구조와 비교해 볼 때, 해쉬 테이블은 많은 수의 자료가 저장될 때 좀 더 유용하며 데이터 셋의 크기를 예측할 수 있을 때 더욱 유용하다.
용어정리
- Collision(충돌) : 서로 다른 입력 값에 대해 동일한 해시 값, 즉 해시 테이블 내의 동일한 인덱스 값(주소)을 반환하는 것을 말한다. 어떤 해시 함수든, 그 알고리즘이 아무리 정교하게 설계되었다 하더라도 모든 입력 값에 대해 고유한 해시 값을 만들지는 못한다. 한마디로 말해서, 해시 함수의 충돌은 피할 수 없다.
- Cluster(클러스터) : 일부 지역의 주소들을 집중적으로 반환하는 것을 말한다. 그 결과 데이터들이 한 곳에 모이게 되는 문제가 발생한다. 배열과 비슷하게, 해쉬 테이블은 평균적으로, 테이블 내 아이템의 수와 상관없이 O(1)의 상수 시간 복잡도를 제공하지만, 최악의 경우 검색 시간이 O(n)으로 나빠질 수도 있다. 해쉬 테이블의 검색 성능은 해쉬 함수의 성능과 해쉬 테이블의 크기에 좌우된다. 충돌이 발생하면 할 수록 성능은 점점 O(n)에 가까워지므로 충돌을 최대한 억제시키는 것이 해쉬에서 가장 중요한 이슈다.
좋은 해쉬 함수라는 것은 해쉬 테이블 성능을 많이 향상시킨다는 의미다. 질 낮은 해쉬 함수는 데이터들의 key를 같은 bucket으로 유도하는 경우가 많다. 그럼 충돌이 증가하고 이는 곧 심각한 해쉬 테이블의 성능 저하로 이어지게 된다. 물론 어떤 구현으로도 충돌을 완전히 피할 수는 없다.
해시(Hash)는 자료를 입력할 때부터 검색하기 쉬운 위치에 삽입하는 방법이기 때문에 검색 방법이라기보다는 빠른 검색을 위해 자료를 관리하는 기법이라고 볼 수 있다. 실생활에서도 해시 기법이 흔히 사용된다. 수첩에 주소록을 작성할 때 가나다순으로 페이지를 미리 분류하고 이름의 첫 글자를 기준으로 주소를 적는 방법이 일종의 해싱이다. 수첩에 아무렇게나 주소를 적어 놓으면, 새 주소를 추가하기는 편해도 찾기가 무척 어려워진다. 하지만 성별로 분류해 놓는 식으로 미리 고유값을 규칙/약속으로 정해놓으면, 처음에 제 위치를 찾아 적기는 좀 귀찮더라도 추후에 필요할 때 빠르게 찾기는 아주 쉬워진다. 이런 검색 방법이 바로 해싱이다.
이 때, 자료가 저장되는 전체 저장소를 해시 테이블(Hash Table)이라고 한다. 해시 테이블은 여러 개의 버킷(Bucket)으로 나누어지는데 주소록을 다시 예로 들면, ㄱ, ㄴ, ㄷ, ㄹ 각 페이지가 버킷이라고 할 수 있다. 데이터를 삽입할 때 데이터의 값으로부터 적절한 버킷을 선택하게 되고, 값을 삽입한다. 버킷은 또한 여러 개의 슬롯(Slot)으로 구성된다. 슬롯이란 버킷에 데이터가 저장되는 단위를 말한다. 주소록의 각 페이지별로 한 명만 적는 것은 아닐 것이다. 여러 명을 적을 수 있어야 하는데, 이 때 한 명 분의 주소를 적는 칸이 일종의 슬롯이다.
해싱의 가장 기초적인 연산은 당연하게도, 자료가 새로 입력될 때 이 자료를 어떤 버킷에 넣을지를 결정하는 것일 것이다. 이 연산을 하는 함수를 해시 함수라고 한다. 해시 함수는 입력된 키값으로 버킷의 번호(해시값)를 찾아내는 함수인데 새로 자료를 삽입할 때 해시 함수가 리턴하는 버킷 번호에 자료를 삽입한다. 다음에 특정 자료를 검색할 때는 다시 해시 함수로 버킷 번호를 찾아 여기에 원하는 자료가 있는지를 보면 된다.
다음은 해시의 기본 동작 원리를 보여주는 아주 간단한 예제다. 해시에 들어가는 수가 양의 정수 뿐이라고 가정하고, 0은 버킷이 비어 있음을 의미하는 값으로 사용한다.
1번째 값을 입력하세요 : 7
2번째 값을 입력하세요 : 28
3번째 값을 입력하세요 : 942
4번째 값을 입력하세요 : 69
5번째 값을 입력하세요 : 33
검색할 키를 입력하세요 : 28
검색되었습니다.- hash 함수 : 10으로 나눈 나머지를 해시값으로 선택하므로 버킷은 10개를 준비하면 된다.
- AddKey 함수 : 입력된 키로부터 hash 함수를 호출하여 해시값을 찾고 이 버킷이 비어 있을 때 해시 테이블에 데이터를 추가한다. 만약 이미 버킷이 점령되어 있다면 값을 추가할 수 없다.
- FindKey 함수 : 키가 해시 테이블에 있는지만 조사한다. 이 때 해시값을 먼저 찾고 버킷에 들어있는 값과 키값을 비교한 결과를 리턴한다. 존재 여부만을 조사하도록 했는데 실제 예에서는 키가 들어있는 버킷과 슬롯 번호를 리턴하는 것이 더 실용적이다.
- main 함수 : 해시 테이블을 0으로 모두 초기화하여 비운다. 만약 이 테이블에 0도 입력될 수 있다면 -1 등의 다른 특이값으로 초기화해야 한다. 그리고 다섯 개의 값을 입력받아 해시 테이블에 추가하고 검색할 키를 입력받은 후 FindKey 함수로 이 값이 해시 테이블에 들어 있는지 조사한다.
해시 테이블이 아무리 크고 데이터가 많다 하더라도 검색 시간은 상수로 항상 일정하다. 검색 시간으로만 본다면 해시는 모든 검색 알고리즘 중에 가장 빠르다고 할 수 있다.
물론 언급했듯이 해싱도 여러 가지 문제점이 있다. 가장 큰 문제는 버킷끼리 충돌할 수 있다는 점이다. 새로 삽입하고자 하는 키의 버킷이 이미 점령되어 있다면 이 키는 해시 테이블에 추가할 수 없게 된다. 예를 들어 38이 8번 버킷에 이미 들어 있을 때 48이나 58이 입력되면 이 값을 저장할 버킷이 없게 된다. 버킷이 이미 점령되어 값을 추가할 수 없는 상황을 충돌(Collision)이라고 위에서 정의했다. 이 충돌을 어떻게 해결할 것인가가 결국 해싱 알고리즘의의 관건이다.
어떻게 해결할까? 슬롯을 충분히 크게 잡기만 해도 충돌을 많이 완화시킬 수 있다. 버킷의 슬롯이 커지면 설사 충돌이 발생하더라도 다음 슬롯에 데이터를 저장할 수 있기 때문이다. 이 때부터는, 슬롯 크기를 초과하는 데이터가 입력될 때 경우에 문제가 발생하게 된다. 슬롯 크기를 늘리면 데이터를 추가 및 검색하는 함수도 다중 슬롯을 지원하도록 수정해야 할 것이다.
- AddKey 함수 : 일단 해시값을 찾은 후 슬롯 크기만큼 루프를 돌며 빈 자리를 찾아 새로운 키를 삽입한다. 버킷에 이미 값이 들어 있더라도 여유 슬롯이 있다면 이 슬롯에 새 데이터를 추가할 수 있게 된다.
위와 같이 구현하면, 데이터가 한 곳에 몰리더라도 슬롯이 충분하다는 가정 하에, 일단은 충돌을 방지할 수 있다. 빈 슬롯이 하나도 없다면 이때는 삽입에 실패하며 여전히 충돌이 발생하게 된다. 결국 다중 슬롯은 충돌을 지연시키기는 정도이다. 완벽하게 충돌을 예방하지는 못한다. 게다가 슬롯이 많아지면 추가, 검색 함수가 복잡해진다. 때문에 실제 해싱을 할 때는 슬롯은 하나만 쓰고 다른 방법을 사용하는 것이 더 일반적이다.
해시 테이블이 아무리 커도 충돌은 발생할 수 있다고 했다. 이 충돌을 가급적 늦추고 버킷을 골고루 사용하려면 키로부터 해시값을 찾는 해시 함수가 정교해야만 한다. 제일 단순한 방법은 나머지 연산자인 %연산자로 끝 자리만 보는 방법이 있다. 이 나머지 연산자로는 균일한 해시값을 만들어 내는데에 한계가 있다.
예를 들어, 해시 테이블에 저장되는 데이터가 '점수'라고 해보자. 문제가 100개가 아닌 한, 점수는 보통 1단위인 경우보다 2나 4단위인 경우가 상대적으로 더 많을 것이다. 이렇게 되면 짝수 버킷에만 데이터가 몰리게 될 것이고 홀수 버킷은 텅텅 빌 것이다. 결국 금새 충돌이 발생할 것이다. 뿐만 아니라 기억 장소도 낭비된다. 이런 케이스는, 십자리와 일자리를 더해 나머지 연산을 적용하는 등으로 조금 꼬기만 해도 훨씬 더 균일한 해시값을 얻을 수 있게 된다.
다른 예로, 주소록이 있다. 첫 글자의 자음을 해시값으로 쓰겠다고 정하면 ㄱ, ㅂ, ㅇ 버킷은 금방 바닥나고 ㄹ, ㅋ, ㅌ 버킷은 남아돌게 된다. 첫 글자의 자음보다는 중간 글자의 자음을 보는 방법이 더 나을 수 있다.
바람직한 해시 함수라면, 값이 한 곳에 몰리지 않고 골고루 퍼지도록, 입력되는 임의의 값으로부터 균일한 해시값을 만들어 낼 수 있어야 한다. 또한 삽입과 검색 속도에 직접적인 영향을 미치므로 너무 복잡해서도 안 된다. 또한 해시값을 신속하게 계산해 낼 수 있어야 한다. 유일한 해시값을 만들어내기 위해서 해시값을 오랜 시간 계산하면 그것은 그것대로 곤란하다. 해시 함수를 만드는 여러 가지 연산 방법들은 이미 개발되어 있다. 입력값을 제곱한다거나 쉬프트, 비트 연산으로 일부 비트만 취하는 간단한 방법에서부터, 입력되는 값들의 분산, 표준 편차 등을 활용하는 수학적인 방법도 있다. 더하고 곱하고 나누고 돌리고 비틀고 꼬고 어찌하든간에 허용 범위 시간 내에서 균일한 해시값을 리턴해 낼 수만 있으면 된다. 이를 위해서는 결국 도메인에 대한 이해를 바탕으로, 저장하는 값의 성질을 잘 분석한 후에 해시값들을 골고루 분산시킬 수 있는 방법을 찾아야 한다.
하지만 슬롯이 넉넉하고 해시 함수가 아무리 정교해도 충돌은 언제나 발생할 가능성이 있다. 그래서 충돌이 발생할 때의 대처 상황을 정의해야 하는데 선형 탐색법이 그 중 가장 간단한 방법이다. 선형 탐색법(Linear Probing)이란 충돌이 발생할 경우 이 데이터를 버리지 않고 다른 버킷에라도 대신 집어 넣는 방법이다. 즉, 꿩 대신 닭을 찾는 방법인데 그렇다고 해서 아무 곳에나 넣어서는 안되며 검색 함수가 찾을 수 있는 곳에 넣어야 한다.
대체할 버킷을 찾는 가장 간단한 방법은 충돌이 일어난, 혹은 슬롯이 가득차서 넣을 수 없는 칸의 바로 옆칸에 넣는 것이다. 그러면 검색 함수가 버킷에서 찾지 못했을 때 옆칸을 살펴보게 된다. 주소록의 경우, ㄱ칸이 모자라면 ㄴ칸을 잠시 빌려 쓸 수 있는 식이다. 이 때, 반드시 옆칸에 적어야지 ㅋ, ㅌ같은 엉뚱한 곳에 적어 놓으면 허용 범위 내에서의 검색은 거의 불가능해질 것이다.
1번째 값을 입력하세요 : 11
2번째 값을 입력하세요 : 12
3번째 값을 입력하세요 : 22
4번째 값을 입력하세요 : 66
5번째 값을 입력하세요 : 77
검색할 키를 입력하세요 : 22
검색되었습니다.-
AddKey 함수 : 입력된 데이터의 버킷 번호를 조사하여 여기에 데이터를 넣되 만약 이 버킷이 비어 있지 않다면 다음 버킷을 조사한다. 만약 다음 버킷도 비어 있지 않다면 그 다음 빈 버킷을 계속해서 찾아 최초로 빈 버킷에 값을 써 넣게된다.
AddKey 함수는 이런 식으로 충돌 발생시 단순히 그 다음 칸을 사용한다. 만약 빈 칸이 하나도 없다면 무한 루프에 빠져 버리는 문제가 있는데 이 문제는 최초 버킷을 기억했다가 이 자리로 다시 돌아 왔을 때 에러를 처리하게 함으로써 해결할 수 있긴 하다. 그러나 무한 루프만 해결했을 뿐이지 데이터 삽입은 실패하는 것이므로 해시 테이블을 더 크게 만들거나 아니면 해시 테이블보다 더 많은 자료를 삽입하지 않도록 하는 것이 맞다.
-
FindKey 함수 : 특정 키가 있는지 검사할 때, 해시값에 해당하는 버킷만 보아서는 안 된다. 다음 버킷과 그 다음 버킷까지도 필요하다면 보아야 한다. 그래서 빈 버킷을 만날 때까지 루프를 돌며 해당 키를 찾고 그래도 없을 때에만 확실하게 ‘없다’는 결과를 리턴하게 한다.
선형 탐색법은 삭제에 무척 취약한 알고리즘이다. FindKey 함수가 빈칸을 찾을 때까지 검색을 하도록 되어 있어서, 삭제한 후에 그 칸을 빈 칸으로 만들어서는 안 된다. 예를 들어 12, 22, 32, 42까지 입력한 후 22를 지우고 32를 찾는다고 해보자.
22, 32, 42를 삽입할 때 충돌이 발생하므로 그 다음 칸에 이 값들을 기록할 것이다. 이렇게 하더라도 FindKey 함수가 연속된 옆칸을 찾도록 되어 있으므로 일단은 문제가 없다. 하지만 22가 삭제되어 버리면 FindKey가 버킷 3에서 검색을 중지하므로 32, 42는 없는 값으로 취급되어 버릴 것이다. 그래서 삭제할 때 빈칸으로 만들어서는 안되며 -1 등의 특이값으로 삭제된 칸임을 명시하고 FindKey 함수는 삭제된 칸의 다음도 계속 검색하도록 해야 한다.
이 예제의 선형 탐색법은 충돌 발생시 바로 오른쪽 칸을 사용하지만, 그것은 구현하기 나름이다. 왼쪽 칸을 사용할 수도 있고, 일정 칸씩 건너 뛰면서 다음 버킷을 찾을 수도 있다. 한 버킷이 넘치면 주변 버킷도 넘칠 확률이 높으로므 몇 칸씩 건너 뛰면 충돌을 좀 더 최소화할 수 있을 것이다.
선형 탐색법과 유사한 방법으로는 재해시(rehash)가 있다. 선형 탐색법은 충돌 발생시 산술적인 연산으로 다른 칸을 찾지만, 재해시법은 대체 칸을 찾는 해시 함수를 별도로 하나 더 두는 방법이다.
- AddKey 함수: 먼저 hash 함수로 해시값을 찾되, 이 자리가 점령되어 있다면 hash2 함수로 대체 버킷을 찾고 그 대체 버킷에 값을 기록한다. 만약 재해시를 했는데도 충돌이 발생한다면 어쩔 수 없다.
- AddKey 함수가 두 개의 해시 함수를 사용하므로 FindKey 함수는 두 해시 함수가 계산하는 해시값을 다 점검해야 한다. 둘 중 하나라도 값이 존재하면 있는 것이고 둘 다 없다면 키가 존재하지 않는다는 것을 알 수 있다. 재해시 방법은 선형 탐색법과 마찬가지로 충돌 발생시에 대체칸을 찾는 방법인데 필요하다면 해시 함수를 더 많이 둘 수도 있다. 3차, 4차 해시 함수까지 둔다면 충돌 발생 확률은 상당히 떨어질 것이다. 이 때, 재해시 함수는 원래 해시 함수와는 가급적 다른 해시값을 계산하도록 작성하는 게 좋다.
해시값을 다양화하기 위해서 이렇게 노력하는 것도 좋고, 슬롯의 갯수를 건들여보는 것도 좋다. 슬롯의 갯수를 동적으로 관리할 수도 있지 않을까? 동적 슬롯은 슬롯의 개수를 가변적으로 관리하는 방법이다. 선형 탐색법이나 재해시가 충돌을 회피하는 방법이라면, 동적 슬롯은 충돌에 보다 유연하게 대처하는 방법이라고 할 수 있다. 최초 일정한 크기의 슬롯을 준비하되 만약 버킷이 가득찰 정도로 데이터가 들어오면 슬롯의 크기를 실행 중에도 원하는 크기만큼을 증가시킨다.이렇게 하면 대체 버킷을 찾을 필요도 없고 삭제하는 방법도 번거롭지 않을 것이다.
슬롯은 실행중에 크기를 늘릴 수 있어야 하기 때문에, 동적 배열이나 연결 리스트로 작성하는 게 옳다. 동적 배열을 쓴다면 해시 테이블은 포인터 배열이 될 것이다. 연결 리스트라면 각 버킷이 슬롯 연결 리스트의 진입점인 head를 저장해야 할 것이다. 버킷 내에서의 검색은 순차 검색을 사용하되 만약 동적 슬롯의 크기가 많이 커질 수 있다면, 이분 검색을 쓰는 것이 더 유리할 것이다. 이 때는 물론 배열로만 작성해야 할 것이다.
이상으로 해싱에 대해 알아 보았다. 해싱은 검색 방법이라기 보다는 빠른 검색을 위한 자료 관리 알고리즘이라고 할 수 있다. 예제에서는 충돌 현상을 쉽게 목격하도록 하기 위해 해시 테이블을 작게 만들었고 슬롯도 작게 만들었는데, 실제 프로젝트에서는 해시 테이블을 메모리가 허용하는 한 크게 만드는 것이 좋다. 정수를 저장한다면 버킷이 10개인 경우보다 100개인 경우 충돌이 훨씬 덜 할 것이기 때문이다. 여기에 슬롯도 다섯 개 정도 준비하면 거의 충돌이 없을 것이고 혹시라도 충돌이 발생할 때를 대비해서 재해시 함수를 하나 정도 두면 좋을 것이다.
해싱은 해시 함수로부터 버킷 위치를 바로 찾을 수 있기 때문에 검색 속도가 대단히 빠른 알고리즘이다. 하지만 메모리를 굉장히 많이 소모한다는 단점이 있다. 메모리 크기와 프로세싱 속도는 반비례라는 것을 잘 보여주는 알고리즘이다. 좀 더 빨라지고 싶다면 충분한 메모리를 준비해야 하고, 메모리가 넉넉하지 않으면 잦은 충돌로 인해 느려질 수 밖에 없으므로, 적은 메모리에서도 충분한 효율을 뽑아내기 위해 정교한 알고리즘을 짜내야 할지도 모른다.
'Development > Algorithms' 카테고리의 다른 글
| algorithms/자료구조 & 알고리즘에 대하여 (0) | 2019.12.30 |
|---|---|
| algorithms/알고리즘이란? (0) | 2019.12.30 |
| 알고리즘 공부법 (0) | 2019.12.26 |
| [Algorithms] 이진트리(Binary tree) (0) | 2017.04.19 |
| [Algorithms] B tree에 대한 개념 정리 (0) | 2017.04.17 |
