(대부분) 기본 값으로 구성된 구조체를 고유하게 식별하는 32 비트 해시 코드를 빠르게 생성합니다.

Question

EDIT : 64 또는 128 비트도 사용할 수 있습니다. 어떤 이유로 든 내 뇌가 32 비트로 뛰어 올라서 충분하다고 생각했습니다.

대부분 숫자 값 (int, decimal)으로 구성된 구조체와 각기 12 자 이상의 알파 문자가 아닌 3 개의 문자열이 있습니다. 나는 해시 코드로 작동 할 정수 값을 만들고, 그것을 빠르게 만들려고 노력하고있다. 일부 숫자 값도 Null 가능합니다.

BitVector32 또는 BitArray가이 엔데버에서 사용하기에 유용한 엔티티 인 것처럼 보이지만이 작업에서 자신의 의지로 어떻게 구부릴 수 있는지 잘 모르겠습니다. 내 구조체에는 3 개의 문자열, 12 개의 십진수 (7 개는 null 입력 가능) 및 4 개의 int가 들어 있습니다.

public struct Foo 
{ 
    public decimal MyDecimal; 
    public int? MyInt; 
    public string Text; 
} 

나는 각 값에 대해 숫자 식별자를 얻을 수 있습니다 알고 내 사용 사례를 단순화하기 위해

, 당신은 다음과 같은 구조체가 있다고 할 수 있습니다. MyDecimal과 MyInt는 물론 수치 적 관점에서 독특합니다. 문자열에는 일반적으로 고유 한 값을 반환하는 GetHashCode() 함수가 있습니다.

그래서 각 숫자 식별자로이 구조를 고유하게 식별하는 해시 코드를 생성 할 수 있습니까? 예 : 동일한 값을 포함하는 2 개의 다른 Foo를 비교하고 매번 동일한 해시 코드 (앱 도메인, 앱 재시작, 시간, Jupiters 달 정렬 등에 관계없이)를 얻을 수 있습니다.

해시가 희박하므로 사용 사례와의 충돌을 예상하지 못합니다.

아이디어가 있으십니까? 내 첫 번째 실행에서 모든 문자열 표현, concated 및 내장 된 GetHashCode() 사용했지만 몹시 비효율적 인 것 같습니다.

편집 : 조금 더 배경 정보. 구조 데이터가 웹 클라이언트에게 전달되고 클라이언트는 포함 된 값, 문자열 생성 등을 계산하여 페이지를 다시 렌더링합니다. 앞서 언급 한 19 개의 필드 구조는 정보의 단일 단위를 나타내며, 각 페이지는 많은 단위를 가질 수 있습니다. 렌더링 된 결과의 일부 클라이언트 측 캐싱을 수행하고 싶습니다. 따라서 서버에서 동일한 해시 식별자를 보면 클라이언트 측에서 다시 계산하지 않고 장치를 신속하게 다시 렌더링 할 수 있습니다. JavaScript 숫자 값은 모두 64 비트이므로 제 32 비트 제약 조건은 인위적이고 제한적이라고 생각합니다. 64 비트가 작동하거나 서버의 두 64 비트 값으로 나눌 수 있다면 128 비트라고 가정합니다.

Answer 1

음, 시간이 지남에 따라 안정 필요 "희박한"의미에 따라 충돌을 대비하십시오.

당신은 당신이 32 비트와이 그래프를 이길 동시에 해시 할 데이터에 대한 매우 특정 가정을 할 수 있어야합니다.

SHA256과 함께 사용하십시오. 해시는 CLR 버전에 의존하지 않으므로 충돌이 발생하지 않습니다. 글쎄, 당신은 아직도, 그러나 덜 자주 운석 영향보다, 그래서 당신은 어떤 기대하지 여유가 있습니다.

Answer 2

두 가지 사항은 here과 here을 살펴 보는 것이 좋습니다. 나는 당신이 단지 32 비트로 충돌을하지 않을 것이라고 생각하지 않는다.

Answer 3

.NET의 일반적인 방법은 구조체의 각 구성원에 GetHashCode를 호출하고 xor를 호출하는 것입니다.

그러나 GetHashCode가 다른 앱 도메인에서 동일한 값에 대해 동일한 해시를 생성한다고 생각하지 않습니다.

당신이 해시 값을 원하는 이유에 대해 귀하의 질문에 좀 더 많은 정보를 제공 할 수 그리고 왜 하나는해야 더 나은조차 스파 스 테이블에서 서로 다른 응용 프로그램 도메인 등

Answer 4

어떤 목표를 쫓고 있습니까? 그것이 성능이라면 함수 매개 변수로 전달할 때마다 구조체가 값에 의해 복사되므로 클래스를 사용해야합니다.

문자열 3 개, 십진수 12 개 (7 개는 null 입력 가능) 및 4 개의 정수입니다.

64 비트 컴퓨터에서 포인터는 8 바이트 크기이며 십진수는 16 바이트이고 int는 4 바이트입니다. 패딩을 무시하면 struct 당 232 바이트가 사용됩니다.. 16 바이트의 권장 최대 값과 비교하면 훨씬 더 큽니다. (객체 헤더로 인해 클래스가 적어도 16 바이트를 차지합니다 ...)

사용할 수있는 지문이 필요한 경우 16 바이트 지문을 생성하는 SHA256과 같은 암호화 등급의 해시 알 고입니다. 이것은 아직 고유하지는 않지만 적어도 충분히 독특합니다. 그러나 이것은 상당한 성능을 요구할 것입니다.

편집 1 : 자바 스크립트 웹 클라이언트 캐시에서 개체를 식별하기 위해 해시 코드가 필요하다는 것을 분명히 한 후에 혼란 스럽습니다. 왜 서버가 동일한 데이터를 다시 보냅니 까? 클라이언트가 아직받지 못한 데이터 만 보내도록 서버를 더 스마트하게 만드는 것이 더 간단하지 않습니까?

SHA 해시 알고리즘을 사용하면 일부 개체 인스턴스 태그를 생성 할 수 있습니다.

---

왜 해시 코드가 필요합니까? 값을 메모리 효율적인 방식으로 저장하는 것이 목표라면 사전을 사용하여 동일한 값을 한 번만 저장하고 조회 키로 int를 사용하는 FooList를 만들 수 있습니다.

using System; 
using System.Collections.Generic; 

namespace MemoryEfficientFoo 
{ 
    class Foo // This is our data structure 
    { 
     public int A; 
     public string B; 
     public Decimal C; 
    } 

    /// <summary> 
    /// List which does store Foos with much less memory if many values are equal. You can cut memory consumption by factor 3 or if all values 
    /// are different you consume 5 times as much memory as if you would store them in a plain list! So beware that this trick 
    /// might not help in your case. Only if many values are repeated it will save memory. 
    /// </summary> 
    class FooList : IEnumerable<Foo> 
    { 
     Dictionary<int, string> Index2B = new Dictionary<int, string>(); 
     Dictionary<string, int> B2Index = new Dictionary<string, int>(); 

     Dictionary<int, Decimal> Index2C = new Dictionary<int, decimal>(); 
     Dictionary<Decimal,int> C2Index = new Dictionary<decimal,int>(); 

     struct FooIndex 
     { 
      public int A; 
      public int BIndex; 
      public int CIndex; 
     } 

     // List of foos which do contain only the index values to the dictionaries to lookup the data later. 
     List<FooIndex> FooValues = new List<FooIndex>(); 

     public void Add(Foo foo) 
     { 
      int bIndex; 
      if(!B2Index.TryGetValue(foo.B, out bIndex)) 
      { 
       bIndex = B2Index.Count; 
       B2Index[foo.B] = bIndex; 
       Index2B[bIndex] = foo.B; 
      } 

      int cIndex; 
      if (!C2Index.TryGetValue(foo.C, out cIndex)) 
      { 
       cIndex = C2Index.Count; 
       C2Index[foo.C] = cIndex; 
       Index2C[cIndex] = cIndex; 
      } 

      FooIndex idx = new FooIndex 
      { 
       A = foo.A, 
       BIndex = bIndex, 
       CIndex = cIndex 
      }; 

      FooValues.Add(idx); 
     } 

     public Foo GetAt(int pos) 
     { 
      var idx = FooValues[pos]; 
      return new Foo 
      { 
       A = idx.A, 
       B = Index2B[idx.BIndex], 
       C = Index2C[idx.CIndex] 
      }; 
     } 

     public IEnumerator<Foo> GetEnumerator() 
     { 
      for (int i = 0; i < FooValues.Count; i++) 
      { 
       yield return GetAt(i); 
      } 
     } 
     System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
     { 
      return GetEnumerator(); 
     } 
    } 


    class Program 
    { 
     static void Main(string[] args) 
     { 
      FooList list = new FooList(); 
      List<Foo> fooList = new List<Foo>(); 
      long before = GC.GetTotalMemory(true); 
      for (int i = 0; i < 1000 * 1000; i++) 
      { 
       list 
       //fooList 
        .Add(new Foo 
        { 
         A = i, 
         B = "Hi", 
         C = i 
        }); 

      } 
      long after = GC.GetTotalMemory(true); 
      Console.WriteLine("Did consume {0:N0}bytes", after - before); 
     } 
    } 
} 

유사한 메모리 보존 목록은 해시 함수의 정의에 의해 here

Answer 5

해시 코드를 찾을 수 있습니다 것은 고유 의미하지 않는다. 그것들은 가능한 한 모든 결과 값에 고르게 분포되도록 의도 된 것입니다. 객체의 해시 코드를 얻는 것은 입니다. 두 객체가 이 다른 경우인지 확인하는 방법은입니다. 두 객체의 해시 코드가 다른 경우 해당 객체가 다릅니다. 그러나 해시 코드가 동일하면 객체를 깊이 비교해야합니다. 해시 코드의 주요 용도는 거의 모든 O (1) 검색 속도를 가능하게하는 모든 해시 기반 컬렉션에 있습니다.

이 점에서 귀하의 GetHashCode은 복잡 할 필요는 없으며 사실 그렇게해서는 안됩니다. 매우 신속하고 균등하게 분산 된 값을 생성하는 것 사이에서 균형을 유지해야합니다. 해시 코드를 얻는 데 너무 오래 걸리면 심한 비교를 통한 이점이 사라 지므로 무의미 해집니다.다른 극단에서 해시 코드가 항상 1 (예 : 빠른 조명) 인 경우이 해시 코드를 무의미하게 만드는 모든 경우에 심층적 인 비교가 이루어집니다.

그래서 균형을 올바르게 잡으시 고 완벽한 해시 코드를 제시하지 마십시오. 모든 구성원 (또는 대부분)에 GetHashCode으로 전화하여 Xor 연산자를 사용하여 비트 단위 시프트 연산자 << 또는 >>을 조합하여 결과를 결합하십시오. 프레임 워크 유형은 GetHashCode이 완벽하게 최적화되어 있지만 각 응용 프로그램 실행에서 동일하게 보장되지는 않습니다. 보장은 없지만 변경하지 않아도되며 많은 사람들이 변경하지 않아도됩니다. 리플렉터를 사용하여 반영된 코드를 기반으로 자신 만의 버전을 만들거나 만들 수 있습니다.

해시 코드를보고 구조를 이미 처리했는지 결정하는 것은 약간 위험합니다. 해시가 좋을수록 위험은 작지만 여전히 작습니다. 궁극적 인 유일한 해시 코드는 데이터 자체입니다. 해시 코드로 작업 할 때는 코드가 실제로 신뢰할 수 있도록 Object.Equals을 다시 정의해야합니다.