정수 전체 범위에 매핑

Question

나는 해시 테이블 (DotNET 사전 개체)을 스파 스 2 차원 데이터 집합의 일부로 사용하고 있습니다. 해시 테이블에있는 대부분의 항목은 서로 가깝게됩니다. 아마 100 ~ 10,000 개의 항목으로 끝날 것이고, 모두 0에 가깝게 흩어져 있습니다. 해쉬 테이블이 전체 정수 (32 비트) 범위에 퍼져있을 때 해시 테이블이 더 잘 수행된다는 것을 읽었습니다.

연속 된 정수를 1 : 1 방식으로 크게 다른 값에 매핑하는 저렴한 방법이 있습니까? 나는 그것들을 다시 매핑 할 필요가 없다. 그것은 단지 일방적 인 것이다.

Answer 1

Integer를 사용하는 대신 Integer에서 상속하는 클래스를 작성하고 GetHashCode 함수를 재정의하십시오. 이렇게하면 아무 것도 할 필요없이이 기능을 만들 수 있습니다! 내가 값을 확산하는 생각할 수

가장 쉬운 방법은 균등하게 그런 짓을하는 것입니다

public class MyInteger:Integer 
{ 
    public override int GetHashCode() 
    { 
     unchecked 
     { 
      return (int)Math.Pow(this,this); 
     } 
    } 
} 

니스와 최소의 노력을 유지하면서 균등 분할.

Answer 2

키 집합의 최대 값 (kmax)을 알고있는 경우 상수 요소 (배율)로 확장하거나, 제품을 최대 정수 크기 (2^31 - 1) 미만으로 유지하는 고정 소수로 곱할 수 있습니다) :

가장 가까운 소수 즉

주

(2^30)/kmax로 : 확실히 주요 사용이 해시 테이블의 버킷 수와 동일하지 않습니다합니다. 여기

다른 솔루션입니다 : 닷넷 Random 클래스는 같은 씨앗에 대해 동일한 값을 생성합니다 때문에, 당신은 입력 키를 배포하는 것을 사용할 수 있습니다.

Answer 3

어쩌면 나는 당신이 말하는 것을 오해하고 있습니다. 그러나 사전은 이미 정수를 해시합니다. 미리 해시 할 필요가 없습니다. 기본 구현을 시험해보고 무의미한 사전 최적화를 시도하는 대신 어떻게 진행되는지보십시오.