문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류: 탐색]] [[분류: 자료 구조]] == 개요 == 해시란 키가 취할 수 있는 범위의 집합을 제한된 수치범위에 매핑시키는 방식이다. 이 매핑을 수행하는 변환함수를 해시 함수라 한다. 해시 함수는 보통 그리 복잡하지 않은 알고리즘으로 구현되기 때문에, 상대적으로 CPU, 메모리 같은 시스템 자원을 덜 소모하는 특성이 있다. 그리고 같은 입력값에 대해서는 같은 출력값이 보장되며, 이 출력값은 가능한 한 고른 범위에 균일하게 분포하는 특성이 있다. 특수 목적용으로 해시값을 생성하는 원본과 별도의 값을 입력받아서 같은 입력에 대해 다른 출력값을 가지게 하는 해시 함수도 존재한다 == [[해시 함수]]의 종류 == #[[SHA]] #[[MD]] == 출돌 회피 == 해시함수는 거의 무한한 Input 을 제한된 output 범위에 매핑시키는 과정이기 때문에, 필연적으로 충돌이 발생한다. 따라서 해시함수는 이렇나 충돌을 최소화 하도록 작성해야 한다. 특히 [[암호화]]에서 사용하는 해시 함수는 이러한 충돌을 암호의 무력화 이기 때문에 반드시 충돌을 피해야 한다. 그러나 많든 적든 반드시 충돌을 일어남으로, 만일 충돌이 일어난다면 데이터를 다른 영역에 저장해야 한다. === 체인 방식 === 해시 테이블은 각각 데이터의 포인터를 저장하는 리스트로 구성되고, 만약에 데이터를 저장하다 충돌이 일어나면, 충돌 데이터는 해시 테이블 리스트 끝에 추가하는 방식이다. === 더블 해시법 === 더블 해시법에서는 충돌 발생시 빈 영역을 찾을 수 있는 거리를 또 다른 해시 함수를 사용해서 계산한다. === Dynamic Hashing === 해쉬 함수의 key value mapping을 동적으로 조정하여, 변화하는 자료의 양에 대처할 수 있게 하는 방식이다. 대표적으로 [[Extendible Hashing]]과 [[Linear Hashing]]이 있다. 해시 문서로 돌아갑니다.