Табулирование хеширования и N3980
У меня проблемы с адаптацией ожидающего предложения C ++ 1z N3980 @HowardHinnant для работы с хеширование таблиц.
Ab initio вычисления хэш табуляции работает так же, как и для алгоритма хэширования (Spooky, Murmur и т. д.), описанного в N3980. Это не так сложно: просто сериализуйте объект любого пользовательского типа с помощью hash_append () и позвольте хеш-функции обновлять указатель на таблицу случайных чисел по мере продвижения.
Проблема начинается с попытки реализовать одно из приятных свойств хэширования таблиц: очень дешевое вычисление инкрементные обновления в хеш, если объект мутирован. Для «сделанных вручную» хэшей табуляции нужно просто пересчитать хэш затронутых байтов объекта.
Мой вопрос: как сообщать инкрементные обновления uhash<MyTabulationAlgorithm> функциональный объект, сохраняя верность центральной теме N3980 (Типы не знают #)?
Чтобы проиллюстрировать трудности проектирования: скажем, у меня есть определенный пользователем тип X с N элементами данных xi различных типов Ti
struct X
{
T1 x1;
...
TN xN;
};
Теперь создайте объект и вычислите его хеш
X x { ... }; // initialize
std::size_t h = uhash<MyTabulationAlgorithm>(x);
Обновите отдельный элемент и пересчитайте хэш
x.x2 = 42;
h ^= ...; // ?? I want to avoid calling uhash<>() again
Я мог бы вычислить инкрементное обновление как что-то вроде
h ^= hash_update(x.x2, start, stop);
где [start, stop) представляет диапазон таблицы случайных чисел, которые соответствуют элементу данных x2. Однако, чтобы постепенно (т.е. дешево!) Обновить хеш для произвольных мутаций, каждый член данных должен каким-то образом знать свой собственный поддиапазон в сериализованном потоке байтов своего содержащего класса. Это не похоже на дух N3980. Например, добавление новых членов данных в содержащий класс изменило бы макет класса и, следовательно, смещения в сериализованном потоке байтов.
заявкаХэширование табуляции очень старое, и недавно было показано, что оно обладает очень хорошими математическими свойствами (см. ссылку на Википедию). Это также очень популярно в сообществе программистов настольных игр (компьютерные шахматы и пр., Например), где оно идет под названием Зобристское перемешивание. Там позиция доски играет роль X, а перемещение — роль небольшого обновления (например, переместить фигуру из источника в пункт назначения). Было бы неплохо, если бы N3980 мог не только быть адаптирован к такому хешированию таблиц, но и приспосабливаться к дешевым инкрементным обновлениям.
Решение
Кажется, что вы должны быть в состоянии сделать это, говоря MyTabulationAlgorithm игнорировать значения всех членов класса, кроме тех, которые изменились:
x.x2 = 42;
IncrementalHashAdaptor<MyTabulationAlgorithm, T2> inc{x.x2};
hash_append(inc, x);
h ^= inc;
Все, что нужно сделать IncrementalHashAdaptor, — это проверить диапазон памяти, который ему передается, чтобы увидеть, x2 в него входит:
template<class HashAlgorithm, class T>
struct IncrementalHashAdaptor
{
T& t;
HashAlgorithm h = {};
bool found = false;
void operator()(void const* key, std::size_t len) noexcept
{
if (/* t contained within [key, key + len) */) {
assert(!found);
found = true;
char const* p = addressof(t);
h.ignore(key, (p - key));
h(p, sizeof(T));
h.ignore(p + sizeof(T), len - (p - key) - sizeof(T));
}
else {
h.ignore(key, len);
}
}
operator std:size_t() const { assert(found); return h; }
};
Очевидно, это будет работать только для членов, чье местоположение объекта можно определить внешне и соответствует блоку памяти, переданному алгоритму хеширования; но это должно соответствовать подавляющему большинству случаев.
Вы, вероятно, хотели бы обернуть IncrementalHashAdaptor и следующее hash_append в uhash_incremental полезность; это оставлено в качестве упражнения для читателя.
Есть знак вопроса по поводу производительности; при условии, HashAlgorithm::ignore(...) виден компилятору и несложен, он должен хорошо оптимизироваться; если этого не произойдет, вы сможете рассчитать адрес байтового потока X::x2 при запуске программы с использованием аналогичной стратегии.
Другие решения