General purpose hashing function for classes and subclasses

I am writing a kind of class framework where I will need to get the hashes of objects for storing them in a hash table.

So if I have:

class A {
    int a;
};

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

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

I need to be able to run B's or C's through the hashing function to get the object's hash.

How should I go about this? I thought about simply doing sizeof(thing) and hashing the raw bytes, but is that a good way to do it? I also thought of having virtual uint_32 hash() = 0 in the base class, but that would be suboptimal to have to implement that for ev开发者_Python百科ery subclass.

Usually you need your hash function to be consistent with equality as defined on your classes. Maybe equality is defined by an overloaded operator==, but even if that's not overloaded you might think that two objects should be considered equal, and have the same hash code, if all their data members are equal.

Hashing the raw bytes doesn't work in general. There is no guarantee that two objects whose data members are all equal will have equal bytes. For example, there might be some padding in the object somewhere, for alignment reasons, and padding bytes could take any value.

Even worse, there's no guarantee that two double values that are equal have equal bytes. For example, positive/negative zero compare equal.

The case of C is particularly tricky: if two C objects point to different otherClass objects, but the two otherClass objects are equal, then should the two C objects have the same hash value? You can't define that in complete generality, it's a property of the C class.

Can something be "suboptimal" if it's also the best that's possible? ;-) The only general solution is to define a function hash, and write a version for every class. In your case you might make that a virtual function of A, but you could also look at how std::hash works in C++0x: it's actually a template functor class rather than a function, and it can be specialized for user-defined classes. That doesn't provide dynamic polymorphism, of course, but if you specialize it for A, and have the implementation call a virtual function, which you implement in each class, then your hash function will work with std::unordered_map etc.

Doing the sizeof thing can give you different hashes of identical objects, if the objects have uninitialized fields (the objects have different meaningless bits) or dynamic members (the objects have pointers that are different, even though they point to identical data). You can't do much better than writing a serializer, then running the result through your hash function.

As for the cost of implementing hash() for every base class, you have three choices.

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.

I'd recommend starting with 2, then moving to 3 piecemeal.