Jak obliczyć dobry kod hash dla listy ciągów?

Nie widzę powodu, aby nie łączyć łańcuchów i obliczać hashcode dla konkatenacji.

Jako analogię, powiedzmy, że chciałem obliczyć sumę kontrolną MD5 dla bloku pamięci, nie dzieliłbym bloku na mniejsze kawałki i obliczał dla nich poszczególne sumy kontrolne MD5, a następnie łączył je z jakąś metodą ad hoc.

Twoja pierwsza opcja ma jedyną niedogodność związaną z (String1, String2) tworzeniem tego samego hashcode (String2, String1). Jeśli to nie problem (np. bo masz zlecenie fix) jest w porządku.

"Cat wszystkie ciąg razem następnie uzyskać hashcode " wydaje się bardziej naturalne i bezpieczne dla mnie.

Update: jak zauważono w komentarzu, ma to tę wadę, że lista ("x", "yz") i ("xy","z") dałaby ten sam hash. Aby tego uniknąć, można połączyć ciągi za pomocą ogranicznika łańcucha, który nie może pojawić się wewnątrz napisów.

Jeśli ciągi znaków są duże, możesz chcieć hashować każdy z nich, cat hashcodes i ponownie dodać wynik. Więcej procesora, mniej pamięci.

Inny sposób, który pojawia się w mojej głowie, łańcuch xorów z obracanymi hashami na podstawie indeksu:

int shift = 0;
int result = 1;
for(String s : strings)
{
    result ^= (s.hashCode() << shift) | (s.hashCode() >> (32-shift)) & (1 << shift - 1);
    shift = (shift+1)%32;
}

Edit: czytając Wyjaśnienie podane w efektywnej Javie, myślę, że kod Geoffa byłby znacznie wydajniejszy.

Rozwiązanie oparte na SQL może być oparte na funkcjach checksum i checksum_agg. Jeśli dobrze nadążam, to masz coś w stylu:

MyTable
  MyTableId
  HashCode

MyChildTable
  MyTableId  (foreign key into MyTable)
  String

Z różnymi łańcuchami dla danego elementu (MyTableId) przechowywanymi w MyChildTable. Aby obliczyć i zapisać sumę kontrolną odzwierciedlającą te (nigdy nie zmieniane) ciągi, coś takiego powinno działać:

UPDATE MyTable
 set HashCode = checksum_agg(checksum(string))
 from MyTable mt
  inner join MyChildTable ct
   on ct.MyTableId = mt.MyTableId
 where mt.MyTableId = @OnlyForThisOne

Uważam, że jest to niezależne od kolejności, więc ciągi " the quick brown "dałyby taką samą sumę kontrolną jak"brown the quick".

Mam nadzieję, że jest to niepotrzebne, ale ponieważ nie wspominasz o niczym, co brzmi jakbyś używał hashcodes tylko do pierwszego sprawdzenia, a następnie sprawdzenia, czy ciągi są rzeczywiście równe, czuję potrzebę, aby cię ostrzec:

równość Hashcode != równość wartości

Będzie wiele zestawów łańcuchów, które dadzą identyczny hashcode, ale nie zawsze będzie równy.

Więc rozumiem, że faktycznie masz jakiś zestaw ciągów znaków, które musisz zidentyfikować za pomocą kodu hashowego, a ten zestaw ciągów, które musisz zidentyfikować, nigdy się nie zmieni?

Jeśli tak jest, nie ma to szczególnego znaczenia, o ile schemat, którego używasz, daje unikalne liczby dla różnych ciągów / kombinacji ciągów. Zacząłbym od konkatenacji strun i obliczenia strun.hashCode () i sprawdzanie, czy masz unikalne numery. Jeśli nie, wtedy możesz spróbować:

• zamiast łączenia łańcuchów, połącz kody hashowe łańcuchów składowych i spróbuj różnych mnożników (np. jeśli chcesz zidentyfikować kombinacje ciągów dwu ciągowych, spróbuj HC1 + 17 * HC2, jeśli to nie daje unikalnych liczb, spróbuj HC1 + 31 * HC2, następnie spróbuj 19, następnie spróbuj 37 itd. - zasadniczo każda mała Nieparzysta liczba będzie dobra).
• jeśli nie masz unikalnych liczb w ten sposób-- lub jeśli musisz poradzić sobie z zestawem możliwości Rozszerzanie-- następnie rozważ mocniejszy kod hashowy. 64-bitowy kod hashowy jest dobrym kompromisem między łatwością porównywania a prawdopodobieństwem unikalności skrótów.

Możliwy schemat dla 64-bitowego kodu hashowego jest następujący:

• generowanie tablicy 256 64-bitowych liczb losowych przy użyciu dość silnego schematu (można użyć SecureRandom, choć schemat XORShift będzie działał dobrze)
• Wybierz "m", kolejną "losową" 64-bitową, nieparzystą liczbę z mniej więcej połową swoich bitów set
• aby wygenerować kod skrótu, przejdź do każdej wartości bajtu, b, tworzącej łańcuch, i weź liczbę bth z tablicy liczb losowych; następnie XOR lub dodaj ją z bieżącą wartością skrótu, pomnożoną przez " m "

Więc implementacja oparta na wartościach sugerowanych w numerycznych recepturach byłaby:

  private static final long[] byteTable;
  private static final long HSTART = 0xBB40E64DA205B064L;
  private static final long HMULT = 7664345821815920749L;

  static {
    byteTable = new long[256];
    long h = 0x544B2FBACAAF1684L;
    for (int i = 0; i < 256; i++) {
      for (int j = 0; j < 31; j++) {
        h = (h >>> 7) ^ h;
        h = (h << 11) ^ h;
        h = (h >>> 10) ^ h;
      }
      byteTable[i] = h;
    }
  }

Powyższe inicjalizuje naszą tablicę liczb losowych. Używamy generatora XORShift, ale naprawdę możemy użyć dowolnego dość dobrej jakości generatora liczb losowych (tworząc SecureRandom () z określonym nasieniem, a następnie wywołanie nextlong () byłoby w porządku). Następnie, aby wygenerować kod hashowy:

  public static long hashCode(String cs) {
    if (cs == null) return 1L;
    long h = HSTART;
    final long hmult = HMULT;
    final long[] ht = byteTable;
    for (int i = cs.length()-1; i >= 0; i--) {
      char ch = cs.charAt(i);
      h = (h * hmult) ^ ht[ch & 0xff];
      h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
    }
    return h;
  }

Przewodnikiem do rozważenia jest to, że biorąc pod uwagę kod haszujący N bitów, można oczekiwać, że będziesz musiał wygenerować hasze w kolejności 2^(n/2) łańcuchów, zanim dojdzie do kolizji. Albo Inaczej mówiąc, z 64-bitowym Hashem, spodziewałbyś się kolizji po około 4 miliardach ciągów (więc jeśli masz do czynienia z, powiedzmy, kilkoma milionami ciągów, szanse na kolizję są następujące dość znikoma).

Inną opcją byłoby MD5, który jest bardzo silnym Hashem (praktycznie bezpiecznym), ale jest to 128-bitowy hash, więc masz niewielką wadę radzenia sobie z wartościami 128-bitowymi. Powiedziałbym, że MD5 jest przesadą do tych celów-jak mówię, z 64-bitowym Hashem, można poradzić sobie dość bezpiecznie w kolejności kilku milionów ciągów.

(Przepraszam, powinienem wyjaśnić -- MD5 został zaprojektowany jako bezpieczny hash, po prostu okazało się, że nie jest bezpieczny. "Bezpieczny" hash to taki, w którym biorąc pod uwagę konkretny hash, nie jest możliwe celowe skonstruowanie danych wejściowych, które doprowadziłyby do tego hasha. W pewnych okolicznościach, ale nie tak, jak rozumiem w Twoim, potrzebowałbyś tej własności. Z drugiej strony, jeśli Ciągi, z którymi masz do czynienia, to dane wejściowe użytkownika-np. złośliwy użytkownik może celowo spróbować zmylić Twój system. Możesz być również interetowany w następujących pisanych w przeszłości:

• przewodnik po hash kody
• secure hash codes in Java (includes some performance measurements)

Użycie GetHashCode() nie jest idealne do łączenia wielu wartości. Problem polega na tym, że dla ciągów, hashcode jest tylko sumą kontrolną. To pozostawia niewiele entropii dla podobnych wartości. np. dodanie hashcodów dla ("abc", "bbc") będzie takie samo jak ("abd", "abc"), powodując kolizję.

W przypadkach, w których musisz być absolutnie pewien, używasz prawdziwego algorytmu hash, takiego jak SHA1, MD5 itp. Jedynym problemem jest to, że są to funkcje blokowe, co jest trudne do szybkiego porównania hashów dla równość. Zamiast tego spróbuj użyć skrótu CRC lub fnv1 . FNV1 32-bit jest super prosty:

public static class Fnv1 {
    public const uint OffsetBasis32 = 2166136261;
    public const uint FnvPrime32 = 16777619;

    public static int ComputeHash32(byte[] buffer) {
        uint hash = OffsetBasis32;

        foreach (byte b in buffer) {
            hash *= FnvPrime32;
            hash ^= b;
        }

        return (int)hash;
    }
}

Możesz użyć poniższej metody, aby połączyć kody hash: http://docs.oracle.com/javase/7/docs/api/java/util/Objects.html#hash(java.lang.Object...)

Rozwiążmy twój problem.

Nie używaj hashcode. Po prostu dodaj klucz podstawowy integer dla każdego ciągu