[Algorithm] Hashing

보통 해싱은 해시 함수를 통해 임의의 데이터를 고정된 길이의 데이터로 매핑하는 것이라고 한다.

데이터베이스에서 테이블에서의 빠른 탐색을 위해서 테이블 내의 각각의 튜플에 대해서

색인(Index)을 만들어서 색인 만으로 데이터를 검색하는데 이용한다.

 

해싱을 알고리즘 문제 풀이에 어떤 식으로 사용하는지 설명 해보려고 한다.

알고리즘에서 해싱이 사용되는 분야는 문자열이 대부분이어서(아직 공부가 부족해서 문자열밖에 접해보지 못했다.)

대부분의 설명이 문자열에 관한 내용이 될 수밖에 없을 것 같다.

 

사람의 시각으로 보면 당연히 문자열은 하나의 의미 덩어리이고 그냥 눈으로 보면 비교가 가능한 것이지만

컴퓨터의 관점에서 보면 문자들의 배열이기 때문에 비교하려면 하나하나 다 확인하는 수밖에 없어서 시간이 많이 걸릴 수 밖에 없다.

 

문자열이라는 임의의 데이터를 고정된 길이의 데이터로 매핑시킬 수 있을까?

생각보다 간단하다. 문자열 하나하나에 색인 값을 지정해주면 비교할 때 색인 만으로 값의 비교가 가능하다.

 

문자열의 색인은 어떤식으로 만들까?

가장 간단한 방법은 문자열을 숫자로 보는 것이다. 

컴퓨터 사이언스에서 캐릭터 값은 눈으로 보기에는 문자로 보이지만, 실제 내부적으로는 모두 0 ~ 255까지의 숫자로 표현된다.

따라서 문자열을 숫자로 보면 256진수로 생각해 볼 수 있다.

 

예를들어 영어단어 Apple의 경우도 256진수로 볼 경우 위의 그림처럼 표현이 가능하다.

아스키코드표에 따르면 Apple는 65 112 112 108 101이라는 5자리 256진수로 표현이 가능하다.

이것을 다시 10진수로 바꾸면 마지막에 보이는 수식과 같이 표현되는데 5자리 수임에도 불구하고 제일 앞 부분만 계산해도 2^32이 넘어간다.

계산자체는 가능하다. 다만 일반적으로 정수를 표현할때 사용되는 자료형인 Int로 표현이 불가능한 범위이고, 이 값을 색인으로 사용한다는것은 조금만 생각해도 불가능한 일이라는것을 알 수있다.

우선 색인을 사용하기위해서는 해시값을 키로하고 원래 문자열을 가리키는 색인을 가지는 배열을 선언해야한다. 그런데 방금전에 본 Apple의 경우처럼 5글자만되더라도 최소 2^32 정도의 공간 즉, 4,294,967,296만큼의 배열을선언해야하는데 가능할까? 선언해본사람은 알겠지만 불가능하다.

 

그렇다면 이 거대한값을 어떤식으로 처리해야 컴퓨터안에서 색인으로 표현이 가능할까?

나머지 연산을 이용하면된다. 등장하는 문자열의 개수보다 큰 적당한 소수를 이용해서 나머지 연산을 수행하면 해시값을 배열로 표현가능한 범위안으로 줄일수있다.

 

그런데 왜 등장하는 문자열의 개수보다 큰수로 나누어야할까? 그리고 왜 소수일까?

등장하는 문자열의 개수보다큰 수여야 하는 이유는 생각해 보면 당연하다. 나머지 연산을 실행할때 N으로 나눈 나머지를 구한다면 결과 값이 0 부터 N - 1까지 나온다. 비둘기 집의 원리에 의하면 N개 이상의 데이터를 N으로 나머지 연산을 하게 될 경우 반드시 나머지 값이 겹치게 되는 값이 한개 이상 존재하게 된다. 따라서 등장하는 문자열의 개수보다 큰 수로 나눠야지 해시 값의 중복을 피할 수 있다, 

그리고 소수인 이유는 아직 제대로 이해하지는 못했지만 소수를 사용할 경우에 해시값의 충돌이 덜 일어나기 때문에 소수를 사용한다고 한다.