Re: [boost] Re: [review] hash functions

From: Dave Harris (brangdon_at_[hidden])
Date: 2005-03-15 11:20:14

In-Reply-To: <d1409a$kc1$1_at_[hidden]>
daniel_at_[hidden] (Daniel James) wrote (abridged):
> Think about how such a class would be stored in the proposed unordered 
> associative containers. If you use unordered_set<base*> then the hash 
> function will be called for the pointer, not the class.

I imagine you would use a hasher which dereferenced the pointer.

    template<typename T> 
    struct hash_ptr {
        size_t operator()(const T *p) const {
            return hash_value( *p );
        }
    };

And perhaps this should be included in boost too? Eg this:

   unordered_set< shared_ptr<MyType>, hash_ptr<MyType> >

looks reasonable to me.

> If Thorsten writes ptr_unordered_set<base> then there might be a 
> problem with boost::hash<base>. Although it will equally apply to 
> std::equal_to<base>.

Absolutely. In general when writing hash_value() you need to look at the 
corresponding equality operator. For example:

    bool Derived::operator==( const Base &base ) const {
        if (Base::operator==( base ))
            if (const Derived *p = dynamic_cast( const Derived * >(&base))
                if (m_value == p->m_value)
                    return true;
        return false;
    }

Ideally we look at this and we decide there ought to be something in the 
hash_value which corresponds to the dynamic_cast. But what?

We can try using hash_value( typeid(*this) ). However, that will be 
relatively slow and may not give good results, depending on how it is 
implemented. We could use our own type IDs, but allocating them is tricky. 

So it is tempting not to bother, and instead use:

    size_t Derived::hash_value() const {
        // return combine_hash( Base::hash_value(), m_value );
        size_t hash = Base::hash_value();
        combine_hash( hash, m_value );
        return hash;
    }

which is correct, but will produce more collisions than if we'd used the 
typeid. If hash_value( m_value ) yielded different results for different 
types of value, then the number of collisions would be reduced.

The stability requirement compromises the quality of hashing.

-- Dave Harris, Nottingham, UK