85. Hashing

해싱(Hashing)은 길이가 정해지지 않은 임의의 데이터를 길이가 정해진 데이터로 변환하여 표현하는 것을 말한다. 일반적으로 해싱의 대상이 되는 '길이가 정해지지 않은 임의의 데이터'는 문자열인 경우가 많으며, 해싱의 결과인 '길이가 정해진 데이터'는 정수값으로 나오는 경우가 많다. 이런 이유로 이 블로그에서는 문자열을 정수로 해싱하는 경우만 다루지만, 해싱의 대상과 결과가 항상 이렇게 될 필요는 없다.

 

해싱에 대해 알아보기 전에 왜 해싱이 필요한지를 알아야 한다. 문자열을 해싱하는 것이 그다지 특이한 일이 아니라는 것은 문자열을 그대로 사용할 경우 큰 단점이 생기는 상황이 있다는 것을 의미한다. 이 상황은 문자열을 검색하는 상황이다. 정수나 실수 데이터를 비교할 경우 단순히 한 번(경우에 따라 두 번)만 대소 비교를 하면 되지만, 문자열의 경우 길이가 서로 같다면 그 자체로는 단번에 비교할 방법이 없어서 한 글자씩 일일히 확인해야 한다. 이런 방식의 비교는 최악의 경우 문자열의 길이에 비례하는 시간이 걸리며, 비교 횟수가 많아질 경우 그만큼 성능도 좋지 않다. 따라서 문자열을 비교하는 횟수가 많아질 경우 해싱을 하는 것이 성능 면에서 더 좋다고 할 수 있다.

---

문자열을 정수값으로 변환하기 위해서는 변환의 기준이 있어야 한다. 이 기준은 일반적으로 함수로 나타낼 수 있으며 이 함수를 해시 함수(Hash Function)이라고 한다. 또한 해시 함수의 결과값을 해시값(Hash Value)이라고 한다. 일반적으로 해시값의 범위가 너무 커지면 다루기가 불편하기 때문에 해시값의 범위를 제한하게 되는데, 원래의 해시값에 모듈러 연산을 해서 얻어지는 결과값을 해시값으로 사용하는 경우가 많다. 이렇게 하면 모듈러를 $m$이라고 할 때 해시값의 범위가 $0$ 이상 $m-1$ 이하로 제한되기 때문에 다루기가 상당히 수월해진다. 하지만 해시값의 종류가 $m$개밖에 없으므로 서로 다른 문자열의 해시값이 같아지는 경우가 발생할 수 있으며, 이를 해시 충돌(Hash Collision)이라고 한다. 해시 함수는 해시 충돌이 최대한 적게 발생하도록 정하는 것이 좋다.

 

해싱을 사용하면 문자열을 저장하는 set, map 등을 정수를 저장하는 set, map 등으로 대체할 수 있으며 이 글에서 설명한 Unordered Container가 그 역할을 수행한다. 각각의 컨테이너들은 해시셋(Hashset), 해시맵(Hashmap) 등으로 불리며 해시맵을 해시 테이블(Hash Table)이라고도 한다. 해시 테이블은 각각의 데이터를 해시값에 따라 적절한 위치에 저장하는데, 해시 충돌이 발생할 경우 주로 다음과 같은 두 가지 방법으로 처리한다. 다음과 같이 데이터가 저장된 해시 테이블이 있다고 하자.

 

 

개별 체이닝(Separate Chaining) 방식은 C++과 JAVA의 해시 테이블이 사용하는 방식으로 해시 충돌이 발생할 경우 데이터를 연결 리스트로 연결한다. 위의 해시 테이블에 해시값이 $2$인 새로운 데이터를 삽입할 경우 해시 테이블의 상태는 아래와 같이 변한다.

 

 

왼쪽 그림은 해시값이 $2$인 리스트의 끝에 새로운 데이터가 추가된 상태이고, 오른쪽 그림은 리스트의 앞에 새로운 데이터가 추가된 상태이다. 왼쪽과 같이 리스트의 끝에 데이터를 추가하는 것은 조금 더 직관적이라는 장점이 있지만 오른쪽과 같이 리스트의 앞에 데이터를 추가하는 것은 더 간단하고 빠른 경우가 많다. 실제로 해시 테이블을 구현할 때는 둘 중 적절한 것을 사용하면 된다.

 

오픈 어드레싱(Open Addressing) 방식은 python의 해시 테이블이 사용하는 방식으로 해시 충돌이 발생할 경우 비어 있는 리스트를 찾아서 그 자리에 데이터를 삽입한다. 위의 해시 테이블에 해시값이 $2$인 새로운 데이터를 삽입할 경우 해시 테이블의 상태는 아래와 같이 변한다.

 

 

해시값이 $2$인 리스트에 이미 데이터가 있기 때문에 다음 위치인 해시값이 $3$인 리스트를 확인한다. 이 리스트에는 데이터가 없기 때문에 여기에 새로운 데이터가 추가되었다. 이렇게 리스트를 순차적으로 확인하면서 비어 있는 리스트를 찾는 방식을 선형 탐사(Linear Probing) 방식이라고 하며 구현이 간단하면서도 성능이 꽤 괜찮은 편이다. 비어 있는 리스트를 찾는 방식은 선형 탐사 이외에도 더 존재하지만 이 글에서는 언급하지 않았다.

 

항상 비어 있는 리스트에 새로운 데이터를 삽입하기 때문에 오픈 어드레싱 방식은 데이터가 항상 해시값에 해당하는 리스트에 추가되지는 않는다. 또한 빈 리스트의 수가 줄어들수록 빈 리스트를 찾기 위한 평균적인 탐색 횟수가 증가하기 때문에 저장된 데이터의 수가 증가할 경우 해시 테이블의 크기를 늘리는 등의 조치를 취해야 하지만 이 방법도 성능 면에서 그렇게 좋지는 않다.

---

현재 MD, SHA 등의 다양한 해시 함수가 존재하며 암호화와 관련하여 해싱이 중요하게 다뤄지고 있으나, 이런 내용은 이 블로그의 범위를 벗어나기 때문에 더이상 언급하지 않는다.

 

→ solved.ac tag: hashing