벡터 해시의 기본 개념

Question

조회 및 정보 검색에 대한 해싱 기술을 배우고 있습니다. 하지만 깊이 파헤 치기 전에 일반적으로 해시 함수에 대한 특정 개념과 혼동합니다.

말은 부동 소수점 값의 벡터 인 x입니다. xi = [x_1,x_2,...,x_L]입니다. 벡터의 크기는 L입니다. 예를 들어 X = [x1,x2,..,x_N]이라고도하는 이러한 벡터가 N입니다. 쿼리 벡터 p이 주어지면 쿼리와 일치하는 가장 가까운/가장 가까운 예제를 찾아야합니다. 여러 가지 읽기 자료를 살펴보면 테이블 크기가 M=10 (말) 일 때 가장 간단한 (그러나 비효율적 인) 해싱 함수는 h(x) = x mod M입니다.

x mod M가 M으로 나누었을 때, 다음 x mod M 항상 0 및 M -1 사이에있을 것입니다 x의 나머지, 우리는 항상 M 슬롯 중 하나에 정수를 매핑 할 수 있습니다. 내 질문 :

질문 1 : 계수는 테이블 크기에 대해 수행됩니다. 그러나 각 샘플 길이가 L이고 해당 샘플이 N 인 경우 모듈 숫자가 무엇입니까? 하겠습니까 h(x) = x mod vector length

또는 h(x) = xmod number of examples?

일반적으로 암호화 응용 프로그램에서는 각 블록의 크기가 8 비트이므로 mod 256이 사용됩니다. 이것은 계수가 벡터의 길이에 걸쳐 취해진다는 것을 의미합니까? 잘못하면 나를 바로 잡으십시오.

질문 2 : 많은 예제에서 입력 값이 ASCII 값 또는 정수로 표시되므로 부동 소수점 숫자를 정수로 변환해야합니까?

질문 3 : 해쉬 함수가 h(x) = 2*x mod 1 인 경우, [0,1] 범위의 부동 소수점 숫자가 생성됩니다. H(x) = round(h(x))을 사용하여 정수로 변환 할 수 있습니다. 메시지 예제가 x 인 경우 길이가 각각 L 인 k 블록으로 분할 된 경우 k 해시 함수가 필요합니까? 이 예제의 해쉬 함수에 대한 제안. 고맙습니다.

Answer 1

그래서 해시 테이블을 만들 때 그것은 단지 배열이며 해시 함수는 객체를 취하고 객체 속성을 기반으로 integer mod (length of array)을 반환합니다. 따라서 부동 소수점 숫자에 대해 걱정하지 마십시오! 구현 방법에 대한 제안을 원할 경우 여기에 제가 할 일이 있습니다.

먼저 해시 테이블을 얼마나 길게 할 것인지 계산합니다. 일반적으로 해시 테이블을 두 번 올리면 (또는 더 길게 입력하는 것이 좋은 선택입니다). 그것은 단지 타입 벡터 (또는 당신이 저장하고있는 객체)의 배열 일 것이다.

다음으로 해시 함수를 만들고 싶을 것입니다. 해시 함수를 디자인 할 때 큰 소수를 사용하고 객체의 다른 부분을 곱하여 모든 것을 추가하는 것이 좋습니다. 예를 들어 ...

int total = 0 
for each floatingptNum currentVector: 
    total = total + 129 * currentFloatingptNum 

return total % lengthOfArray 

는 suedo 코드의 아주 기본적인 해시 함수 (사용중인 언어를 확인하지 않음)하지만 한 당신있는 거 배열의 범위 내에서 당신에게 정수를주기 때문에, 단지 그 , 너 세트 야!

우리가 큰 소수를 사용하는 이유는 최대한 두 개의 충돌 값 (두 개의 개별 값이 같은 위치로 매핑되는 경우)을 얻지 만 이러한 것들은 거의 항상 발생해야한다는 것을 명심하십시오. 한 가지 해결책은 bucket or chain hashing입니다. 이것은 기본적으로 벡터 배열 대신 해시 테이블의 동일한 지점에 두 개의 다른 벡터를 저장할 수있는 유일한 목적으로 벡터의 연결된 목록 배열을 갖게됨을 의미합니다.

많은 정보가 있지만 도움이되기를 바랍니다. 해피 해싱!