임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 알고리즘.
해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 체크섬 또는 해시 등으로 불린다.
해시 함수는 결정론적으로 작동해야 하며, 따라서 두 해시 값이 다르다면 그 해시값에 대한 원래 데이터도 달라야 한다.
비둘기집 원리란 n+1개의 물건을 n개의 상자에 넣을때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다.
해시 충돌이란 해시 함수가 서로 다른 두개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.
검색 - 해시함수를 사용하여 입력 키 값으로부터 해시 값을 얻어 그것을 인덱스로 사용하는 것은 효율적인 검색 방식중 하나이다. 이와 같은 해시 값으로 이루어진 자료구조를 해시 테이블이라 부른디. 서로 다른 키값이 동일한 인덱스로 매핑될 경우, 해시 충돌이 발생하여 해시 테이블의 성능을 떨어뜨리게된다.. 이와 같은 해시 충돌을 처리하는 방식 중 가장 많이 쓰이는것이 체이닝과 개방 번지화 방법을 쓴다.. 그러나 둘다 최악의 경우 조회 복잡도가 원소 새수에 따라 선형 시간이 된다.
* 상수 시간 O(1)
* 선형 시간 O(n) 입력값에 비례해 증가비율이 일정
일반적으로 정렬 알고리즘의 경우 비교를 요구하기때문에 O(n logn)보다 시간을 단축시킬수 없다.
결정론적 알고리즘: 예측한 그대로 동작하는 알고리즘.
어떤 특정한 입력이 들어오면, 언제나 똑같은 과정을 거쳐서 언제나 똑같은 결과를 내놓는다. 결정론적 알고리즘은 실제 기계에서 돌릴 수 있는 효율적인 알고리즘일 뿐 아니라, 가장 오랫동안 연구되었으며 가장 친숙한 알고리즘이다.
결정론적 알고리즘은 가장 단순한 형태로 생각하면 수학 함수라 볼수 있다.
분산 해시 테이블 (distributed hash tables, DHT or DHTs) 이름대로 해시 테이블을 분산하여 관리하는 기술/ 대표적인 시스템으로 비트토렌트, eDonkey등 P2P 네트워크에 많이사용
'프로그래밍 > 일반' 카테고리의 다른 글
| 프레임워크란? (11) | 2012.05.28 |
|---|---|
| 스크립트 언어란? (1) | 2012.05.23 |
| 유니코드? UTF-8? (0) | 2012.01.03 |
JOKERGT
타고난 능력이란, 자연계의 초목과 같아 항상 탐구로써 가지를 쳐줘야 한다. https://www.linkedin.com/in/datajoker1