해시 문서 원본 보기

[[분류: 탐색]]
[[분류: 자료 구조]]

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

== [[해시 함수]]의 종류 ==
#[[SHA]]
#[[MD]]

== 출돌 회피 ==
해시함수는 거의 무한한 Input 을 제한된 output 범위에 매핑시키는 과정이기 때문에, 필연적으로 충돌이 발생한다. 따라서 해시함수는 이렇나 충돌을 최소화 하도록 작성해야 한다. 특히 [[암호화]]에서 사용하는 해시 함수는 이러한 충돌을 암호의 무력화 이기 때문에 반드시 충돌을 피해야 한다. 그러나 많든 적든 반드시 충돌을 일어남으로, 만일 충돌이 일어난다면 데이터를 다른 영역에 저장해야 한다. 
=== 체인 방식 ===
해시 테이블은 각각 데이터의 포인터를 저장하는 리스트로 구성되고, 만약에 데이터를 저장하다 충돌이 일어나면, 충돌 데이터는 해시 테이블 리스트 끝에 추가하는 방식이다.

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

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