Универсальная хеш-функция для классов и подклассов

Question

Я пишу некую платформу классов, где мне нужно будет получить хеши объектов для хранения их в хеш-таблице.
Так что, если у меня есть:

class A {
    int a;
};

class B : public A {
    const char* str;
};

class C : public A {
    double d;
    otherClass* oc;
};

Мне нужновозможность запустить B или C через функцию хеширования, чтобы получить хеш объекта.

Как мне поступить?Я думал о простом выполнении sizeof(thing) и хешировании необработанных байтов, но разве это хороший способ сделать это?Я также подумал о том, чтобы иметь virtual uint_32 hash() = 0 в базовом классе, но это было бы неоптимально для реализации этого для каждого подкласса.

Answer 1

Обычно вам нужно, чтобы ваша хеш-функция соответствовала равенству, определенному в ваших классах.Возможно, равенство определяется перегруженной operator==, но даже если она не перегружена, вы можете подумать, что два объекта следует считать равными и иметь одинаковый хэш-код, если все их элементы данных равны.

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

Что еще хуже, нет гарантии, что два равных значения double имеют равные байты.Например, положительное / отрицательное нулевое сравнение равно.

Случай C особенно сложен: если два объекта C указывают на разные otherClass объекты, но два объекта otherClass равны, то если дваОбъекты C имеют одинаковое значение хеша?Вы не можете определить это в полной общности, это свойство класса C.

Может ли что-то быть "неоптимальным", если это также лучшее, что возможно?;-) Единственное общее решение - определить функцию hash и написать версию для каждого класса.В вашем случае вы могли бы сделать это виртуальной функцией A, но вы также можете посмотреть, как std::hash работает в C ++ 0x: это на самом деле класс функтора шаблонов, а не функция, и он может быть специализирован для пользовательскихклассы.Конечно, это не обеспечивает динамический полиморфизм, но если вы специализируете его для A и у вас есть вызов реализации виртуальной функции, которую вы реализуете в каждом классе, тогда ваша хеш-функция будет работать с std::unordered_map и т. Д.

Answer 2

Выполнение вещи sizeof может дать вам разные хэши идентичных объектов, если у объектов есть неинициализированные поля (объекты имеют разные бессмысленные биты) или динамические члены (объекты имеют разные указатели, даже если они указывают на идентичныеданные).Вы не можете сделать намного лучше, чем написать сериализатор, а затем запустить результат через вашу хэш-функцию.

Что касается стоимости реализации hash() для каждого базового класса, у вас есть три варианта.

1. Реализуйте 'hash () `для базового класса, но не перегружайте его во всех производных классах.Некоторые объекты производных классов будут иметь одинаковый хэш, даже если они разные.
2. Сделайте его чисто виртуальным (`virtual uint32 hash () = 0`), внедрите его во все производные классы, даже если это иногда тривиально (` hash () {return (0)} `).Та же проблема, что и у 1, но проблему легче увидеть.
3. Укуси пулю.Реализуйте это правильно для всех подклассов.

Я бы рекомендовал начать с 2, а затем перейти к 3 по частям.