[IT 기술면접 준비자료] 해시(Hash)와 해시충돌(Hash Collision)

 해싱(Hashing)은 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것이다. (출처: http://www.terms.co.kr/hashing.htm) 그리고 해싱은 해시 테이블(Hash Table)과 해시 함수(Hash Function)로 구성된다.

그림1. 해시테이블과 해시함수의 역할을 나타내는 개념도

 

 

 해시테이블(Hash Table, Hash Map이라고도 불림.)은 Key와 Value를 갖는 자료구조이다. 주로 효율적인 검색에 활용되는데, 위 그림을 보자. John Smith라는 사람의 전화번호를 찾는 과정을 가정했을 때, 해시함수(Hash Function)의 입력값은 "John Smith"이고 출력값은 "01"이다. 그리고 색인이 "01"인 bucket에서 "521-8976"을 찾는다.

 그렇다면 해시함수에 대해서도 어느정도 설명이 되었을 것이다. 해시함수는 해시테이블의 키 값으로 레코드가 저장되어 있는 주소(혹은 색인)를 산출하는 함수이다. 순차검색에 비해, 해시테이블을 이용한 검색은 속도 측면에서 획기적이라고 할 수 있다. 

 데이터를 Key로 간소화하여 저장한다는 아이디어는 좋지만, 다른 내용의 데이터가 같은 키를 갖는다면? 이러한 상황을 해시 충돌(Hash Collision)이라고 한다. 같은 키값을 갖는 데이터가 생긴다는 것은, 특정 키의 버켓에 데이터가 집중된다는 뜻이다. 그래서 너무 많은 해시 충돌은 해시테이블의 성능을 떨어뜨린다. 

 그러므로 해시 함수를 잘 정의하여 해시 충돌을 최소화 하는 것이 성능 개선에 도움이 된다. 한편, 해시함수의 입력값은 무한하지만, 출력값의 가짓수는 유한(출력값, 즉 키가 유한하지 않다면 해시기법을 사용하는 의미가 없다.)하므로 해시 충돌은 반드시 발생한다.(비둘기집 원리)

해시 충돌과 이를 해결하는 체이닝을 나타낸 그림

 

 위의 그림에서 Sandra Dee라는 사람의 연락처를 삽입하는 상황을 가정해보자. Sandra Dee라는 키는 John Smith라는 키와 결과값이 같다. 둘 사이에 충돌이 일어난 것이다. 그러자 충돌이 일어난 주소(혹은 색인)의 bucket에 레코드가 추가로 담긴 것을 확인할 수 있다. 만약에 해당 bucket에 충분한 공간이 없다면? 오버플로우가 발생한다.

 이러한 해시 충돌을 해결하는 방법에는 여러가지가 있다.

1. 체이닝(Chaining)

 버켓 내에 연결리스트(Linked List)를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식이다. 그림2를 다시보자, Sandra Dee라는 사람의 연락처를 삽입할 때, 충돌이 일어나니 버켓 내에서 연결리스트로 데이터를 연결하는 것을 확인할 수 있다. 

2. 개방 주소법(Open Addressing)

 체이닝의 경우 버켓이 꽉 차더라도 연결리스트로 계속 늘려가기에, 데이터의 주소값은 바뀌지 않는다.(Closed Addressing) 하지만 개방 주소법의 경우에는 다르다. 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식을 개방 주소법이라고 한다. 개방 주소법은 대표적으로 3가지가 있다.

선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.

제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)

이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

 

개방 주소법에는 더 많은 방법들이 있다. 그리고 지금까지 다뤄본 해싱과 개념이 살짝 다른 '동적 해싱'도 있다. 사족으로 아래에 체이닝과 개방주소법의 비교를 추가하여 기재해봤다.

 

그림3. 체이닝과 선형탐색의 비교

 

 

  

 

◎ 체이닝(Chaining)의 장점 
 

 → 연결 리스트만 사용하면 된다. 즉, 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.

 → 해시테이블이 채워질수록, Lookup 성능저하가 Linear하게 발생한다. (그림 3 참조)

 

◎ 개방주소법(Open Addressing)의 장점

 

 → 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다.

 

 → 삽입,삭제시 오버헤드가 적다.

 → 저장할 데이터가 적을 때 더 유리하다.

 

  

 

 

 -끝-

 

  

 

 

그림출처 및 참고: https://en.wikipedia.org/wiki/Hash_table