Алгоритм для hash/crc неупорядоченного мультимножества

Question

Предположим, я хотел бы создать неупорядоченный набор неупорядоченных мультимножеств unsigned int. Для этого мне нужно создать хэш-функцию для вычисления хэша неупорядоченного мультимножества. Фактически, это должно быть хорошо для CRC.

Одним из очевидных решений является размещение элементов в векторе, сортировка их и возврат хеша результата. Кажется, это работает, но это дорого.

Другим подходом является xor значения, но, очевидно, если у меня есть один элемент дважды или нет, результат будет таким же - что не очень хорошо.

Любые идеи, как я могу реализовать это дешевле - у меня есть приложение, которое будет делать эту тысячу для тысяч наборов и относительно больших.

Answer 1

Реализовать внутренний мультимножитель как карту хэша value-> count.

Это позволит избежать проблемы, заключающейся в том, что четное количество элементов отменяется с помощью xor следующим образом: вместо того, чтобы каждый элемент, вы создаете новое число из числа и значения (например, умножая их), а затем вы можете построить полный хэш с помощью xor.

Answer 2

Поскольку это мультимножество, вы хотите, чтобы значение хеша было одинаковым для идентичных мультимножеств, представление которых может иметь одинаковые элементы, представленные, добавленные или удаленные в другом порядке. Тогда вам хотелось бы, чтобы значение хеша было коммутативным, легко обновлялось и изменялось для каждого изменения элементов. Вы также хотели бы, чтобы два изменения не могли легко отменить их эффект на хеш.

Одна операция, которая соответствует всем, кроме последних критериев, является дополнением. Просто суммируйте элементы. Чтобы сохранить ограниченную сумму, суммируйте сумму по размеру вашего хэш-значения. (Например, modulo 2 для 64-разрядного хэша.) Чтобы убедиться, что вставка или удаление нулевых значений изменяет хеш, сначала добавьте их к каждому значению.

Недостатком этой суммы является то, что два изменения могут быть легко отменены. Например. заменяя 1 3 на 2 2. Чтобы решить это, вы можете использовать тот же подход и суммировать полином записей, сохраняя при этом коммутативность. Например. вместо суммирования x + 1, вы можете суммировать x + x + 1. Теперь сложнее придумывать наборы изменений с одинаковой суммой.

Answer 3

Вот разумная хеш-функция для std::unordered_multiset<int>, было бы лучше, если бы вычисления были сделаны по модулю большого простого, но идея стоит.

#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 

Когда это простое число р, число столкновений пропорционально 1/р. Я не знаю, что такое анализ двух степеней. Вы можете сделать обновления хэша эффективными, добавив/вычитая BASE^x, когда вы вставляете/удаляете целое число x.