해시

개요

해시란 키가 취할 수 있는 범위의 집합을 제한된 수치범위에 매핑시키는 방식이다. 이 매핑을 수행하는 변환함수를 해시 함수라 한다. 해시 함수는 보통 그리 복잡하지 않은 알고리즘으로 구현되기 때문에, 상대적으로 CPU, 메모리 같은 시스템 자원을 덜 소모하는 특성이 있다. 그리고 같은 입력값에 대해서는 같은 출력값이 보장되며, 이 출력값은 가능한 한 고른 범위에 균일하게 분포하는 특성이 있다. 특수 목적용으로 해시값을 생성하는 원본과 별도의 값을 입력받아서 같은 입력에 대해 다른 출력값을 가지게 하는 해시 함수도 존재한다

해시 함수의 종류

1. SHA
2. MD

출돌 회피

해시함수는 거의 무한한 Input 을 제한된 output 범위에 매핑시키는 과정이기 때문에, 필연적으로 충돌이 발생한다. 따라서 해시함수는 이렇나 충돌을 최소화 하도록 작성해야 한다. 특히 암호화에서 사용하는 해시 함수는 이러한 충돌을 암호의 무력화 이기 때문에 반드시 충돌을 피해야 한다. 그러나 많든 적든 반드시 충돌을 일어남으로, 만일 충돌이 일어난다면 데이터를 다른 영역에 저장해야 한다.

체인 방식

해시 테이블은 각각 데이터의 포인터를 저장하는 리스트로 구성되고, 만약에 데이터를 저장하다 충돌이 일어나면, 충돌 데이터는 해시 테이블 리스트 끝에 추가하는 방식이다.

더블 해시법

더블 해시법에서는 충돌 발생시 빈 영역을 찾을 수 있는 거리를 또 다른 해시 함수를 사용해서 계산한다.

Dynamic Hashing

해쉬 함수의 key value mapping을 동적으로 조정하여, 변화하는 자료의 양에 대처할 수 있게 하는 방식이다. 대표적으로 Extendible Hashing과 Linear Hashing이 있다.