Hashing zestaw liczb całkowitych w sposób niezależny od zamówienia

Question

Chcę hash zestaw liczb całkowitych tak, że kolejność liczb całkowitych nie mają wpływu na obliczoną wartość mieszania. tj. H([32224,12232,564423]) == H([564423,32224,12232]).

Liczba unikatowych zestawów będzie w zakresie kilku milionów. Prędkość to bardzo ważne, ale muszę znać górną granicę w przypadku kolizji z wybranym podejściem.

Wikipedia ma dobrą sekcję na temat hashing vectors, ale nie rozumiem matematyki za nią, aby pewnie wdrożyć je w kodzie. Byłbym wdzięczny, gdyby ktoś mógł wyjaśnić matematykę związaną z jakimś kodem. Najlepiej byłoby, gdyby końcowy skrót miał 32 bity. Jeśli jest to przydatne - będę to implementował w Javie.

Aktualizacja: Aktualizacja: Staram się unikać sortowania liczb całkowitych w zestawie, ze względu na wydajność (działa na wielu takich zestawach).

Answer 1

Możesz umieścić wszystkie liczby całkowite w Java HashSet i użyć jego hashCode.

Z drugiej strony, java.util.Set nie określa następujące w dokumentach:

Zwraca kod skrótu dla tego zestawu. Kod skrótu zestawu to zdefiniowany jako suma kodów skrótów elementów w zestawie, gdzie kod skrótu elementu zerowego jest zdefiniowany jako zero. Ten zapewnia, że ​​s1.equals (s2) implikuje, że s1.hashCode() == s2.hashCode() dla dowolnych dwóch zestawów s1 i s2, zgodnie z wymogami generalnej umowy z Object.hashCode().

I Integer.hashCode(), to wówczas

wartość kod skrótu dla tego obiektu, równa pierwotnej int wartości reprezentowane przez obiekt całkowitą.

Zatem hashCode do zbioru liczb całkowitych i1, i2, ... i_n w standardowej biblioteki Java jest i1 + i2 + ... + i_n.

W przypadku, gdy liczby są raczej małe, można także pomnożyć każdy element za pomocą odpowiedniej liczby pierwszej. Knuth użył 2654435761, który jest zbyt duży dla int java, ale możesz wziąć jego 2-dopełnienie, -1640531527. Zatem weź C = -1640531527, a następnie twój kod to C*i1 + C*i2 + ... C*i_n.

private static final int C = -1640531527; 

public static int calculateHash(int[] set) { 
    int code = 0; 
    for (int e: set) { 
     code += C * e; 
    } 

    return code; 
} 

Jednak istnieje 1 oczywisty błąd w myśleniu. Aby skorzystać z hashCode, musisz udowodnić, że 2 zestawy są rzeczywiście równe, więc w każdym razie najprostszym sposobem udowodnienia jest posortowanie elementów. Oczywiście, jeśli istnieje znacznie mniej niż miliony zestawów, nie ma też zbyt wielu kolizji.

Answer 2

Proste podejście polega na dodaniu xor lub dodaniu skrótów poszczególnych liczb całkowitych. xor i add są przemienne, więc to spełnia niezależność od zamówienia.

Zatem:

int hc = 0; 
for(int i = 0; i < n; i++) { 
    hc += a[i]; 
} 
return hc; 

lub

int hc = 0; 
for(int i = 0; i < n; i++) { 
    hc ^= a[i]; 
} 
return hc; 

ponieważ kod hash int jest jego wartość i tak.

W rzeczywistości jest to dokładnie co zrobi HashSet<Integer>.hashCode (używa Dodaj). Jeśli twoje liczby całkowite są już w pudełku lub możesz obsłużyć je, to jest to wbudowane rozwiązanie.

Answer 3

Zakładając trzeba prędkość bez obciążania *Set klas, a następnie można napisać H następująco:

/** 
* Hashes a set of integers. 
* 
* @param list to hash 
* @return hash code 
*/ 
public static int H(int list[]) { 
    // XOR all the integers together. 
    int hashcode = 0; 
    for (int val : list) { 
     hashcode ^= val; 
    } 
    return hashcode; 
} 

To jest taka sama niezależnie od kolejności, i to jest stosunkowo wydajny.

Na przykład:

public static void main(String[] args) { 
    System.out.println(Integer.toHexString(H(new int[]{0xabcd,0x1234,0x1111}))); 
    System.out.println(Integer.toHexString(H(new int[]{0x1234,0x1111,0xabcd}))); 
} 

Wyświetla:

a8e8 
a8e8 

ten można uogólnić na więcej niż tylko int s, wykonując następujące czynności:

/** 
* Hashes a set of objects. 
* 
* @param list to hash 
* @return hash code 
*/ 
public static int H(Object list[]) { 
    // XOR all the hashes together. 
    int hashcode = 0; 
    for (Object val : list) { 
     hashcode ^= val.hashCode(); 
    } 
    return hashcode; 
} 

Program main będzie wtedy muszą używać tablic o wartości Integer instea d prymitywu int.

Dodawanie liczb powinno być prawie tak szybkie i może dać lepszą dystrybucję w zakresie 32 bitowym. Jeśli elementy zestawu są już równomiernie rozłożone w zakresie, to xor może być lepszy.

Jednak za pomocą obu metod można łatwo tworzyć kolizje z liczbami całkowitymi. Na przykład za pomocą metody dodawania;

{1000, 1001, 1002} 
{0, 1, 3002} 

Obie macierze mają taką samą H().

Za pomocą metody XOR;

{0x1010, 0x0101} 
{0x1111, 0x0000} 

Oba mają tę samą H().

Podobnie, element 0 jest problematyczny, ponieważ listy będą miały ten sam skrót z nim lub bez niego. Można to ograniczyć, dodając stałą wartość w każdej iteracji. Na przykład:

  ... 
      hashcode += val.hashCode() + CONSTANT; 
      ... 

Albo o tym, jak wiele elementów pierwotnego kodu skrótu:

  ... 
      // XOR all the hashes together. 
      int hashcode = list.length; 
      ... 

Answer 4

wolałbym sumowanie a następnie realizacji operacji XOR, ponieważ 1) suma jest stosowany w hashcode Set „s() implementacja, 2) suma, ponieważ podejście do mieszania tablic jest zalecane w efektywnej Java 3) jest mniej podatne na kolizję.Proponuję spojrzeć na OpenJDK za AbstractSet realizacji: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/AbstractSet.java?av=f

120 public int hashCode() { 
121  int h = 0; 
122  Iterator<E> i = iterator(); 
123  while (i.hasNext()) { 
124   E obj = i.next(); 
125   if (obj != null) 
126    h += obj.hashCode(); 
127  } 
128  return h; 
129 } 

Chciałbym również polecić dokonywania h long i powrót (int) ((h & 0xffffffffL) & h >>> 32))

Answer 5

To nie oznacza programowanie trywialne, ale można czerpać inspirację z DES algorytmu S-boxy: dzięki temu możesz osiągnąć dobrą funkcję rozpraszania, która odwzorowuje podobne liczby całkowite na bardzo różne od siebie. Następnie XOR-owanie tych różnych liczb całkowitych nie powinno już stanowić zagrożenia z powodu kolizji.