해싱은
하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것이다. 짧은 해시 키를 사용하여 항목을 찾으면 원래의 값을 이용하여 찾는 것보다 더 빠르기 때문에, 해싱은 데이터베이스 내의 항목들을 색인하고 검색하는데 사용된다.
간단한 예제로서, 데이터베이스 내에 있는 사람들의 그룹은 다음과 같이 배열될 수 있다.
Abernathy, Sara
Epperdingle, Roscoe
Moore, Wilfred
Smith, David
(그리고 더 많은 수의 데이터가 알파벳 순으로 정렬되어 있다).
이러한 이름들 각각은 데이터베이스 내에서 개인들 데이터의 키가 될 수 있다. 데이터베이스 검색 수법은 일치하는 것이 먼저 발견될 때까지 각 이름들을 글자단위로 확인하기 시작해야만 한다. 그러나, 만약 이름들 각각이 해시 된다면, 각 이름별로 4자리의 고유한 키 (자릿수는 데이터베이스 내에 들어있는 이름의 수에 따라 다르다)를 생성하는 것이 가능해진다. 예를 들면 다음과 같다.
7864 Abernathy, Sara
9802 Epperdingle, Roscoe
1990 Moore, Wilfred
8822 Smith, David
(기타 등등)
어떤 이름을 찾는 작업은 먼저 해시 값을 계산하고, 그 다음에 그 값을 사용하여 일치여부를 비교하는 작업으로 구성된다. 일반적으로 이렇게 하는 것은, 각 문자가 26개의 경우를 갖는 예측할 수 없는 값의 길이에서 찾는 것보다, 각각이 오직 9개의 경우를 갖는 네 자리 수에서 일치하는 것을 찾는 것이 더 빠르다.
해싱 알고리즘을 해시 함수라고 부른다. 해싱은 빠른 속도의 데이터 검색 외에도, 전자서명을 암호화하고 복호화하는 데에도 사용된다. 전자서명은 해시 함수를 이용하여 변환된 다음, 해시 값(이를 요약 메시지라고 부른다)과 전자서명이 별도로 전송된다. 수신자는 송신자가 사용한 해시함수와 같은 것을 사용하여, 서명으로부터 요약 메시지를 뽑아내어 그것을 이미 수신한 요약 메시지와 비교한다. 그 비교 결과는 같아야만 전자서명이 유효한 것이다.
해시 함수는 원래의 값이나 키를 색인하는데 사용되며, 그 값이 관련된 데이터가 검색될 때마다 다시 사용된다. 그러나, 해싱은 항상 한 쪽 방향으로만 연산된다. 따라서, 해시된 값을 분석함으로써 해시 함수를 추출해내는 역방향 공학은 필요가 없다. 사실, 이상적인 해시함수는 그러한 분석에 의해 추론할 수 없어야 한다. 또한, 우수한 해시 함수는 서로 다른 두 개의 입력에 대해, 동일한 해시 값을 생산해서는 안된다. 만약 그렇게 되면, 충돌이 생긴다. 충돌 위험성이 매우 적은 해시 함수라야 훌륭한 해시 함수로 평가된다.
다음에 나열한 것들은, 그 동안 사용되어 온 비교적 단순한 해시 함수들이다.
1) 나눗셈-나머지 방식 : 먼저 테이블 내에 들어갈 항목의 개수를 추정한다. 그 숫자는 원래의 값이나 키에서 몫과 나머지를 추출해 내기 위해 각각을 나누는 제수(除數)로 사용된다. 계산의 나머지가 해시 값이 된다 (이 방식은 얼마간의 충돌이 일어나는 것을 피할 수 없으며, 어떠한 검색 방식이라도 충돌 여부를 인식하고, 대체 검색 방법을 제공할 수 있어야만 한다).
2) 접기 : 이 방식은 원래의 값을 여러 부분으로 나누어, 그 부분들을 함께 더하고 나서, 마지막 네 자리를 해시 값이나 키로 삼는 것이다.
3) 기수변환 : 값이나 키가 디지털이라면, 다른 순서의 숫자열을 만들도록 기수(基數)를 변경할 수 있다. 즉, 10진수의 키를 16진수의 키로 변경할 수 있는 것이다. 변경 후, 해시 값의 길이를 일정하게 유지하기 위해 상위 자리수의 일부는 버려질 수 있다.
4) 자리수 재배열 : 이것은 단순히 세 번째부터 여섯 번째 자리까지 등과 같이 원래 값이나 키의 일부를 취하여 그 순서를 역으로 한 다음, 그 것을 해시 값이나 키로 사용하는 것이다.
데이터베이스 저장이나 검색에 잘 적용되는 해시 함수는 오히려 암호화나 에러검출 목적으로는 잘 듣지 않을 수도 있다. 암호화에 사용되는 잘 알려진 해시 함수들이 몇 개 있다. 이러한 것들에는 전자서명을 요약 메시지라고 불리는 더 짧은 값으로 바꾸는 데 사용되는 요약 메시지 해시 함수 MD2, MD4, MD5 등과, 더 큰 요약 메시지 (60 비트)를 만드는 표준 알고리즘인 SHA 등이 포함된다.
