본문 바로가기

Computer Science/Algorithm

Hashing 이란?

728x90

 

 

1. (Hashing)이란 무엇인가?

 

 

- 해싱(hashing)이란 한마디로 말해서 많은 양의 데이터(data)들을 그보다는 작은 크기의 테이블(table)로 대응

(mapping)시켜 저장할 수 있도록 하는 일종의 데이터 관리 기법이다. 데이터들을 저장하거나 찾을 때 인덱스

(index)라는 또다른 데이터 스트럭쳐(data structure)를 이용하는 대신, 각 데이터들이 테이블의 어느 영역에 위

치할 것인가를 결정해주는 해쉬함수(hash function)를 사용하여 일정한 시간 내에 데이터들을 효과적으로 찾을

수 있도록 해주는 것이 바로 해싱이다. 따라서 데이터들은 순차적으로 저장되는 것이 아니라 테이블 전 영역에

걸쳐서 고루 분포하게 되며, 저장된 데이터를 찾을 때에도 해쉬함수를 사용하면 곧바로 그 위치를 알 수가 있

기 때문에 빠르게 데이터를 검색할 수가 있게 된다.

그러나 해싱은 그 기본 개념으로 인하여 매우 치명적인 약점을 지니고 있는데, 해쉬함수가 이상적(ideal)이지

않은 이상 서로 다른 키(key)들이 테이블의 같은 위치로 결정될 소지가 다분하다는 것이 바로 그것이다. 이런

현상을 충돌(collision)이라 하며, 따라서 해싱에서는 이 충돌을 어떻게 해결할 것인가가 매우 커다란 이슈

(issue)가 된다. 결국 해싱 알고리즘(hashing algorithm)은 해쉬함수와 충돌해결전략(collision resolution

strategy)으로 나뉘게 된다.

=========================================================================================

 

 

 

2. Hashing Algorithm

 

- 해싱 알고리즘(hashing algorithm)은 해싱을 위한 구현 부분으로, 다음과 같이 크게 세 가지로 구분할 수가 있다.

2.1. 완전 해싱 (Perfect Hashing)

- 완전 해싱은 나중에 좋은 해싱 기법으로 언급될 simple uniform 해싱을 의미한다. 즉 서로 다른 키(key)값이 해싱에 의해 주소값을 할당받을 때, 주소값이 절대로 겹치지 않는 이상적인 해싱을 의미한다. 물론 이런 방식은 일대일대응 이외에는 존재하지 않는 방식으로 이상적인 것이다.

2.2. 정형 해싱 (Conventional Hashing)

- 데이타 개수를 이미 알고 있어서, 데이타들이 저장될 주소 범위를 미리 데이타 개수만큼 지정해 두는 방식을 의미한다. 즉, 필요한 메모리의 크기는 미리 측정되고 미리 할당받아야 한다.

2.3. 동적 해싱 (Dynamic Hashing)

- 정형 해싱의 문제점은 데이타를 입력하기 이전에 데이타 개수에 대한 정보가 있어서 메모리를 미리 할당받아야 한다는 점이다. 일반적으로 시간이 지남에 따라서 데이터의 양의 증가하게 되므로 잘못된 측정으로 데이터가 메모리의 범위를 넘게 되면, 더 큰 메모리 크기를 잡고 다시 해싱을 해야 하는 시간적, 자원적 낭비가 일어나게 된다. 동적 해싱은 이러한 데이터의 증감에 적응하기 위해서 나타난 것으로, 동적으로 메모리의 크기를 변화시키는 해싱 기법을 의미한다.

=========================================================================================

 

 

3. Hash Function

 

- 해싱 알고리즘을 해쉬 함수라고 부른다. 해싱 함수(hashing function) h(k)는 어떤 키 k에 대한 테이블 주소(table address)를 계산하기 위한 방법으로, 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식을 말한다.

해싱은 빠른 속도의 데이터 검색 외에도, 전자서명을 암호화하고 복호화 하는 데에도 사용된다. 전자서명은 해쉬 함수를 이용하여 변환된 다음, 해쉬 값(이를 요약 메시지라고 부른다)과 전자서명이 별도로 전송된다. 수신자는 송신자가 사용한 해쉬함수와 같은 것을 사용하여, 서명으로부터 요약 메시지를 뽑아내어 그것을 이미 수신한 요약 메시지와 비교한다. 그 비교 결과는 같아야만 전자서명이 유효한 것이다.

해쉬 함수는 원래의 값이나 키를 색인하는데 사용되며, 그값이 관련된 데이터가 검색될 때마다 다시 사용된다. 그러나, 해싱은 항상 한 쪽 방향으로만 연산된다. 따라서, 해쉬된 값을 분석함으로써 해쉬 함수를 추출해내는 역방향 공학은 필요가 없다. 사실, 이상적인 해쉬함수는 그러한 분석에 의해 추론할 수 없어야 한다. 또한, 우수한 해쉬 함수는 서로 다른 두 개의 입력에 대해, 동일한 해쉬 값을 생산해서는 안된다. 만약 그렇게 되면, 충돌이 생긴다. 충돌 위험성이 매우 적은 해쉬 함수라야 훌륭한 해쉬 함수로 평가된다.

데이터베이스 저장이나 검색에 잘 적용되는 해쉬 함수는 오히려 암호화나 에러검출 목적으로는 잘 듣지 않을 수도 있다. 암호화에 사용되는 잘 알려진 해쉬 함수들이 몇 개 있다. 이러한 것들에는 전자서명을 요약 메시지라고 불리는 더 짧은 값으로 바꾸는 데 사용되는 요약 메시지 해쉬 함수 MD2, MD4, MD5 등과, 더 큰 요약 메시지 (60 비트)를 만드는 표준 알고리즘인SHA (Secure Hash Algorithm) 등이 포함된다.

 

 

'Computer Science > Algorithm' 카테고리의 다른 글

How to learn the algorithm?  (0) 2023.04.15
시간복잡도 개념  (0) 2020.05.17
알고리즘 강좌 7회  (0) 2010.11.28
알고리즘 강좌 6회  (0) 2010.11.28
알고리즘 강좌 5회  (1) 2010.11.27