어떤 해시 함수가 "해킹"합니까?

Question

해시 함수는 데이터에 종속적 일 수 있습니다. 예를 들어 (this 기사에서) 데이터가 모든 문자열이고 거의 모든 길이가 다른 경우 간단한 문자열 길이는 매우 좋은 해시 함수가 될 수 있습니다 (사실은 아는 바가 없습니다).

값 * sizeOfHashTable

당신이 당신의 입력 주위에 만든 재단사가 같은 해시 함수를 사용하는 경우 내가 관심 : 또는 예를 들어 0에서 1의 실수는 간단한 해시 함수를 가질 수있다? 더 이상 예가 없습니까?

Answer 1

올바르게 설명한대로 해시 함수는 해시 데이터에 따라 다릅니다.

• 기능은 계산이 용이해야한다 : 3 조건을 준수 - 일반적인 생각은 좋은 해시 함수를 설계합니다. 어쩌면, 좋은 해시를 사용하지 않는 편이 좋지만 해시를 빠르게 계산하고 불균형 한 버킷이나 테이블 경로에서 손실 된 것보다 해싱에 더 많은 시간을 절약 할 수 있습니다.

• 함수는 테스트 데이터 집합에 올바른 분포 (의사 임의)가 있어야합니다. 좋은 아이디어 - 해시 함수 "snow-crash effect"에서 입력 데이터의 단일 비트를 변경하면 출력 값이 반으로 줄어 듭니다.

• 외부 입력 데이터의 경우 해시 함수가 "범용"이어야합니다. 즉 충돌 생성을 시도해야합니다.

내가 가장 좋아하는 해시 기능은 다음과 같습니다. 처음 사용하기 전에 임의의 값을 사용하여 테이블 S_block을 초기화해야합니다. 각 프로그램을 실행할 때마다 실행하는 것이 좋습니다.

const unsigned int S_block[256] = { ... }; 
#define NLF(h, c) (S_block[(unsigned char)(c + h)]^c) 

unsigned int hash(const char *key) { 
unsigned int h = 0x1F351F35; 
char c; 
while(c = *key++) 
    h = ((h << 7) | (h >> (32 - 7))) + NLF(h, c); 
h ^= h >> 16; 
return h^(h >> 8); 
} 

실시 예로서, 내 프로그램 emcSSH이 함수의 변화량을 이용하여 참조. htable.c 파일에는 double hashing 알고리즘에 적합한이 함수의 변형이 포함되어 있습니다.