해싱은 해시 함수로 알려진 수학 함수를 사용하여 텍스트 또는 숫자 목록에서 값을 생성하는 프로세스입니다. 숫자 또는 영숫자 키를 사용하는 많은 해시 함수가 있습니다. 다양한 해시 함수는 다음과 같습니다.
해시 함수
다음은 해시 함수의 일부입니다 -
분할 방식
이것은 해시 함수를 생성하는 가장 쉬운 방법입니다. 해시 함수는 다음과 같이 설명할 수 있습니다. -
h(k) = k mod n
여기서 h(k)는 키 값 k를 나머지를 이용하여 해시 테이블 n의 크기로 나눈 해시 값이다. 키가 더 균일하게 분포되도록 하려면 n이 소수인 것이 가장 좋습니다.
나눗셈 방법의 예는 다음과 같습니다 -
k=1276 n=10 h(1276) = 1276 mod 10 = 6
획득한 해시 값은 6
연속 키가 해시 테이블의 연속 해시 값에 매핑되는 분할 방법 ID의 단점. 이는 성능 저하로 이어집니다.
곱셈 방법
곱셈 방법에 사용되는 해시 함수는 -
h(k) = floor( n( kA mod 1 ) )
여기서 k는 키이고 A는 0과 1 사이의 상수 값일 수 있습니다. k와 A는 모두 곱해지고 소수 부분은 분리됩니다. 그런 다음 해시 값을 얻기 위해 n을 곱합니다.
곱셈 방법의 예는 다음과 같습니다 -
k=123 n=100 A=0.618033 h(123) = 100 (123 * 0.618033 mod 1) = 100 (76.018059 mod 1) = 100 (0.018059) = 1
획득한 해시 값은 1
곱셈 방법의 장점은 일부 값이 다른 값보다 더 나은 것으로 여겨지지만 A의 모든 값과 함께 작동할 수 있다는 것입니다.
중간 제곱법
mid square 방법은 아주 좋은 해시 함수입니다. 키 값을 제곱한 다음 중간 r자리 숫자를 해시 값으로 추출하는 작업이 포함됩니다. r의 값은 해시 테이블의 크기에 따라 결정될 수 있습니다.
Mid Square Method의 예는 다음과 같습니다 -
해시 테이블에 100개의 메모리 위치가 있다고 가정합니다. 따라서 r=2 키를 메모리 위치에 매핑하려면 두 자리 숫자가 필요하기 때문입니다.
k = 50 k*k = 2500 h(50) = 50 The hash value obtained is 50
해시 테이블
해시 테이블은 키를 값에 매핑하는 데이터 구조입니다. 해시 함수를 사용하여 데이터 키에 대한 인덱스를 계산하고 키가 인덱스에 저장됩니다.
해시 테이블의 예는 다음과 같습니다 -
해시 테이블에 저장해야 하는 키 시퀀스는 -
35 50 11 79 76 85
사용된 해시 함수 h(k)는 다음과 같습니다.
h(k) = k mod 10
선형 프로빙을 사용하여 값은 해시 테이블에 −
로 저장됩니다.
