자료구조 - 해시충돌 피하기 (ft. 체이닝, open addressing)

자료구조 - 해시충돌 해결방안 (ft. 체이닝, open addressing)

 

안녕하세요.

 

로스윗의 코딩캠프입니다.

 

오늘은 자료구조 중에서 중요한 해시(Hash)충돌을 피하는 방법에 대해서 강의하겠습니다.

 

해시가 무엇인지, 해시 충돌이 무엇인지 모르시는 분은 이전 강의를 참고해주세요.

 

정말 어렵지 않으니 잘 따라와주세요!!

 

 

자료구조 - 해시(Hash)란? (ft. 가장 쉬운 비유 설명)

자료구조 해시(Hash)란? (ft. 가장 쉬운 비유 설명)

자료구조 - 해시(Hash)의 특징

자료구조 - 해시(Hash)의 특징

해시충돌과 해결방안

자료구조 - 해시충돌과 해결방안

 

 

- 해시충돌을 피하는 방법

1. 체이닝

체이닝이 어떤 방식으로 돌아가는지 매커니즘을 먼저 설명드릴게요.

우선 특정 Key에 Hash function으로 넣은 해시값을 인덱스화 해서 데이터를 저장 할 거에요.

 

 

체이닝 그림 예시

 

그런데 다른 키를 넣었는데도 똑같은 해시값이 나왔다면 똑같은 인덱스 위치를 가리키겠죠. 

 

 

 

체이닝 그림 예시

 

그리고 이때 이미 저장된 데이터가 있다면

 

데이터가 저장된 bucket이 마치 연결리스트(linkedlist)처럼 다음 노드를 가리키게 해서

 

그 노드에 새로운 데이터를 저장하도록 만듭니다.

 

반응형

그리고 또 다른 key에서 또 동일한 해시값이 나온다면

 

bucket에 또 새로운 노드를 연결해서 데이터를 삽입하게 될겁니다.

이 모습이 마치 체인이 연결된것 같다고 해서 체이닝 방법이라고 부르는것입니다.

 

 

 

 

체이닝 그림 예시

 

그래서 해시테이블 전체모양을 본다면 그림과 같은 형태로 도식화 할 수 있습니다.

 

 

 

체이닝 그림 예시

 

인덱스가 10이 나온 경우, 그리고 12, 13에서

 

동일한 인덱스 값이 발생해서 이렇게 linkedlist를 연결하고 있는 모습이죠.

이런 체이닝 방식으로 해시 충돌을 회피하게 될 경우에는

 

결국 hash function으로 인덱스의 위치를 찾는데 O(1)의 시간 복잡도가 걸린다고 해도

인덱스의 위치에서 값을 가져올 때 해당 값을 찾기 위해 또 list를 하나씩 탐색하는 과정을 거쳐야 합니다.

이 스캔 과정은 list에서 설명드렸다시피 

 

이 뒤에 노드가 길어질수록 탐색시간도 같이 늘어나는 O(N)의 시간복잡도를 갖는다고 했습니다.

그렇기 때문에 최악의 경우 해시테이블임에도 O(N)의 시간복잡도가 나올 수 있게 되는거죠. 

그래서 사실 이렇게 List로 체이닝을 구현하는 것이 전통적인 체이닝 연결 방식이지만

최근 Java에서는 List대신 Tree 라는 자료구조를 써서 시간 복잡도를 조금 더 단축시키기도 합니다.

 

Tree가 어떤 자료 구조인지는 다음 포스팅에서 자세히 다뤄보도록 하구요.

지금은 체이닝이라는 전통적인 방식을 통해 해시충돌을 해결할 수 있다는 것을 아시는것이 중요합니다.

 

 

 

- Open Addressing

해시 충돌을 해결하는 두번째 방법은 Open Addressing이라는 방법입니다.

충돌이 발생할 경우에 다른 버킷에 데이터를 저장하는 방법입니다.

 

 

오픈 어드레싱

 

그런데 이때 다른 버킷을 어떻게 찾느냐에 따라서 또 방법이 나눠지게 됩니다.

우선 첫번째는 선형 탐색을 통해서 다음 버킷을 찾는 방법입니다.

해시 충돌시에 N칸을 건너뛴 다음 다음 버킷에 저장을 하는 것입니다. 

이 N칸은 1칸이 될 수도 있고 2칸이 될수도 있고, 3칸이 될 수도 있겠죠.

 

 

 

오픈 어드레싱

 

예를들어 그림처럼 이렇게 10번 인덱스 부터 19번까지 인덱스가 있는데

빨간색이 칠해진 10번 인덱스, 14번 인덱스, 18번 인덱스에 데이터가 들어있는 상황입니다.

그런데 다른 키를 넣었을 때 10번 인덱스와 동일한 인덱스를 가리키는 해시 값이 나왔습니다.

근데 이 10번칸에는 이미 다른 데이터가 들어 있으니까

 

이 버킷을 건너뛴 다음 버킷인 11번 인덱스에 값을 저장하게 되는거죠.

이 선형 탐색의 방식으로 다음 버킷을 찾는다면 계산이 굉장히 단순하다는 장점이 있습니다. 

계산이 단순하다는 장점이 있지만 반면에 검색 시간이 많이 소요될 수 있다는 단점도 있습니다.

 

예를들면 아까 10번 인덱스의 위치에 이미 값이 있기 때문에

 

그 다음 버킷인 11번 인덱스에 값을 넣는다고 했죠.

그런데 만약 11번 버킷에 데이터가 또 있는 상황이라면

 

1칸 더 건너 뛰어서 12번 인덱스로 건너가야겠죠.

그런데 만약 12번 버킷에도 데이터가 또 있는 상황이에요.

 

그러면 1칸 더 건너 뛰어서 13번째 인덱스에 값을 넣어야겠죠.

이런 방식으로 버킷의 위치를 탐색하다보면 결국 시간복잡도가 O(N)까지 늘어날 수 있기 때문에

 

검색 시간이 많이 소요될 수 있다는 부분입니다.

그리고 더 큰 문제는 데이터들이 특정 위치에만 밀집하게 되는 경우가 생길 수 있습니다.

 

앞에서 좋은 해시function은 키를 고르게 분포시키는거라고 했죠.

이렇게 데이터들이 밀집되지 않고 고르게 분포되는게 왜 중요하냐면

 

밀집될수록 충돌로 데이터의 위치를 재탐색해야 할 일이 많아지기 때문이에요.

데이터들이 특정 위치에만 밀집되는 것은 (Clustering)클러스터링이라 부르고,

 

이거는 결국 성능의 저하를 초래하게 됩니다.

 

 

- 클러스터링 피하기

1. 제곱 탐색

그렇다면 밀집현상인 이 클러스터링을 피하기 위한 방법에는 무엇이 있을까요?

제곱 탐색이라는 방법이 있습니다.

제곱 탐색은 N번째 칸이 아니라 N제곱 칸을 건너 뛴 다음 버킷에 데이터를 저장하는 방법입니다.

예를들면 처음에는 1칸을 건너 뛰고 그 다음에는 2의 제곱인 4칸을 건너뛰고,

 

그 다음에는 3의 제곱인 9칸, 그 다음은 4의 제곱인 16칸 이런 식으로 건너뛰게 되는거죠.

그렇게 되면 데이터들이 특정 위치에 촘촘히 밀집되는게 아니라

 

데이터간 간격이 넓어지기 때문에 클러스터링을 현상을 피할 수 있겠죠.

 

하지만 처음 해시function을 통해 나온 해시값이 동일하다면

 

마찬가지로 건너 뛴 칸의 개수도 똑같기 때문에 똑같이 N번의 탐색을 할 수 있다는 문제가 여전히 있습니다.

그래서 이 문제를 해결하기 위해 나온 방법이 바로 이중 해시입니다.

 

2. 이중 해시

이중해시는 해시로 나온 값에 한 번 더 다른 해시함수를 적용하는거에요.

 

그래서 첫번째 해시 함수는 최초의 해시값을 구하는 해시function이고,

 

두번째 해시함수는 충돌이 발생 했을 때 돌리는 해시함수입니다.

그래서 충돌이 발생 했을 때 몇 칸을 이동할 지를 이 해시함수를 통해서 구하게 됩니다.

이렇게 값을 구하게 되면,

 

최초의 해시 값이 같더라도 이동 폭이 다르기 때문에 클러스터링 문제가 해결 될 수 있겠죠.

이 방법은 버킷을 탐색하는데 있어서 규칙성을 아예 없애버린 방법이라고 볼 수 있습니다.

오늘은 이렇게 해시 충돌에 대한 포스팅을 진행해보았습니다.

 

아무쪼록 도움이 되었으면 좋겠구요.

 

다음 포스팅에서는 자료구조 트리에 대해서 강의를 진행하도록 하겠습니다.

 

로스윗의 코딩캠프는

 

미래의 개발자 여러분을 응원합니다!

 

모두 화이팅!!

 

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)

그림으로 쉽게 이해하는 자료구조와 알고리즘 차이

그림으로 쉽게 이해하는 자료구조와 알고리즘 차이