char의 위치를 ​​존중하지 않는 문자열의 해시 함수

Question

제 질문의 제목은 자기 설명 적입니다. 3 개의 64 비트 변수 구조를 해시 할 필요가 있습니다 (각 문자열을 문자로 변환합니다). 각각 하나의 카드 - 카드 게임 앱이 포함되어 있으므로 이러한 변수에서 일부 문자를 서로 바꿔야 동일한 해시를 생성 할 수 있습니다. 한 가지 방법은 결과 문자열을 정렬하는 것입니다. 더 나은 해결책이 있습니까?

Answer 1

손 모양이 비트 세트와 비슷하면 이미 순서가 지정되어 있습니다. 당신은 카드의 조합을 나타내는 비트 마스크의 조합을 사용하는 경우이

A♠ - 0x00000001 
2♠ - 0x00000002 
3♠ - 0x00000004 
4♠ - 0x00000008 
... 
K♠ - 0x00001000 
A♥ - 0x00002000 
2♥ - 0x00004000 
... 

는 다음 비트의 조합을 사용하여 손을 나타낼 수처럼 예를 들어, 다음과 같이 말한다 :

A♠ 4♠ 2♥ - 0x00004009 

이 표현 위치가 독립적이므로 핸드 4♠ A♠ 2♥ 및 2♥ 4♠ A♠은 정확히 A♠ 4♠ 2♥과 같은 표현을 갖습니다. 이 표현을 개별 비트 반복을 통해 필요에 따라 문자열로 변환하고 1로 설정된 비트를 발견 할 때마다 문자열 표현에 카드를 추가 할 수 있습니다.

이 표현은 다음과 같이 계산할 수 있습니다 하위 32 비트로 표현의 상위 32 개 비트를 XOR이 한창 의해 32 비트 해시 코드 :

uint64_t hand = ... // A representation of hand similar to what's described above 
uint32_t hash = (uint32_t)(hand^(hand >> 32)); 

현 내 카드 바이트로 표현되지만, 두 카드에서의 비트는 중첩 할 수 A♣ = 0x11; 10♣=0x12; K♣=0x13있다. .. 등등.

당신은 해시 코드를 계산할 때 위에서 설명한 하나에이 표현을 변환하고, 그런 식으로 정렬 피할 수

:

// Each card is a number from 1 to 53, inclusive 
uint8_t hand[HAND_SIZE] = ...; // The hand 
uint64_t set = 0; 
for (int i = 0 ; i != HAND_SIZE ; i++) { 
    set |= (1LL << hand[i]); 
} 
uint32_t hash = (uint32_t)(set^(set >> 32)); 

Answer 2

이 작업을 수행하는 다른 방법은 각각의 발생 수를 계산하는 것입니다 문자를 찾은 다음 결과 벡터를 해시합니다 (벡터 count, count[c]은 문자 발생 횟수를 나타냅니다) c. 나는 그것이 정렬보다 낫다는 것을 말하지 않을 것이다. (문자의 수는 고정되어 있고 (아마 꽤 낮다) 그래서 기수 정렬을 사용할 수있다.) 그러나 (나는 더 나쁜 것도 말할 수 없다). 기수 정렬을 사용한 정렬과 각 문자의 발생 횟수 계산은 선형입니다 (또한 기수 정렬 및 계수 문자는 거의 동일합니다). 따라서이 두 가지 사이에는 큰 차이가 없어야합니다.