해시함수

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : [해시 기능]– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2010년 7월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

해시 함수는 임의의 크기의 데이터를 고정 크기 값에 매핑하는 데 사용할 수 있는 함수입니다.해시 함수에 의해 반환되는 값은 해시 값, 해시 코드, 다이제스트 또는 단순 해시라고 불립니다.이 값은 보통 해시 테이블이라고 하는 고정 크기의 테이블을 인덱싱하는 데 사용됩니다.해시 함수를 사용하여 해시 테이블을 인덱싱하는 것을 해시 또는 분산 스토리지 주소 지정이라고 합니다.

해시함수와 그 관련 해시테이블은 데이터 저장 및 검색 어플리케이션에서 검색당 작고 거의 일정한 시간에 데이터에 액세스하기 위해 사용됩니다.데이터나 레코드에 필요한 총 공간보다 극히 일부만 더 큰 스토리지 공간을 필요로 합니다.Hashing은 순서부여 및 순서부여 목록과 구조화 트리의 일정하지 않은 액세스 시간과 큰 키 또는 가변 길이 키의 상태 공간에 직접 액세스해야 하는 기하급수적인 스토리지 요건을 회피하는 계산 및 스토리지 공간 효율적인 데이터 액세스 형태입니다.

해시함수의 사용은 키와 함수 상호작용의 통계적 특성에 의존합니다.최악의 경우 동작은 참을 수 없을 정도로 나쁘고, 평균적인 경우 동작은 거의 최적(최소한의 충돌)^[1]일 수 있습니다.

해시 함수는 체크섬, 체크 디짓, 핑거프린트, 손실 압축, 랜덤화 함수, 오류 수정 코드 및 암호와 관련되어 있으며 종종 혼동됩니다.개념은 어느 정도 중복되지만, 각각 고유한 용도와 요구사항이 있으며 다르게 설계되고 최적화됩니다.해시 함수는 주로 데이터 무결성 측면에서 이러한 개념과 다릅니다.

개요

해시함수는 입력을 키로 하여 데이터 저장 및 검색 어플리케이션으로 식별하기 위해 데이터 또는 레코드와 관련지어진다.키는 정수처럼 고정 길이이거나 이름처럼 가변 길이일 수 있습니다.경우에 따라서는, 데이텀 그 자체가 열쇠가 되는 경우가 있습니다.출력은 데이터 또는 레코드 또는 포인터를 저장하는 해시 테이블을 인덱싱하는 데 사용되는 해시 코드입니다.

해시 함수는 다음 세 가지 함수를 수행하는 것으로 간주할 수 있습니다.

• ADD 또는 XOR와 같은 패리티 보존 연산자를 사용하여 단어 또는 다른 단위로 접어서 가변 길이 키를 고정 길이(일반적으로 기계 단어 길이 이하) 값으로 변환합니다.
• 결과 값이 키 공간 전체에 균일하게 분산되도록 키의 비트를 스크램블합니다.
• 키 값을 테이블 크기 이하의 값으로 매핑합니다.

양호한 해시함수는 1) 매우 고속으로 계산해야 하며 2) 출력값(충돌)의 중복을 최소화해야 한다는 두 가지 기본 특성을 충족합니다.해시 함수는 그 효과를 위해 바람직한 확률 분포를 생성하는 데 의존하며, 액세스 시간을 거의 일정하게 단축합니다.높은 테이블 로딩 계수, 병리학적 키 세트 및 제대로 설계되지 않은 해시 함수로 인해 테이블 내의 항목 수가 선형에 근접할 수 있습니다.해시 함수는 최악의 ^{[Notes 1]}경우 최고의 퍼포먼스, 높은 테이블 로딩 팩터에서의 뛰어난 퍼포먼스, 특별한 경우 키를 해시 코드에 매핑할 수 있도록 설계할 수 있습니다.구현은 패리티 보존 비트 연산(XOR 및 ADD), 곱셈 또는 분할을 기반으로 합니다.해시 함수에 필요한 부가적인 방법은 링크 리스트와 같은 보조 데이터 구조 또는 빈 슬롯을 찾기 위한 테이블의 체계적인 프로브를 사용하는 충돌 해결 방법입니다.

해시 테이블

해시 함수는 해시 테이블과 함께 데이터 항목 또는 데이터 레코드를 저장 및 검색하기 위해 사용됩니다.해시 함수는 각 데이텀 또는 레코드에 관련된 키를 해시 코드로 변환하여 해시 테이블을 인덱싱하는 데 사용됩니다.항목을 테이블에 추가할 때 해시 코드는 빈 슬롯(버킷이라고도 함)을 인덱싱할 수 있으며, 이 경우 항목이 테이블에 추가됩니다.해시 코드가 풀슬롯을 인덱스 하는 경우, 어떤 종류의 충돌 해결이 필요합니다.새로운 아이템은 생략(테이블에 추가되지 않음)되거나 오래된 아이템을 대체할 수 있습니다.또한 지정된 절차에 따라 다른 위치에 있는 테이블에 추가할 수 있습니다.이 순서는 해시 테이블의 구조에 따라 달라집니다.체인 해싱에서는 각 슬롯이 링크 리스트 또는 체인의 선두가 되어 슬롯에서 충돌하는 항목이 체인에 추가됩니다.체인은 랜덤 순서로 유지되며 선형 또는 시리얼 순서로 검색되거나 주파수별 자기순서 목록으로 검색되어 액세스 속도를 높일 수 있습니다.오픈 어드레스 해시의 경우 테이블은 점유된 슬롯에서 지정된 방법으로 시작되며, 일반적으로 열린 슬롯이 발견되거나 테이블 전체가 프로브(오버플로우)될 때까지 선형 프로브, 2차 프로브 또는 더블 해시에 의해 프로브됩니다.항목을 찾거나 열려 있는 슬롯이 발견되거나 테이블 전체가 검색될 때까지(테이블에 없는 항목) 동일한 절차를 따릅니다.

특수한 용도

해시 함수는 저속 미디어에 저장된 대용량 데이터 세트의 캐시를 구축하는 데도 사용됩니다.충돌하는 두 항목 ^[2]중 오래된 항목을 폐기하거나 다시 쓰는 방법으로 충돌을 해결할 수 있으므로 캐시는 일반적으로 해시 검색 테이블보다 단순합니다.

해시 함수는 Bloom 필터의 필수 요소입니다. Bloom 필터는 공간 효율적인 확률론적 데이터 구조이며 요소가 집합의 구성원인지 여부를 테스트하는 데 사용됩니다.

해시의 특수한 경우를 기하학적 해싱 또는 그리드 방식이라고 합니다.이러한 어플리케이션에서 모든 입력의 집합은 일종의 메트릭 공간이며, 해시 함수는 셀의 그리드에 대한 그 공간의 분할로 해석될 수 있다.테이블은 대개 두 개 이상의 인덱스(그리드 파일, 그리드 인덱스, 버킷 그리드 및 유사한 이름)를 가진 배열이며 해시 함수는 인덱스 태플을 반환합니다.이 원리는 컴퓨터 그래픽스, 계산 기하학 및 기타 많은 분야에서 점 집합에서 가장 가까운 쌍 찾기, 모양 목록에서의 유사한 모양 찾기, 이미지 데이터베이스에서의 유사한 이미지 찾기 등과 같은 평면 또는 3차원 공간에서 많은 근접 문제를 해결하기 위해 널리 사용됩니다.

해시 테이블은 연관 배열 및 동적 ^[3]집합 구현에도 사용됩니다.

특성.

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : [해시 기능]– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2017년 10월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

균일성

정상적인 해시함수는 예상되는 입력을 출력 범위에 걸쳐 가능한 한 균등하게 매핑해야 합니다.즉, 출력 범위의 모든 해시 값은 거의 동일한 확률로 생성되어야 합니다.이 마지막 요건이 필요한 이유는 동일한 해시 값에 매핑된 입력의 쌍인 충돌 횟수가 증가함에 따라 해시 기반 메서드의 비용이 급격히 증가하기 때문입니다.일부 해시 값이 다른 값보다 발생할 가능성이 높은 경우 검색 작업의 더 큰 부분이 충돌하는 테이블 항목 집합을 검색해야 합니다.

이 기준은 값이 랜덤이 아니라 균일하게 분포되어야 한다는 점에 유의하십시오.좋은 랜덤화 함수는 (계산 효율에 관한 문제를 제외하고) 일반적으로 해시 함수로서 좋은 선택이지만, 그 반대가 참일 필요는 없습니다.

해시 테이블에는 대부분의 경우 유효한 입력의 작은 부분 집합만 포함됩니다.예를 들어, 클럽 멤버십 리스트는 가능한 모든 이름 중 매우 큰 집합 중 100개 정도의 멤버 이름만 포함할 수 있습니다.이 경우 균일성 기준은 가능한 모든 엔트리의 글로벌세트뿐만 아니라 표에서 찾을 수 있는 엔트리의 거의 모든 전형적인 서브셋에 대해 유지되어야 합니다.

즉, m 레코드의 일반적인 세트가 n개의 테이블슬롯에 해시되어 있는 경우 버킷이 m/n보다 많은 레코드를 수신할 확률은 매우 작아야 합니다.특히 m이 n보다 작을 경우 레코드를 1개 또는 2개 이상 보유하는 버킷은 매우 적습니다.n이 m보다 훨씬 크더라도 소수의 충돌은 사실상 불가피합니다. 생일 문제를 참조하십시오.

키가 미리 알려져 있고 키 세트가 정적인 특별한 경우 절대(또는 무충돌) 균일성을 실현하는 해시 함수를 찾을 수 있습니다.이런 해시함수는 완벽하다고 한다.이러한 함수를 구성하는 알고리즘적인 방법은 없습니다. 하나는 매핑할 키 수와 탭할 테이블 슬롯 수의 요인 함수입니다.매우 작은 키 집합보다 완벽한 해시 함수를 찾는 것은 보통 계산상 불가능합니다. 결과 함수는 표준 해시 함수보다 계산상 복잡할 가능성이 높으며 최소한의 충돌 수를 생성하는 양호한 통계 속성을 가진 함수보다 한계적 이점만 제공합니다.범용 해시 함수를 참조하십시오.

테스트 및 측정

해시 함수를 테스트할 때 카이 제곱 검정을 통해 해시 값의 분포의 균일성을 평가할 수 있습니다.이 검정은 적합도 측도입니다. 버킷에 있는 항목의 실제 분포 대 기대(또는 균일한) 항목 분포입니다.${\displaystyle \frac{\underset{}{\overset{}{}}}{}}$은${\displaystyle \frac{\underset{}{\overset{}{}}}{}}$: j $0$ m - 1 ( b j${\displaystyle \frac{}{}}$) ( ${\displaystyle \frac{{}_{}{j}_{}}{}}$ +${\displaystyle \frac{1}{}}$) /${\displaystyle \frac{}{2\mathrm{}}}$ (${\displaystyle \frac{n}{}}$ / ${\displaystyle \frac{2\mathrm{}m}{}}$) / 2 ( n + 2 ${\displaystyle \frac{m}{}}$)$$(${\displaystyle \frac{n}{}}$ + ${\displaystyle \frac{2}{}}$ m - 1 ) \ $displaystyle$ \$frac$ { $sum$ ${\displaystyle \frac{{}_{}}{}}${ j =$0$}^{ $m$- 1 （ b _ { $j$} + 1) / $2$（ $n$+ 2$m$-$$${\displaystyle \frac{1}{}}$）$}}}$

$여기$서 n$${\$displaystyle$ n$}$은 키 수$,$ $m{\displaystyle }$ {\$displaystyle$ m$}$은 버킷 수, b ${\displaystyle j_{}}$ ${\$는 $버킷{\displaystyle }$ j$${$displaystyle$ j$}$의 항목 수입니다.

하나의 신뢰 구간(0.95 - 1.05) 내의 비율은 계산된 해시 함수의 예상 균일한 분포가 있음을 나타냅니다.

해시 함수는 적용할 때 균일한 분포를 가질 가능성이 높은 기술적 속성을 가질 수 있습니다.하나는 엄밀한 눈사태 기준입니다.단일 입력 비트가 보완될 때마다 각 출력 비트가 50% 확률로 변경됩니다.이 속성이 발생하는 이유는 키 공간의 선택된 하위 집합의 변동성이 낮기 때문입니다.출력이 균일하게 분포되기 위해서는 1비트라도 낮은 변동량이 출력의 높은 변동량(즉 테이블스페이스에 걸친 분포)으로 변환되어야 합니다.일부 비트가 변경을 꺼리면 키가 해당 값을 중심으로 클러스터화되기 때문에 각 비트는 50%의 확률로 변경됩니다.비트가 너무 쉽게 변경되기를 원하는 경우 매핑은 단일 비트의 고정 XOR 함수에 접근하고 있습니다.이 성질에 대한 표준 테스트는 ^[4]문헌에 설명되어 있습니다.곱셈 해시 함수에 대한 기준의 관련성은 여기에서 ^[5]평가된다.

효율성.

데이터 저장 및 검색 애플리케이션에서 해시 함수의 사용은 검색 시간과 데이터 저장 공간 간의 트레이드오프입니다.검색 시간이 제한되지 않은 경우 매우 콤팩트하고 순서가 없는 선형 목록이 가장 좋습니다. 스토리지 공간이 제한되지 않은 경우, 키 값으로 인덱싱할 수 있는 임의 액세스 구조는 매우 크고 매우 희박하지만 매우 빠릅니다.해시함수는 잠재적으로 큰 키 공간을 키의 수에 관계없이 제한된 시간 내에 검색 가능한 가능한 저장 공간의 양에 매핑하는 데 유한한 시간이 걸린다.대부분의 응용 프로그램에서 해시 함수는 최소 지연 시간으로 계산 가능하며 다음으로 최소 명령 수로 계산해야 합니다.

계산의 복잡성은 필요한 명령의 수와 개별 명령의 지연 시간에 따라 달라지며, 가장 단순한 방법은 비트 방식(폴딩), 그 다음 곱셈 방법, 가장 복잡한(가장 느린) 방법은 나눗셈 기반 방법입니다.

충돌은 빈도가 낮고 약간의 지연이 발생하지만 그 외에는 무해하기 때문에 일반적으로 더 많은 연산이 필요하지만 몇 번의 충돌을 저장하는 것보다 더 빠른 해시 함수를 선택하는 것이 좋습니다.

사업부는 거의 모든 칩 아키텍처에 마이크로프로그래밍되어 있기 때문에 사업부 기반 구현이 특히 중요합니다.상수로 나눗셈(모듈로)을 반전시켜 상수의 단어 크기 곱셈 역수로 곱셈할 수 있다.이것은 프로그래머 또는 컴파일러에 의해 수행될 수 있습니다.분할은 일련의 시프트 서브트랙트 및 시프트 애드로 직접 축소할 수도 있지만, 이러한 작업의 수를 최소화하는 것은 어려운 문제이며, 결과적으로 발생하는 조립 명령의 수는 12개 이상일 수 있으며 파이프라인에 영향을 미칠 수 있습니다.아키텍처에 하드웨어 다중 기능 유닛이 있는 경우, 역순으로 다중화하는 것이 더 나은 접근법이 될 수 있습니다.

이러한 계산에는 비용이 많이 들기 때문에 테이블사이즈 n을 2의 거듭제곱으로 할 수 없고, 나머지 연산이나 나눗셈 연산을 수행할 필요가 없습니다.예를 들어 n이 2보다 훨씬^b 작다고 가정합니다.[0, 2^b - 1] 구간에서 균일한 의사 난수 생성 함수 P(키)를 고려합니다.[0, n-1] 간격의 해시함수는 n P(key)/2이다^b.분할을 오른쪽 비트 시프트(가능한 한 고속)로 대체할 수 있습니다.nP(키)>> b.

키가 반복적으로 해시되고 해시 함수가 비용이 많이 드는 경우 해시 코드를 미리 계산하여 키로 저장함으로써 계산 시간을 절약할 수 있습니다.해시 코드가 일치한다는 것은 키가 동일하다는 것을 의미합니다.이 기술은 보드 위치의 64비트 해시 표현을 저장하는 게임 플레이 프로그램의 전치 테이블에 사용됩니다.

유니버설리티

유니버설 해싱 스킴은 임의의 2개의 개별 키의 충돌 확률이 1/m이 되도록 해싱 함수 h를 선택하는 랜덤화 알고리즘입니다.여기서 m은 2개의 키에 관계없이 원하는 개별 해시 값의 수입니다.유니버설 해시는 입력 데이터의 분포에 대해 해시 함수 애플리케이션이 랜덤 함수를 사용하는 것처럼 동작하는 것을 보증합니다(확률적인 의미).그러나 완전한 해시보다 더 많은 충돌이 발생하고 특수 목적의 해시 함수보다 더 많은 작업이 필요할 수 있습니다.

적용 가능성

해시 함수는 다양한 상황에서 사용할 수 있습니다.특정 테이블 크기만 허용하거나, 문자열이 특정 길이까지만 허용되거나, 시드(즉, 이중 해시 허용)를 허용할 수 없는 해시 함수는 사용할 ^{[citation needed]}수 있는 것보다 유용하지 않습니다.

결정론

해시 프로시저는 결정론적이어야 합니다.즉, 특정 입력 값에 대해 항상 동일한 해시 값을 생성해야 합니다.즉, 이는 해쉬되는 데이터의 함수여야 하며, 이는 용어의 수학적 의미여야 합니다.이 요건은 의사 난수 생성기나 시각 등 외부 변수 파라미터에 의존하는 해시함수는 제외합니다.또한 실행 중에 주소가 변경될 수 있는 경우(가비지 수집의 특정 방법을 사용하는 시스템에서 발생할 수 있음) 해시되는 개체의 메모리 주소에 의존하는 함수도 제외됩니다.

결정론은 함수 재사용의 맥락에 있다.예를 들어,^[6] Python은 해시 함수가 해시할 입력 외에 Python 프로세스가 시작될 때 한 번 생성되는 무작위 시드를 사용하는 기능을 추가합니다.Python 해시(SipHash)는 한 번의 실행 내에서 사용할 경우 여전히 유효한 해시 함수입니다.그러나 값이 유지되면(예를 들어 디스크에 기록됨) 다음 실행에서는 랜덤 값이 다를 수 있으므로 더 이상 유효한 해시 값으로 취급할 수 없습니다.

정의된 범위

해시 함수의 출력은 보통 고정 크기를 갖는 것이 좋습니다(단, 아래 참조).예를 들어 출력이 32비트 정수 값으로 제한되어 있는 경우 해시 값을 사용하여 배열에 인덱스를 작성할 수 있습니다.이러한 해시는 일반적으로 데이터 ^[7]검색을 가속화하는 데 사용됩니다.가변 길이 입력으로부터 고정 길이 출력을 생성하는 것은 입력 데이터를 특정 크기의 청크로 분할함으로써 달성할 수 있습니다.데이터 검색에 사용되는 해시 함수는 입력의 청크(예를 들어 문자열의 문자)를 반복적으로 처리하는 일부 산술식을 사용하여 해시 ^[7]값을 생성합니다.

가변 범위

많은 응용 프로그램에서 해시 값의 범위는 프로그램의 각 실행마다 다르거나 동일한 실행(예를 들어 해시 테이블을 확장해야 하는 경우)에 따라 변경될 수 있습니다.이러한 상황에서는 입력 데이터 z와 허용되는 해시 값 n의 두 가지 파라미터를 사용하는 해시 함수가 필요합니다.

일반적인 해결책은 매우 큰 범위(0~2³² - 1)의 고정 해시 함수를 계산하고 결과를 n으로 나눈 다음 나눗셈의 나머지를 사용하는 것입니다.n 자체가 2의 거듭제곱인 경우 비트 마스킹 및 비트 시프트로 이를 수행할 수 있습니다.이 방법을 사용할 경우 응용 프로그램에서 발생할 수 있는 임의의 값 n에 대해 결과가 0 ~n - 1 사이에서 균일한 분포를 갖도록 해시 함수를 선택해야 합니다.함수에 따라 나머지는 홀수 또는 소수 등 n의 특정 값에 대해서만 균일할 수 있다.

최소한의 움직임으로 가변 범위(동적 해시 함수)

해시 함수를 사용하여 프로그램 실행 시간을 초과하는 값을 해시 테이블에 저장하고 해시 테이블을 확장 또는 축소해야 하는 경우 해시 테이블을 동적 해시 테이블이라고 합니다.

테이블 크기 변경 시 최소 레코드 수를 재배치하는 해시 함수가 바람직합니다.필요한 것은 해시함수 H(z,n)입니다.여기서 z는 해시되는 키이고 n은 허용되는 해시값의 개수입니다.그러면 H(z,n + 1) = 확률이 n/(n + 1)에 가까운 H(z,n)입니다.

선형 해싱 및 나선형 스토리지는 일정한 시간에 실행되지만 최소한의 이동 속성을 달성하기 위해 균일성 속성을 완화하는 동적 해시 함수의 예입니다.확장 가능한 해시는 n에 비례하는 공간이 필요한 동적 해시 함수를 사용하여 해시 함수를 계산하고, 이전에 삽입된 키의 함수가 됩니다.균일성 특성을 유지하지만 H(z,n) 값을 계산하기 위해 n에 비례하는 시간을 필요로 하는 여러 알고리즘이 ^{[clarification needed]}발명되었습니다.

이동이 최소인 해시 함수는 분산 해시 테이블에서 특히 유용합니다.

data 정규화

일부 응용 프로그램에서는 입력 데이터에 비교 목적과 무관한 기능이 포함될 수 있습니다.예를 들어, 개인 이름을 조회할 때 대소문자의 구분을 무시하는 것이 바람직할 수 있습니다.이러한 데이터의 경우 사용되는 데이터 동등성 기준과 호환되는 해시 함수를 사용해야 합니다. 즉, 동등하다고 간주되는 두 개의 입력이 동일한 해시 값을 생성해야 합니다.이는 모든 문자를 대문자로 구분하여 해시하기 전에 입력을 정규화함으로써 수행할 수 있습니다.

해시 정수 데이터 유형

해시정수에는 몇 가지 일반적인 알고리즘이 있습니다.최적의 분포를 제공하는 방법은 데이터에 의존합니다.실제로 가장 간단하고 일반적인 방법 중 하나는 모듈로 나눗셈법입니다.

아이덴티티 해시 함수

해시되는 데이터가 충분히 작을 경우 데이터 자체(정수로 재해석)를 해시 값으로 사용할 수 있다.이 아이덴티티 해시함수를 계산하는 비용은 사실상 제로입니다.이 해시 함수는 각 입력을 개별 해시 값에 매핑하기 때문에 완벽합니다.

"충분히 작음"의 의미는 해시 값으로 사용되는 유형의 크기에 따라 달라집니다.예를 들어 Java에서 해시 코드는 32비트 정수입니다.따라서 32비트 정수는Integer및 32비트 부동소수점Float오브젝트는 단순히 값을 직접 사용할 수 있지만 64비트 정수는Long및 64비트 부동소수점Double는 이 메서드를 사용할 수 없습니다.

다른 유형의 데이터에서도 이 해시 방식을 사용할 수 있습니다.예를 들어 대문자와 소문자 사이에 문자열을 매핑할 때 정수로 해석되는 각 문자의 바이너리 인코딩을 사용하여 해당 문자의 대체 형식을 제공하는 테이블(「a」는 A, 「8」 등)을 색인화할 수 있다.각 문자가 8비트(확장^[8] ASCII 또는 ISO 라틴어 1)로 저장되는 경우 테이블에는 2 = 256개의 엔트리만⁸ 있습니다. Unicode 문자의 경우 테이블에는 17×2¹⁶ = 1114112의 엔트리가 있습니다.

동일한 기술을 사용하여 "us" 또는 "za"와 같은 두 글자의 국가 코드를² 국가 이름(26=676 테이블 항목), 13083과 같은 다섯 자리 우편 번호를 도시 이름(100000 항목)에 매핑할 수 있습니다.유효하지 않은 데이터 값(국가 번호 "xx" 또는 우편 번호 00000 등)은 테이블에서 정의되지 않은 상태로 두거나 적절한 "null" 값에 매핑될 수 있습니다.

Trivial 해시 함수

키가 키 공간에 균일하게 또는 충분히 균일하게 분포되어 키 값이 본질적으로 랜덤일 경우, 이미 '해시'된 것으로 간주될 수 있다.이 경우 키 내의 임의의 수의 비트가 다이얼아웃되어^{[clarification needed]} 인덱스로서 해시 테이블에 조합됩니다.예를 들어 단순한 해시함수는 최하위m비트를 마스크하여 그 결과를 사이즈2의^m 해시테이블의 인덱스로 사용할 수 있습니다.

접이식

폴딩 해시 코드는 입력을 m비트의 n개의 섹션(여기서^m 2는 테이블 사이즈)으로 분할하고 ADD 또는 XOR 등의 패리티 보존 비트별 연산을 사용하여 섹션을 결합하고 이어서 마스크 또는 시프트를 사용하여 하이엔드 또는 로우엔드에서 여분의 비트를 잘라냄으로써 생성된다.예를 들어 테이블 크기가 15비트이고 키 값이 0x0123456789인 경우ABCDEF에는 0x4DEF, 0x1357, 0x159E, 0x091A 및 0x8의 5개의 섹션이 있습니다.여기에 15비트 값인 0x7AA4를 더하면 얻을 수 있습니다.

중간 제곱

중간 제곱 해시 코드는 입력을 제곱하여 적절한 수의 중간 자리 또는 비트를 추출함으로써 생성된다.예를 들어 입력이 123,456,789이고 해시 테이블사이즈가 10,000인 경우 키를 제곱하면 15,241,578,750,190,521이 생성되므로 해시 코드는 17자리 번호(높은 자리) 8750의 중간4 자리수로 간주됩니다.중간 제곱법은 키에 선행 또는 후행 0이 많지 않은 경우 적절한 해시 코드를 생성합니다.이것은 곱셈 해시의 변형이지만, 임의의 키가 좋은 승수가 아니기 때문에 그다지 좋지 않습니다.

분할 해시

표준적인 방법은 테이블 크기에 가까운 소수인 제수$M{\displaystyle }$(\$displaystyle$ M$)$을 선택하여 키에 모듈로 함수를 사용하는 것입니다. $즉{\displaystyle }$, h${\displaystyle (K)}$ ${\displaystyle =}$ ${\displaystyle K}$ ${\displaystyle mod}$ M$(\$ h$(K$) =$K{\bmod {M$테이블 사이즈는 보통 2의 거듭제곱입니다.${\displaystyle \mathrm{이}}$를 통해 {${\displaystyle }$0 ,${\displaystyle M}$ - ${\displaystyle 1}$ $}$ { $displaystyle$\ {$0$ , M - 1$$\ }$$에서의 분포가 제공됩니다.이를 통해 다수의 키세트에 대해 양호한 결과를 얻을 수 있습니다.분할 해시의 중요한 단점은 분할이 x86을 포함한 대부분의 최신 아키텍처에서 마이크로프로그래밍되어 곱셈보다 10배 느릴 수 있다는 것입니다.두 번째 단점은 클러스터된 키를 분해하지 않는다는 것입니다.예를 들어, 키 123000, 456000, 789000 등은 모두 같은 주소에 매핑됩니다.이 기술은 많은 키 세트가 이미 충분히 랜덤하고, 키 세트가 큰 소수만큼 순환할 확률은 작기 때문에 실제로 잘 작동합니다.

대수 부호화

대수 부호화는 n비트를 m비트로 ^[9]매핑하기 위해 정수 대신 다항식 모듈로 2로 나눗셈을 사용하는 해시의 나눗셈 방법의 변형이다.$이{\displaystyle }$ 접근법에서 M $= 2$m (${\displaystyle x}$ ) ${\displaystyle =}$ m$$( $x$${\displaystyle }$) ${\displaystyle m_{}{m}^{}}$- 1 ${\displaystyle {}_{}{}^m}$ -${\displaystyle {}^{}{1}^{}}$+ .${\displaystyle }$+ ${\displaystyle {0\mathrm{}}_{}}$0 ( \ $display$$style$ \ $mathrm${$Z$} (x$) = x^{m$} + \$zeta _1-m$$^{$$x}$ {m-{x})을 가정한다$.$$+\zeta$ _${0$ 키 $K{\displaystyle }$ ${\displaystyle =}$ ( ${\displaystyle k_{}}$n -${\displaystyle {}_{}}$1${\displaystyle }$. ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}{}_{}{0\mathrm{}}_{}}$ )$$ ( \ $displaystyle$ K = ( $k$_ { n - ${\displaystyle 1_{}}$) 。$k_{1}k_{0}_$${2}}$$\_다항식{\displaystyle }$ K${\displaystyle (x)}$ $=$ ${\displaystyle {}_n}$ - ${\displaystyle 1_{}}$ ${\displaystyle {}_{}{}^n}$ -${\displaystyle {}^{}{1}^{}}$+${\displaystyle }$.${\displaystyle }$. + ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}{}_{}}$ + ${\displaystyle {}_{}}$ ({$displaystyle$ K$(x$)= $k_{n-1}x^{n-1}+...)$로 간주할 수 있다.$+k_{1}x+k_{0$다항식 산술 모듈 2를 사용하는 나머지는 $K{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle mod}$Z (${\displaystyle x}$ ) ${\displaystyle =}$ ${\displaystyle h_{}}$ m${\displaystyle {}_{}}$- ${\displaystyle 1_{}}$ ${\displaystyle {}_{}{}^m}$ -${\displaystyle {}^{}{1}^{}}$+${\displaystyle }$.${\displaystyle }$+${\displaystyle }$h ${\displaystyle {}_{}}$x + ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$( \ $displaystyle$K ( x ) { \ $bmod${$Z$} =$h$_ { m - 1$}$x { m - 1 + $...$$+h_{1}x+h_{0$$다음$으로${\displaystyle }$h (${\displaystyle K}$ ) ${\displaystyle =}$ ( ${\displaystyle h_{}}$ m${\displaystyle {}_{}}$-${\displaystyle {}_{}}$1${\displaystyle }$. .${\displaystyle {h\mathrm{}}_{}}$ 1 ${\displaystyle {}_{}{}_{}{}_{}{0\mathrm{}}_{}}$ )$$ ( \ $displaystyle$h ( K ) = ( h$_$ { m - $1$ ) $。$$h_{1}h_{0}_{2$${\displaystyle }$Z (${\displaystyle x}$) {$displaystyle$ Z$(x)}$ 가$$ 0 이외의 계수를 가지도록 구성되어 있는 $경우{\displaystyle }$ t 비트 미만의 키를 공유하는 것은 보증됩니다.

Z는 GF(2^k) 필드에서 2-1의^k 제수인 k, t 및 n의 함수를 구성한다.Knuth는 예를 들어 n=15, m=10 및 t$=$에 대해 Z${\displaystyle (x)}$ ${\displaystyle =}$ ${\displaystyle {\mathrm{x}}^{}{}^{}}$ + ${\displaystyle {x\mathrm{}}^{}{}^{}}$5${\displaystyle {}^{}}$+ ${\displaystyle {}^{}}$ ${\displaystyle {4\mathrm{}}^{}}$+ ${\displaystyle {x\mathrm{}}^{}}$2 +${\displaystyle x}$ + ${\displaystyle 1}${\ $displaystyle$ Z$(x$)=$x^{10}$ + $x^{8}$ + $x^{5}$ + $x^{4}$ + x$^{$2} + x+$x+$x+x+$1$ 입니다.파생은 다음과 같습니다.

S$(\displaystyle$ S$)$를 {${\displaystyle 1,}$ ${\displaystyle 2}$,${\displaystyle }$.${\displaystyle }$. , ${\displaystyle t\}}$ ${\displaystyle \}}$(\$displaystyle \1,$2, $..., t\}\subseteq S$$}$${\displaystyle }$및 (${\displaystyle 2}$ j ${\displaystyle mod}$ n${\displaystyle )s}$ S$$ S$displaystyle (2j {\bmodn})\in S\ad$와${\displaystyle }$같은 최소 정수 세트라고 $합니다{\displaystyle }$.

${\displaystyle P}$(${\displaystyle }$x ) ${\displaystyle =}$ ${\displaystyle \underset{}{}}$ j${\displaystyle \underset{}{s}}$S (${\displaystyle x}$ - ${\displaystyle {\alpha }^{}}$j$$) { $displaystyle$P ( x ) = \ $prod$_ {$j$ \ $in$ S （ x - \ $alpha ^$ { $j$} } $\alpha$ 、 （ 2 k ） 、 α ${\displaystyle 、}$ \ $displaystyle$\ alpha \ $in$^ { $n$( $2$^ { $k$} ) } where$$ ) where${\displaystyle }$where where $where$ where where where ${\displaystyle {where}^{}}$ where 、 $（$ \ ） 。$다음$으로 P${\displaystyle (x)}$ ${\displaystyle =}$ $displaystyle$ P$(x$) =$$S.$$${\displaystyle {\alpha \mathrm{}}^{}}$$$ 2 j(\displaystyle $\alpha ^{2j})$는 P${\displaystyle (}$$x)$의 $루트$이므로 ${\displaystyle {\alpha }^{}}$j$(\$$displaystyle \alpha$^{$j$$})$가 루트일 $때$는 반드시$$${\displaystyle (\backslash }$$displaystyle$P$)$의 $계수$를 따른다.$$ ${\displaystyle {\mathrm{}}_{}^{}}$ 2 $=$ ${\displaystyle {pi}_{}}${\$style p_{i}^{2$}=$p_{i}}$를 $만족$하므로 모두 0 또는 1이 됩니다.$R{\displaystyle }$(${\displaystyle x}$ ) ${\displaystyle ={}_{}}$ (${\displaystyle {}_{}}$n -${\displaystyle 1_{}}$ )${\displaystyle x^{}}$n -${\displaystyle {}^{}{1}^{}}$+${\displaystyle }$.${\displaystyle }$+ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$x + ${\displaystyle {}_{}}$ ( \ $displaystyle$R ( x ) =$$r _ { ( n - 1 ) }$x^$ { $n-1}$ +...+$r_{1}x+r_{0}$은 최대 t개의 0이 아닌 계수를 가진 0이 아닌 다항식 모듈 2이며, $R{\displaystyle (x)}${$displaystyle$ R$(x)}$은(는) P$)$ {$displaystyle$ P$(x)}$ 모듈$$ ^{[Notes 3]}$2$의 배수가 아닙니다$.$그러면 대응하는 해시 함수는 공통적으로 t비트 미만의 키를 고유 ^[10]인덱스에 매핑합니다.

일반적인 결과는 계산적으로 실현 가능한 체계를 위해 n개가 커지거나 트윌이 커지거나 둘 다 커집니다.따라서 하드웨어 또는 마이크로코드 ^[11]구현에 더 적합합니다.

고유 치환 해시

최악의 경우 삽입 시간이 ^[12]보장되는 고유한 순열 해시를 참조하십시오.

곱셈 해시

표준 곱셈 해시는 ${\displaystyle \mathrm{h}\mathrm{a}}$ (${\displaystyle K}$ )${\displaystyle {}_{}=}$ ${\displaystyle (}$ ( K ${\displaystyle mod}$W${\displaystyle }$)${\displaystyle }$/ (${\displaystyle W}$ /${\displaystyle M}$ )⌋$${ $display$ $style$ h _ { $a } =$ \$lfloor$ ( $aK${ \ $bmod${ W$$} ) / ($W$ / $M$)$$$display$ ${\displaystyle 、}$ ${\displaystyle 1。}$$값$ a$(\$$displaystyle$ a)는 W$(\displaystyle$ W$)$에 비해 상대적으로 소수여야 하는 적절한 값입니다. 이 값은 커야^{[clarification needed]} 하며 바이너리 표현은 1과 0이 랜덤하게^{[clarification needed]} 혼합되어 있어야 합니다.W ${\displaystyle =}$ ${\displaystyle {\mathrm{}}^{}}$ \ $displaystyle$ W =$2$^ {$w$ } $및$ M ${\displaystyle =}$ ${\displaystyle {\mathrm{}}^{}}$ { $displaystyle$ M =$2$^ { $m$}의$$ 거듭제곱이고 $w{\displaystyle }$\ $displaystyle$w가 기계어 크기일 때 중요한 $실용적$인 특수한 경우가 발생한다.$이{\displaystyle {}_{}}$ 경우 이 공식은 h ${\displaystyle a_{}}$(${\displaystyle K)}$ $=$ ${\displaystyle (}$ ( ${\displaystyle K}$ ${\displaystyle {mod\mathrm{}}^{}}$ ${\displaystyle 2^{}}$w${\displaystyle }$) / ${\displaystyle 2^{}}$w - ${\displaystyle m^{}}$ $⌋$ ( \ $displaystyle$ h$_$ {$a$ } \$lfloor$ ( a K { \ $bmod {$} { } { $w$$$} ) / $2$$$^ { w - mod 2 w$}$ 。이것은$$ 산술모듈 $w-m$ }\ $loor{\displaystyle {\mathrm{}}^{}}$ $\}$ $display$ styledisplay 2 $wyle$에 의해 행해지므로 특수합니다.예를 들어 C에서는 이 함수가 다음과 같이 됩니다.

부호 없는 해시(부호 없는 K) {return (a*K) >>> (w-m);}

$고정{\displaystyle }$m {\$displaystyle$ m$}$ $및$ w {\$displaystyle$ w$}$의 경우 단일 정수 곱셈과 오른쪽 시프트로 변환되어 가장 빠른 해시 함수 중 하나입니다.

곱셈 해시는 확산 불량으로 이어지는 "일반적인 실수"의 영향을 받기 쉽습니다. 즉, 높은 값의 입력 비트는 낮은 값의 출력 ^[13]비트에 영향을 주지 않습니다.곱셈 스텝이 이를 수정하기 전에 유지되는 상위 비트의 스팬을 아래로 이동하고 XOR 또는 ADD를 키로 전환하는 입력 변환입니다.따라서 결과 함수는 다음과 같습니다.^[14]

부호 없는 해시(부호 없는 K) {K ^= K >> (w-m), 반환(a*K) >> (w-m), }

피보나치 해시

피보나치 해시는 승수가 ${\displaystyle 2^{}}$ w${\displaystyle {}^{}}$/ ${\$ { $display 2$^ { $w$} / \ $phi$ $}$인 승수 해시의 한 형태입니다.$여기$서$$w { $display$ $style$$w$$$}$$는$$ 기계어 길이이고$$phi는 황금비(약 5/3)입니다.이 승수의 특성은 키 내의 비트 블록에 대해 테이블 공간에 연속된 키 블록을 균일하게 분산시키는 것입니다.키의 상위 비트 또는 하위 비트(또는 일부 다른 필드) 내의 연속 키는 비교적 일반적입니다.$다양$한 단어 ${\displaystyle {}^{}}$ w\style$^{$}의$$ 승수는 다음과 같습니다.

• 16: a=40503₁₀
• 32: a=2654435769₁₀
• 48: a=173961102589771₁₀^{[Notes 4]}
• 64: a=11400714819323198485₁₀^{[Notes 5]}

조브리스트 해시

미국의 컴퓨터 과학자인 Albert Zobrist의 이름을 따서 Zobrist 해시라고 더 일반적으로 알려진 테이블 해시는 테이블 룩업과 XOR 연산을 결합함으로써 해시 함수의 범용 패밀리를 구성하는 방법입니다.이 알고리즘은 해싱(특히 정수 ^[15]키의 해싱) 목적으로 매우 빠르고 고품질임이 증명되었습니다.

조브리스트 해시는 원래 컴퓨터 게임 플레이 프로그램에서 체스 포지션을 콤팩트하게 나타내기 위한 수단으로 도입되었습니다.보드의 각 공간에 있는 각 조각 유형(흑백의 경우 각각 6개)을 나타내기 위해 고유한 난수가 할당되었습니다.따라서 64x12의 이러한 숫자의 테이블은 프로그램 시작 시 초기화됩니다.임의의 길이를 지정할 수 있지만 64비트는 보드에 64개의 정사각형이 있기 때문에 자연스러웠다.위치는 위치에 있는 조각 사이를 순환하여 변환되고 대응하는 난수(빈 공간은 계산에 포함되지 않음)를 인덱싱하여 XOR(시작값, XOR의 ID 값 또는 랜덤 시드)로 변환됩니다.결과 값은 모듈로, 폴딩 또는 해시 테이블 인덱스를 생성하기 위한 다른 연산에 의해 감소되었습니다.원래 Zobrist 해시는 위치에 대한 표현으로 테이블에 저장되었습니다.

그 후, 이 방법은 워드 내의 4개의 가능한 위치에 있는 각 바이트를 고유한 32비트 난수로 나타냄으로써 해시 정수로 확장되었다.따라서 이러한 난수의 2x4⁸ 표가 작성됩니다.32비트 해시 정수는 플레인 텍스트 정수의 각 바이트 값으로 연속적으로 테이블을 인덱스하고 로드된 값을 XOR화함으로써 전사된다(다시 말해 시작 값은 ID 값 또는 랜덤 시드일 수 있다).64비트 정수에 대한 자연스러운 확장은 2x8⁸ 64비트 난수 테이블을 사용하는 것입니다.

이러한 종류의 함수는 몇 가지 훌륭한 이론적 특성을 가지고 있으며, 그 중 하나를 3-태플 독립이라고 합니다. 즉, 모든 3태플의 키가 동일한 3태플의 해시 값에 매핑될 가능성이 높습니다.

커스터마이즈된 해시 함수

해시함수는 키 내의 기존 엔트로피를 이용하도록 설계할 수 있습니다.키에 선행 또는 후행 제로 또는 미사용의 특정 필드가 있는 경우, 항상 제로 또는 기타 상수 또는 일반적으로 거의 차이가 없는 경우, 이들 위의 휘발성 비트와 해시만 마스킹하면 더 좋고 더 빠른 해시 함수를 얻을 수 있습니다.나눗셈 및 곱셈 방식에서 선택된 제수 또는 승수는 키가 주기적이거나 다른 용장성을 갖는 경우 보다 균일한 해시 함수를 만들 수 있습니다.

가변 길이 데이터 해시

데이터 값이 개인 이름, 웹 페이지 주소 또는 메일 메시지와 같이 긴(또는 가변 길이의) 문자열인 경우 일반적으로 분포가 매우 고르지 않고 종속성이 복잡합니다.예를 들어, 자연어 텍스트는 언어의 특징인 문자와 문자 쌍의 매우 불균일한 분포를 가지고 있습니다.이러한 데이터의 경우 문자열의 모든 문자에 의존하며 각 문자에 다른 방식으로 ^{[clarification needed]}의존하는 해시 함수를 사용하는 것이 좋습니다.

중간과 끝

단순 해시 함수는 문자열의 첫 번째 및 마지막 n개의 문자를 길이와 함께 추가하거나 문자열의 중간 4개 문자에서 워드 크기 해시를 형성할 수 있습니다.이렇게 하면 (잠재적으로 긴) 문자열에 대한 반복은 저장되지만, 문자열의 모든 문자를 해시하지 않는 해시 함수는 키 집합의 용장성, 클러스터링 또는 기타 병리학에 의해 쉽게 선형화 될 수 있습니다.이러한 전략은 키의 구조가 중간, 끝 또는 다른 필드가 0이거나 키를 구분하지 않는 다른 불변 상수일 경우 커스텀 해시 함수로 효과적일 수 있습니다. 그러면 키의 불변 부분은 무시될 수 있습니다.

캐릭터 폴딩

문자별로 접는 전형적인 예는 문자열 내의 모든 문자의 정수 값을 합산하는 것입니다.더 좋은 방법은 오버플로를 무시하고 다음 문자를 추가하기 전에 해시 합계에 상수(일반적으로 상당한 소수)를 곱하는 것입니다.add 대신 배타적 'or'를 사용하는 것도 그럴듯한 대안이다.마지막 연산은 단어 값을 테이블 크기의 인덱스로 줄이는 모듈로, 마스크 또는 기타 함수입니다.이 순서의 약점은 정보가 바이트의 상위 또는 하위 비트로 클러스터될 수 있다는 것입니다.이 경우 클러스터링은 해시 결과에 남아 적절한 랜덤화 해시보다 더 많은 충돌이 발생합니다.예를 들어 ASCII 바이트 코드의 상위 비트는 0이고 인쇄 가능한 문자열은 처음 32바이트 코드를 사용하지 않으므로 정보(95바이트 코드)는 눈에 띄지 않는 방식으로 나머지 비트로 클러스터됩니다.

전형적인 접근법은 Peter의 연구를 바탕으로 PJW 해시라고 불렸습니다.1970년대 ATT Bell Labs의 J. Weinberger는 원래 "Dragon Book"[16]에서 주어진 대로 식별자를 컴파일러 심볼 테이블로 해시하기 위해 설계되었습니다.이 해시 함수는 바이트를 함께 추가하기 전에 4비트를 오프셋합니다.양이 줄지어지면 상위 4비트가 시프트 아웃되고 0이 아니면 XOR이 누적량의 하위 바이트로 돌아갑니다.그 결과 모듈로 또는 기타 축소 연산을 적용하여 최종 해시 인덱스를 생성할 수 있는 워드 크기 해시 코드가 생성됩니다.

오늘날, 특히 64비트 워드 사이즈가 등장함에 따라 워드 청크에 의한 훨씬 더 효율적인 가변 길이 문자열 해시를 사용할 수 있게 되었습니다.

단어 길이 접기

최신 마이크로프로세서는 8비트 문자열이 한 번에 1개의 문자를 처리함으로써 해시 처리되는 것이 아니라 32비트 또는 64비트 정수의 배열로 해석되어 산술 연산을 통해 이러한 "와이드 워드" 정수 값을 해시/적산함으로써 훨씬 더 빠른 처리를 가능하게 합니다(예를 들어 상수 및 비트 시 곱셈).fting). 마지막 단어는 비어 있는 바이트 위치가 있을 수 있으며 해시에 접히기 전에 0 또는 지정된 "랜덤화" 값으로 채워집니다.누적된 해시 코드는 최종 모듈로 또는 다른 연산에 의해 감소되어 인덱스를 테이블로 출력합니다.

기수 변환 해시

10진수를 나타내는 ASCII 또는 EBCDIC 문자열이 계산용 수치로 변환되는 방법과 마찬가지로 가변길이 문자열은 (xa₀^k−1+xa₁^k−2+...)로 변환될 수 있다.+xa_k−2+x_k−1. 이것은 단순히 0이 아닌 기수 a!=1에서 성분(x,x,....,x_1k−1)을₀ 길이 k의 입력 문자열의 문자로 사용하는 다항식입니다.해시 코드로 직접 사용하거나 해시 코드에 적용된 해시 함수를 사용하여 잠재적으로 큰 값을 해시 테이블 크기에 매핑할 수 있습니다.의 값은 일반적으로 잠재적인 키의 문자 집합에서 서로 다른 문자 수를 포함할 수 있는 최소 소수입니다.문자열의 기수 변환 해시는 ^[17]충돌 수를 최소화합니다.사용 가능한 데이터 크기에 따라 이 방법으로 해시할 수 있는 문자열의 최대 길이가 제한될 수 있습니다.예를 들어 128비트의 더블롱 워드는 26글자의 알파벳 문자열(대소문자 무시)만을 기수 29로 해시합니다.인쇄 가능한 ASCII 문자열은 기수 97 및 64비트 길이의 워드를 사용하여9글자로 제한됩니다.단, 키는 해시 테이블에 저장해야 하기 때문에 알파벳 키는 보통 적당한 길이입니다.숫자 문자열은 보통 문제가 되지 않습니다.64비트는 최대 10자리까지 카운트할 수 있습니다.기수 10에서는 19자리까지 카운트할¹⁹ 수 있습니다.

롤링 해시

서브스트링 검색 등의 일부 어플리케이션에서는 k자 너비의 창을 k자열을 따라 진행시킴으로써 소정의 n자열의 k자 서브스트링별로 해시함수 h를 계산할 수 있다.여기서 k는 고정정수이고 n은 k보다 크다.텍스트의 모든 문자 위치에서 이러한 하위 문자열을 추출하고 h를 별도로 계산하는 간단한 솔루션은 k·n에 비례하는 여러 연산을 필요로 한다.그러나 h를 적절하게 선택하면 mk + n에 비례하는 노력으로 모든 해시를 계산할 수 있습니다. 여기서 m은 서브스트링의 ^{[18][citation needed][what is the choice of h?]}발생 횟수입니다.

이 유형의 가장 친숙한 알고리즘은 최상의 경우 성능 O(n+mk)와 최악의 경우 O(n·k)를 가진 Rabin-Karp이다(모든 공정성 측면에서 최악의 경우 심각한 병리학적이며, 텍스트 문자열과 하위 문자열은 모두 t="와 같은 반복된 단일 문자로 구성되어 있다).AAAAAAAAAAA" 및 s="AAA".알고리즘에 사용되는 해시함수는 보통 8비트 문자열의 충돌을 피하기 위해 설계된 Rabin 핑거프린트이지만 다른 적절한 해시함수도 사용됩니다.

분석.

해시 함수의 최악의 경우 결과는 이론적인 것과 실제적인 것의 두 가지 방법으로 평가할 수 있습니다.이론적으로 최악의 경우는 모든 키가 단일 슬롯에 매핑될 확률입니다.실제 최악의 경우 가장 긴 프로브 시퀀스(해시 함수 + 충돌 해결 방법)가 예상됩니다.이 분석에서는 균일한 해시를 고려합니다.즉, 임의의 키가 유니버설해시 함수의 특징인 확률 1/m의 특정 슬롯에 매핑됩니다.

Knuth는 실시간 ^[19]시스템에 대한 적대적 공격에 대해 우려하는 반면, Gonnet은 이러한 사례가 발생할 가능성이 "터무니없이 작음"을 보여주었다.그의 표현은 k/n개의 키가 단일 슬롯에 매핑될 $확률$은 ${\displaystyle \frac{e^{}{}^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$ k$!$ ${\display$ {$frac {e^{-\alpha$}\$alpha$^{$k}{k!$$}}}$ 여기서 α는 하중 계수 n/^[20]m입니다.

역사

해시 함수가 입력 데이터를 스크램블하여 출력을 ^[21]도출하는 방법을 고려할 때 해시라는 용어는 비기술적 의미(뭔가를 잘라내거나 엉망으로 만드는 것)와 자연스럽게 유사합니다.Donald Knuth는 이 용어의 정확한 기원에 대한 연구에서 IBM의 Hans Peter Luhn이 1953년 1월 메모에서 해시함수의 개념을 최초로 사용한 것으로 보이지만, 이 용어 자체는 Herbert Hellerman's Digital Computer System Principles, Tho에서 1960년대 후반 출판된 문헌에만 등장할 것이라고 언급했습니다.그땐 ^[22]이미 널리 퍼진 용어들이었어

「 」를 참조해 주세요.

메모들

레퍼런스

외부 링크

• Timo Denk에 의해 지정된 값의 해시 계산
• 마유르 파텔의 Goulburn 해싱 함수(Goulburn Hashing Function)
• 텍스트 및 기하학적 데이터 검색(PDF)을 위한 해시함수 구축 컴퓨터 최신 동향, Vol.2, 페이지 483-489, CSCC Conference, Corfu, 2010