해시

해시

해시는 값이 저장될 위치(index)를 간단한 연산으로 구하는 것이다.

 

해시 함수를 사용하여 키를 해시값으로 매핑하고 이 해시값을 인덱스 삼아 데이터의 값을 키와 함께 저장하는 것이다. 이때 데이터가 저장되는 곳을 버킷 혹은 슬롯이라 한다.

 

해시 테이블의 크기는 보통 소수로 설정하는데 이는 해시 함수 내부 과정이 해싱을 한 뒤 그 값을 해시 테이블의 크기로 나눈 나머지를 리턴하기 때문이다. 해시 테이블의 크기가 소수가 아니라면 나머지 값이 한 곳으로 치우지기 쉽다. 이를 방지하기 위해 테이블의 크기는 소수로 한다.

 

해시

 

 

그냥 리스트 쓰면 되지 해시 함수를 통해서 숫자를 만들고 그것을 key로 사용하는 해시라는 개념을 왜 굳이 만들었을까?

 

만약 List에 위 정보를 저장했다고 가정해보자.

 

a_list = [["John Smith", "521-1234"], 
          ["Lisa Smith", "521-8976"],
          ["Sandra Dee", "421-9655"]]

 

여기서 "Sandra Dee"의 번호를 찾으려면 리스트 검색의 경우 순차적으로 하나하나씩 확인해야 하므로 O(n) 시간이 걸린다.

반면 해시테이블의 경우 "Sandra Dee"를 해싱하여 key값을 알아내고 테이블에서 key값에 해당되는 value를 가져오면 되므로, O(해싱하는 시간) + O(테이블에서 값 가져오는 시간)이 걸린다.

해싱 과정은 단순한 연산이므로 상수 시간 내에 처리가 가능하고 key를 통해 테이블에서 value를 가져오는 것 또한 상수 시간 내에 처리가 가능하다. 따라서 O(1) + O(1) 이므로 해시 테이블을 사용하여 값을 가져오는데 드는 총 시간 복잡도는 O(1)이다.

 

또, 값을 삭제할 때 a_list.pop(0)을 하면 a_list의 인덱스 0의 뒤에 있는 모든 값들은 한 칸씩 자리를 옮겨야 한다. 이는 크기가 커짐에 비례하며 이 비용은 작지 않다. 반면 해시 테이블의 경우 테이블의 value를 없앤다고 하여 나머지 값들을 옮겨야 되는 것이 아니므로 O(1) 시간 안에 처리가 가능하다. 이는 삽입 시에도 동일하게 적용된다.

 

 

해시 충돌 ( hash collision )

그런데 만약 해싱을 해서 나온 key값이 겹치면 어떻게 해야 할까? 기존에 있던 값을 없애야 하나?

이를 해결하는 방법이 크게 2가지가 있다.

 

 

개별 체이닝 ( Separate Chaining )

해시 체이닝

 

해시 테이블의 기본 방식이기도 한 개별 체이닝(Separate Chaining)은 충돌 발생 시 그림과 같이 연결 리스트로 연결하는 방식이다. 충돌이 발생한 윤아와 서현은 윤아의 다음 아이템이 서현인 형태로 서로 연결 리스트로 연결되었다. 이처럼 기본적인 자료구조와 임의로 정한 간단한 알고리즘만 있으면 되므로, 개별 체이닝 방식은 인기가 높다. 

 

단, 해시 값이 한 곳으로 몰려서 모든 value가 하나의 연결 리스트에 있으면 검색 시 O(n) 시간이 걸릴 것이다. 예를 들어 위 그림에서 윤아, 유리, 서현, 수영의 key 값이 모두 2 라면 다른 곳은 텅텅 비어있고 2번에 해당되는 연결 리스트에 모든 value들이 있을 것이다. 여기서 검색을 진행하는 것은 list에서 검색을 하는 것과 다를 바 없으므로 O(n) 시간이 걸리는 것이다.

 

자바 8에서는 충돌이 일정 임계값을 넘을 경우 연결 리스트를 red-black 트리로 변경하여 검색 시간이 O(log n) 내에 완료되도록 단점을 보완했다. 그리고 java에서 hash map에 어떤 객체를 넣었다면 반드시 comparable을 구현하도록 하자. 참고

 

오픈 어드레싱 ( Open Addressing )

오픈 어드레싱

 

오픈 어드레싱(Open Addressing) 방식은 충돌 발생 시 그림과 같이 탐사를 통해 빈 공간을 찾아 나서는 방식이다. 사실상 무한정 저장할 수 있는 체이닝 방식과 달리, 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다. 충돌이 일어나면 테이블 공간 내에서 탐사(Probing)를 통해 빈 공간을 찾아 해결하며, 이 때문에 개별 체이닝 방식과 달리, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다. 그림은 가장 간단한 방식인 선형 탐사(Linear Probing) 방식이며 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행한다. 특정 위치가 선점되어 있으면 바로 그다음 위치를 확인하는 식이다. 이렇게 탐사를 진행하다가 비어 있는 공간을 발견하면 삽입하게 된다. 가장 가까운 다음 빈 위치를 탐사해 새 키를 삽입한다. 그림에서도 윤아 다음에 서현의 해시값이 동일한 2로 충돌이 발생했고, 다음번 빈 위치를 탐색하며 그다음 위치인 3에 서현이 들어가게 된다. 이처럼 선형 탐사 방식은 구현 방법이 간단하면서도, 의외로 전체적인 성능이 좋은 편이기도 하다.

 

오픈 어드레싱이 충돌 발생 시 진행하는 탐사의 기법은 크게 3가지 선형 탐사, 제곱 탐사 이중해시 3가지가 있다.

 

 

선형 탐사 (Linear probing)

충돌이 일어나면 그 다음 칸에 값을 삽입하는 방식이다.

만약 다음 칸도 채워져 있다면 다다음 칸에 넣고, 다다음 칸도 채워져 있다면 다다다음칸 ...... 이런 식으로 빈칸을 찾을 때까지 검색을 하고 빈칸에 삽입을 하는 방식이다.

 

삭제 시 묘비를 세운다. 묘비를 사용하는 이유는 다음과 같다.

a, b, c의 해시 값이 모두 같을 때 차례대로 a, b, c를 넣으면 테이블은 [..., a, b, c, ...]의 형식으로 테이블이 채워질 것이다.

여기서 b를 지우면 [..., a, null, c, ...]이런 모양이 될 것이다.

그다음 c를 검색하면 a부터 한 칸씩 이동하며 c와 같은지 비교를 하는데 null 부분에서 검색을 멈추게 되고 c가 있음에도 c를 찾지 못한다.

그래서 [..., a, 묘비, c, ...]의 형식으로 삭제할 때 어떤 표시를 남기는 것이다.  이렇게 한다면 a 다음 값으로 묘비를 만나게 될 것이고 빈칸이 아니니 검색을 끝내지 않고 그다음 값도 비교를 하게 되고 그렇게 되면 c를 찾을 수 있다.

 

검색

받은 키의 해시 값을 계산하고, 계산된 해시 값을 key로 사용해 table의 해당 위치로 이동한다.

원하는 값을 찾을 때까지 혹은 빈칸이 나올 때까지 검색을 진행한다.

 

삽입

받은 키가 기존에 있는 키와 같은 경우 키 값에 대해 중복을 허용하지 않으므로 작업을 마친다.

그렇지 않은 경우, 받은 키의 해시 값을 계산하고, 계산된 해시 값을 key로 사용해 table의 해당 위치로 이동한다.

한 칸씩 이동하며 묘비나 빈칸을 찾고 그 위치에 값을 넣는다.

 

삭제

받은 키의 해시 값을 계산하고, 계산된 해시 값을 key로 사용해 table의 해당 위치로 이동한다.

원하는 값을 찾을 때까지 혹은 빈칸이 나올 때까지 검색을 진행하고, 만약 원하는 값을 찾았다면 그 위치에 묘비를 세운다.

 

 

선형 탐사 방식의 문제점

요소들이 모여있을 때 성능이 느려진다.

예를 들어, 선형 탐사 방식을 사용하여 아래 값을 저장하면 다음과 같다.

a ( hash 5)

b ( hash 5)

c ( hash 5)

d ( hash 8)

e ( hash 7)

f ( hash 5)

 

값         [..., a, b, c, d, e, f, ...]

인덱스   [..., 5, 6, 7, 8, 9, 10, ...]

 

이때 f를 찾는다면 해시 값이 5인 것은 현재 a, b, c, f 뿐이므로 이 4개 중에서 검색하는 것이 맞는 것 같은데, 실제로는 a, b, c, d, e, f에 대해 검색을 해야 한다. 이 비효율을 어떻게 개선할 수 있을까?

 

 

Robin Hood hashing  참고

요소를 삽입할 때 만약 삽입하는 요소가 최근 요소보다 집으로부터 더 멀리 떨어져 있다면, 해당 위치의 값을 새 요소로 대체하고 원래 있던 값은 다시 자기 위치를 찾는다. 선형 탐사의 단점을 보완한 방식이다. (156p ~ 191p)

 

위 방식으로 삽입을 진행하면 삭제 시 묘비를 사용하지 않고 backward-shift deletion이라는 기술을 사용할 수 있다. 이는 home에서 얼마큼 떨어져 있는지 알고 있으므로 현재 위치가 홈이랑 떨어져 있는 요소들을 홈 방향으로 하나씩 옮기는 방법이다. (202p ~ 219p)

 

검색

받은 키의 해시 값을 계산하고, 계산된 해시 값을 key로 사용해 table의 해당 위치로 이동한다.

한 칸씩 이동할 때마다 step을 +1 하고, 원하는 값을 찾거나, 빈칸을 찾거나, 현재 내 step보다 작은 step을 갖고 있는 요소를 찾으면 중단한다.

 

삽입

받은 키가 기존에 있는 키와 같은 경우 키 값에 대해 중복을 허용하지 않으므로 작업을 마친다.

그렇지 않은 경우, 받은 키의 해시 값을 계산하고, 계산된 해시 값을 key로 사용해 table의 해당 위치로 이동한다.

한 칸씩 이동할 때마다 step을 +1 하고, 빈칸일 경우 혹은 현재 내 step보다 작은 step을 갖고 있는 경우 해당 위치에 삽입한다.

후자의 경우 덮어 쓰인 기존 값에 대해 삽입을 다시 진행한다.

 

삭제

받은 키의 해시 값을 계산하고, 계산된 해시 값을 key로 사용해 table의 해당 위치로 이동한다.

한 칸씩 이동할 때마다 step을 +1 한다. 빈칸을 찾거나 현재 내 step보다 작은 step을  갖고 있는 요소를 찾으면 중단하고 원하는 값을 찾았으면 해당 값을 삭제하고 빈칸이나 홈 위치에 있는 항목(step 값이 0인 요소)을 발견할 때까지 테이블에서 요소를 한 칸 뒤로 계속 이동하다.

 

 

 

제곱 탐사 (Quadratic probing)

한 칸씩 이동하는 선형 탐사와 달리 이동하는 수를 제곱으로 구한다.

이를테면 처음 충돌이 일어나면 1^2칸 이동하여 그 칸이 비어있는지 확인하고 그곳도 이미 채워져 있다면 2^2칸 이동, 3^2칸 이동하는 식이다.

 

제곱 탐사는 초기 해시 값이 같으면 다음 탐사 위치 또한 동일하다는 점에서 선형 탐사의 단점을 그대로 갖고 있다.

 

 

 

이중 해시 (Double hashing)

탐사할 값의 규칙성을 제거하여 요소들이 뭉쳐져 있는 것을 방지하는 기법이다. 2개의 해시 함수를 준비한 후, 하나는 해시 값을 얻을 때 사용하고 다른 하나는 해시 충돌 시 탐사 이동 수를 얻기 위해 사용한다. 

이를테면, 해시 값을 반환하는 함수는 '3으로 나눈 나머지'를 반환하고 탐사 폭을 반환하는 함수는 '5로 나눈 나머지'를 반환할 때 키 값이 3, 6인 데이터의 해시 값은 둘 다 0으로 동일하지만 3의 탐사 이동 폭은 3이고 6의 탐사 이동 폭은 1이다.

 

단, 제수는 서로소 이어야 원하는 효과를 볼 수 있다. ( 위 경우 3과 5 )

 

 

 

 

쓰이는 단어들

로드 팩터 (load factor)

해시 테이블이 얼마만큼 가득 차있는지 확인할 수 있는 비율이다. 적재율이라고도 한다.

해시 테이블 전체 크기가 m이고 현재 n개의 원소가 저장되어 있을 때 적재율은 n/m이다.

적재율이 올라갈수록 충돌이 자주 일어나고 충돌이 자주 일어날수록 해시 테이블의 성능은 나빠지므로 로드 팩터가 어느 정도 높아지면 데이터들을 더 큰 테이블로 옮긴다. 반대로 적재율이 너무 낮으면 사용하지 않는 빈 슬롯이 많다는 것이고 이는 공간 낭비가 될 수 있으므로 적절한 값 이하로 로드 팩터 값이 떨어지면 데이터들을 더 작은 테이블로 옮긴다.

 

 

 

 

 

---

https://woonys.tistory.com/entry/%ED%95%B4%EC%8B%9CHash-%EA%B0%9C%EB%85%90-%EC%A0%95%EB%A6%ACFeat-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B8%ED%84%B0%EB%B7%B0

해시(Hash) 개념 정리(Feat. 파이썬 알고리즘 인터뷰)

https://namu.wiki/w/%ED%95%B4%EC%8B%9C#s-2

해시 - 나무위키

https://soobarkbar.tistory.com/50

해시 (Hash)