오르카의 아틀리에

지난번 포스팅까지는 해시 테이블에 대한 소개와 동작 방식, 충돌 문제를 해결하는 방법으로 Close-Addressing 기법인 Chaining을 소개했다. 이번 포스팅에서는 Open-Addressing 기법에 속하는 3가지 방법을 소개하고, 지금까지 소개했던 해결법들을 간단하게 비교해 본 뒤 해시 테이블의 장단점을 정리해 보도록 하려 한다.

Open-Addressing?!

Open-Addressing 기법은 해시 함수로 얻어낸 주소를 그대로 이용하지 않고 상황에 따라 변경할 수 있는 기법이다. 물론 추적 가능하게 변형하는 기법을 사용한다. 이 기법을 사용하면 Close-Addressing에서는 보지 못했던 "클러스터링 문제"가 발생하게 되고 클러스터가 많이, 크게 일어나면 성능상 문제가 생기기 때문에 그에 관련된 또 다른 해결책들이 만들어져있다. 처음부터 천천히 소개해보고자 한다.

Linear Probing

선형 해결법이라고도 하는데, 충돌이 일어나게 되면 바로 옆칸에 자료를 저장하는 방식이다.



만약 위 그림과 같은 상황에서 "위가혜"라는 이름을 해시테이블에 저장한다고 하자, 해시함수에서 26이라는 결과가 나왔고, 보시다시피 26번에는 "최일지"라는 이름이 이미 저장되어있다. Linear Probing은 바로 옆칸을 확인하고 비어있다면 그 공간에 저장하는 방식이다. 그림에서는 26번 27번이 비어있지 않기 때문에 28번에 저장해야만 한다. 간단해 보이는 방식이다. Chaining 방식처럼 동적으로 추가 메모리를 할당하지 않아도 되고, 생성한 테이블을 다 사용할 수 있을 것 같아 좋아 보일 수 있다. (사실 해시테이블에서는 그렇게 좋지는 않다. 자세한 건 뒤에서 설명)


삽입은 이런 방식으로 빈 곳을 찾아서 집어넣으면 되고, 검색도 이런 방식으로 찾고 빈 곳이 나올 때 까지 못 찾으면 데이터 셋에 없는 것이다. 삭제는 항상 조금 복잡한데, 만약 단순하게 "위가혜"라는 이름을 저장하고, "이혜주"라는 이름을 삭제해버리면 "위가혜"라는 이름을 찾을 수 없을 것이다. 삭제에는 조금 번거로운 과정을 거쳐야만 한다. 이렇게 삭제과정에서 생기는 구멍을 Hole이라고 표현하는데 아래 소스코드에서 구현되어있다.



봐야 할 부분은 erase와 reMove 부분이다. 내가 왜 이렇게 네이밍했었는지 모르겠다. 부끄러운 네이밍이다 ㅠㅜ 하여튼, erase를 보면 지우고 난 뒤 생기는 hole을 기준으로 reMove를 하게 되는데, reMove과정을 보면 단순하게 빈 곳이 나올 때 까지 옆칸 데이터를 확인하면서 지운 데이터와 해시값이 같은 데이터들을 Hole로 이동시키게 된다. 물론 재귀적으로 동작한다. 그렇게 되면 Hole 부분이 연속적으로 재정렬되게 되고 데이터가 빠질 일이 없어질 것이다.



여기서 바로 클러스터링 이슈가 발생하게 된다. 충돌이 일어나게 되면 바로 옆칸으로 저장공간이 확장되게 되고 확장된 공간에는 해시값이 같지 않더라도 충돌이 일어나게 된다. "위가혜"라는 이름을 저장하기 위해 26, 27, 28, 29번 인덱스를 검사해야 했다. 그런데 사실 27번에 있는 이름은 해시값이 26, 28번에 있는 이름은 25, 29번에 있는 이름은 29번으로 "위가혜"라는 이름을 저장하기 위해 검사한 데이터들의 해시값이 같지는 않지만 전부 리니어하게 저장되어있다. 이렇게 클러스터가 커지면 해시테이블의 효율이 떨어지게 된다. 넣기만 하면 클러스터에 히팅되니 더 많이 자리를 검사해야 하기 때문에 자료가 많아질수록 O(1)보다는 O(k)에 가까워 질 것이다. 이러면 굳이 해시테이블을 사용하는 이유가 없어진다. 앞으로 소개할 방법으로 클러스터링이 일어나는 것을 방지할 수는 없지만, 어느 정도 완화할 수는 있다.

Quadratic probing과 Double Hashing

두 가지 방법이 존재한다. 비슷한 접근 방법이기 때문에 같이 소개하기로 하는데, 간략하게 설명하면 충돌이 일어나서 새로운 공간을 찾을 때 Linear 처럼 바로 옆 공간이 아니라 유추할 수 있는 거리만큼 떨어진 공간을 사용하는 방법을 사용한다.


Quadratic probing은 Linear처럼 1칸 2칸 3칸 떨어진 곳이 아니라 1칸 4칸 9칸 떨어진 곳을 검사하는 방법이다.?이렇게 되면 어느 정도 클러스터링이 생기는 것을 방지할 수 있게 된다. 구현도 Linear probing에 서 조금 수정해주면 되는 정도이다. 하지만 같은 해시값을 가지는 데이터들에 대해서는 공간 간격이 같으므로 같은 해시값을 가지는 데이터들과는 여전히 클러스터링이 발생하기 쉬워진다.



Double Hashing은 떨어져 있는 공간 간격을 계산하는 전용 해시 함수를 만들어서 사용하는 방법이다. 같은 해시값의 데이터들의 클러스터링을 방지하려면 되도록 첫 해시함수에서 값이 같더라도 두 번째 해시 함수에서는 다른 값이 나와야 하기 때문에 함수를 만드는데 조금 신중하게 만들어야 하는 어려움이 있다.


해시 테이블 평가하기

해시테이블에는 Load Factor라는 지표가 있다. 공식으로 이야기하면 "데이터가 저장된 수 / 테이블 사이즈"인데 이 지표에 따라서 해시 테이블의 성능에 영향을 준다. 일반적으로 Open-addressing에서 이 지표가 1에 가까워 지면 해시테이블의 동작이 기하급수적으로 느려지게 된다. 그래서 많아도 이 지표를 0.8로 유지하는 것이 좋다. (나는 0.6정도를 권장한다) 해시테이블의 성능은 "Load Factor"와 "클러스터의 빈도"로 정해진다. Load Factor를 잘 유지해야 하고 클러스터가 잘 발생하지 않는 해시함수를 사용하는 것이 좋다. (아무래도 내가 만드는 것보다는 검증된 소스를 사용하는 것이 좋겠지….)

해시 테이블의 장단점

이론적으로는 O(1), 충돌을 잘 해결한다면 O(m)정도에 데이터를 저장하고 처리할 수 있다. 정말 빠르게 삽입, 검색할 수 있는 자료구조 중 하나이다. 하지만 데이터가 해시함수를 통해 규칙성 없게 분포하게 되는데, 만약 자료를 정렬된 순서로 접근하고 싶거나 활용해야 한다면 정말로 효율이 좋지 못하다. AVL 같은 다른 자료구조들은 O(n) 정도로 해시 테이블보다 느리고 구현도 어렵지만, 항상 자료를 정렬되게 가지고 있으므로 활용도가 큰 편이다. 또한, 캐시 적중률이 높으면 그만큼 처리 시간이 줄기 때문에 알고리즘 성능에 영향을 미치게 되는데 해시테이블은 자료가 규칙성 없게 널리 분포되기 때문에 캐시 적중률이 상당히 떨어지는 편에 속한다.