Re: [Boost-users] functional/hash: hash_value with context

From: Boris Mansencal (boris.mansencal_at_[hidden])
Date: 2006-12-04 13:16:46

Peter Dimov wrote:

>Boris Mansencal wrote:
>  
>
>>> return ((size_t)p.x()<<1)*P_width + (size_t)(p.y()<<1);
>>>      
>>>
>
>What type does p.x() have in your case, and why do you shift it left by one? 
>In principle, this discards one bit of entropy, if the bucket count is even 
>(but not when it's prime).
>
>Why do you multiply p.x() by the width? Isn't x() supposed to be within 
>0..width and y() within 0..height? It seems that you need to either multiply 
>y() by width or x() by height.
>  
>
indeed,
return (size_t)(p.x()*P_height + p.y())
seems to give slightly better results...
(but actually I still do not really grasp why...)

>  
>
>>Is there no solution to my question ?
>>    
>>
>
>You can't have a context-dependent hash_value, but you can pass a 'Hasher' 
>function object to unordered_map that stores your context.
>  
>
exactly. This is the solution I was looking for.
I can do :

class ptHasher
  : public std::unary_function<point, std::size_t>
{
public:
  ptHasher(int pHeight)
    : m_height(pHeight)
  {}
 
  inline
  std::size_t
  operator()(const point &p) const
  {
    return (size_t)(p.x()*m_height+p.y());
  }

protected:
  int m_height;
};
 
std::tr1::unordered_map<point, myType,  ptHasher> 
map_point_to_myType(10, ptHasher(height));

Is there any drawback to do things like that ?
Is there any portability issue ?
(it starts to become really off topic as I do not use boost anymore here...)

>Depending on the typical values of your width, it may also be possible to 
>just use a fixed width of, say, 65536.
>  
>
yes.

>Unfortunately, there are no "context free" rules regarding hash functions, 
>you have to find one that works best in your particular situation. Even if 
>it doesn't make much sense. :-) One problem with this approach is that it 
>can tie you to a particular unordered_map implementation. We've tried to 
>make hash_combine work adequately for as many cases as possible, but this 
>makes it a bit slower to compute. 
>  
>
thanks a lot,

Boris.