2D 평면에서 기하학적 점을 해시하는 방법은 무엇입니까?

Question

간단히 말하면, (x, y) 형태로 많은 점을가집니다.

나는 점은 키 인에 해시 테이블로 그 점을 넣고 싶다.

어떻게 클래스 Point의 hashCode() 메소드를 구현해야합니까? (당신이

public int hashCode() { 
    return x.hashCode()^y.hashCode(); 
} 

을이 테스트에 너무 많은 충돌을 제공하는 경우 : 나는 이중의 해시가 얼마나 잘 모르겠어요

class Point { 
    public double x; 
    public double y; 

    @Override 
    public int hashCode() { 
     // How do I implement here? 
    } 
} 

Answer 1

숫자 평면 좌표에 가장 클러스터링하는 경향이있다; 왜냐하면 편안한 범위 내에서 숫자를 사용하는 경향이 있기 때문입니다. 이러한 이유 때문에 사소한 xor 조합은 바람직하지 않습니다. x == y이 충돌 할 모든 숫자와 마찬가지로 모든 숫자는 x + 1 == y 등입니다.

이러한 문제가 발생하지 않도록하기 위해, 나는 당신이 x 좌표를에 xor 전에 y 좌표의 바이트를 반대하는 것이 좋습니다. 이것은 한 입력의 가장 가변적 인 영역 (하위 바이트)과 다른 입력의 가장 작은 가변성 (상위 바이트)의 영역을 결합합니다. 이러한 알고리즘은 숫자 클러스터 (1에서 1000 사이의 x 값)를 고려할 때보다 균일 한 분포를 제공합니다.

해시 알고리즘은 무거운 클러스터링없이 숫자 필드를 생성 할 때 가장 잘 작동하므로 해시 충돌이 적어 해시 관련 데이터 구조가 더 빨라집니다. 다음

는

물론, 최적화되지이다, 그리고 확률은 아마 당신은 당신의 필요에 맞게 트리밍 할 수 있지만, 여기에 기본 생각이다 :

public int hashCode() { 

    long bits = Double.doubleToLongBits(y); 
    byte[] ybits = new byte[] { 
     (byte)((y >> 56) & 0xff), 
     (byte)((y >> 48) & 0xff), 
     (byte)((y >> 40) & 0xff), 
     (byte)((y >> 32) & 0xff), 
     (byte)((y >> 24) & 0xff), 
     (byte)((y >> 16) & 0xff), 
     (byte)((y >> 8) & 0xff), 
     (byte)((y >> 0) & 0xff), 
    }; 
    byte[] xbits = new byte[] { 
     (byte)((x >> 56) & 0xff), 
     (byte)((x >> 48) & 0xff), 
     (byte)((x >> 40) & 0xff), 
     (byte)((x >> 32) & 0xff), 
     (byte)((x >> 24) & 0xff), 
     (byte)((x >> 16) & 0xff), 
     (byte)((x >> 8) & 0xff), 
     (byte)((x >> 0) & 0xff), 
    }; 
    // this combines the bytes of X with the reversed order 
    // bytes of Y, and then packs both of those into 4 bytes 
    // because we need to return an int (4 bytes). 
    byte[] xorbits = new byte[] { 
     (xbits[0]^ybits[7])^(xbits[4]^ybits[3]), 
     (xbits[1]^ybits[6])^(xbits[5]^ybits[2]), 
     (xbits[2]^ybits[5])^(xbits[6]^ybits[1]), 
     (xbits[3]^ybits[4])^(xbits[7]^ybits[0]), 
    }; 

    int value = 0; 
    for (int i = 0; i < 3; i++) { 
     value = (value << 8) + (by[i] & 0xff); 
    } 
    return value; 
} 

초기 최적화 나는를 캐시하는 것입니다 제안 후속 조회를 위해 오브젝트의 해시 코드를 작성하고, 프로파일 링이 문제가 있다고 제시하면 작성/삭제 된 어레이를보다 효율적으로 관리하십시오.

Answer 2

언어로 자바를 가지고,하지만 당신은 할 수 있어야 그게 맞습니까?) 비트 시프 팅, 매직 넘버 등으로 조금 다를 수 있습니다. 모든 종류의 비트 연산. 이 자바

인가? 나는 C#으로 내 경험에 대한 나의 대답을 근거로하고있다.

Answer 3

당신은 당신이 원하는 기능을 사용할 수 있습니다. 그것은 모두 좌표 값이 어떤 전형적인 값이고 해시 함수가 얼마나 좋은지에 달려 있습니다.

경우 예컨대 귀하의 모든 포인트는 1 백만에서 1 백만까지의 범위에 있으며, 다음과 같은 것을 사용할 수 있습니다 (이것은 C++ 코드이며, 사용하는 언어를 모르는 것입니다).

size_t hashCode = (size_t)x * (size_t)y; 

값을 추가하거나 값을 곱하거나 원하는대로 할 수 있습니다.

size_t hashCode = (size_t)(x+y); 

또는

size_t hashCode = (size_t)(x*y); 

또는

size_t hashCode = (size_t)(x*y) + (size_t)(x+y);