Algoritmo per hash/crc del multiset non ordinato

Question

Diciamo che mi piacerebbe creare un insieme non ordinato di multiset non ordinati di int unsigned. Per questo, ho bisogno di creare una funzione di hash per calcolare un hash del multiset non ordinato. In effetti, deve essere buono anche per CRC.

Una soluzione ovvia è mettere gli elementi in vettoriale, ordinarli e restituire un hash del risultato. Questo sembra funzionare, ma è costoso.

Un altro approccio è quello di xor i valori, ma ovviamente se ho un elemento due volte o nessuno il risultato sarà lo stesso - che non è buono.

Qualche idea su come posso implementare questo più economico - Ho un'applicazione che lo farà migliaia per migliaia di serie e relativamente grandi.

Answer 1

Implementare il multiset interno come valore-> contare hash map.

Ciò consentirà di evitare il problema che un numero pari di elementi si annulla tramite xor nel modo seguente: Invece di xorare ogni elemento, si costruisce un nuovo numero dal conteggio e dal valore (ad es. Moltiplicandoli), e quindi puoi costruire l'hash completo usando xor.

Answer 2

Poiché è un multiset, si desidera che il valore di hash sia lo stesso per multiset identici, la cui rappresentazione potrebbe presentare gli stessi elementi, aggiunti o eliminati in un ordine diverso. Ti piacerebbe quindi che il valore hash fosse commutativo, facile da aggiornare e modificare per ogni cambio di elementi. Ti piacerebbe anche che due modifiche non annullino facilmente il loro effetto sull'hash.

Un'operazione che soddisfa tutti tranne l'ultimo criterio è l'aggiunta. Basta sommare gli elementi. Per mantenere la somma limitata, fai la somma modulo la dimensione del tuo valore hash. (Ad esempio modulo 2 per un hash a 64 bit.) Per assicurarsi che l'inserimento o l'eliminazione di valori zero modifichi l'hash, aggiungere prima uno a ciascun valore.

Uno svantaggio della somma è che due modifiche possono facilmente annullare. Per esempio. sostituendo 1 3 con 2 2. Per risolvere questo problema, è possibile utilizzare lo stesso approccio e sommare un polinomio delle voci, mantenendo comunque la commutatività. Per esempio. invece di sommare x + 1, è possibile sommare x + x + 1. Ora è più difficile escogitare serie di modifiche con la stessa somma.

Answer 3

Ecco una funzione di hash ragionevole per std::unordered_multiset<int> sarebbe meglio se i calcoli sono stati presi mod un grande primo ma l'idea è valida.

#include <iostream> 
#include <unordered_set> 

namespace std { 
    template<> 
    struct hash<unordered_multiset<int>> { 
     typedef unordered_multiset<int> argument_type; 
     typedef std::size_t result_type; 

     const result_type BASE = static_cast<result_type>(0xA67); 

     result_type log_pow(result_type ex) const { 
      result_type res = 1; 
      result_type base = BASE; 
      while (ex > 0) { 
       if (ex % 2) { 
        res = res * base; 
       } 
       base *= base; 
       ex /= 2; 
      } 
      return res; 
     } 

     result_type operator()(argument_type const & val) const { 
      result_type h = 0; 
      for (const int& el : val) { 
       h += log_pow(el); 
      } 
      return h; 
     } 
    }; 
}; 

int main() { 
    std::unordered_set<std::unordered_multiset<int>> mySet; 
    std::unordered_multiset<int> set1{1,2,3,4}; 
    std::unordered_multiset<int> set2{1,1,2,2,3,3,4,4}; 
    std::cout << "Hash 1: " << std::hash<std::unordered_multiset<int>>()(set1) 
       << std::endl; 
    std::cout << "Hash 2: " << std::hash<std::unordered_multiset<int>>()(set2) 
       << std::endl; 
    return 0; 
} 

Output:

Hash 1: 2290886192 
Hash 2: 286805088 

Quando è un numero primo p, il numero di collisioni è proporzionale a 1/p. Non sono sicuro di quale sia l'analisi per le potenze di due. È possibile rendere efficienti gli hash aggiungendo/sottraendo BASE^x quando si inserisce/rimuove il numero intero x.