Хеш-функция общего назначения для классов и подклассов

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

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 в базовом классе, но было бы неоптимально реализовывать это для каждого подкласса.


c++ class hierarchy hash hashtable
person James Feder    schedule 20.11.2010    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

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

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

person Steve Jessop    schedule 20.11.2010

arrow_upward
1
arrow_downward

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

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

  1. Implement 'hash()` for the base class, but don't overload it in all derived classes. Some objects of derived classes will have the same hash, even though they're different.
  2. Make it a pure virtual(`virtual uint32 hash()=0`), implement it in all derived classes, even if it's sometimes trivial (`hash() {return(0)}`). Same problem as 1, but the problem is easier to see.
  3. Bite the bullet. Implement it correctly for all subclasses.

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

person Beta    schedule 20.11.2010