Re: [Boost-users] [boost-users][multi-index] hashed identity: lookup by hash value

From: JOAQUIN M. LOPEZ MUÑOZ (joaquin_at_[hidden])
Date: 2008-07-13 14:42:26

Hi Igor,

________________________________________
De: boost-users-bounces_at_[hidden] [boost-users-bounces_at_[hidden]] En nombre de Igor R [boost.lists_at_[hidden]]
Enviado el: domingo, 13 de julio de 2008 14:12
Para: boost-users_at_[hidden]
Asunto: [Boost-users] [boost-users][multi-index] hashed identity: lookup by hash value
>
> Hello,
>
> Given a multi_index_container with 1 hashed unique identity key (kind
> of unordered set) - is there a "trivial" way to find a value by its
> hash-code?

There is a trivial method but it relies on undocumented implementation features
of hashed indices:

  std::size_t h=boost::hash<Element>()(...);
  std::size_t n=h%elementSet.bucket_count();
  // the element lies in the range [first,last). In most cases (i.e. if the hash
  // function is doing a good job), this range only contains one element.
  ElementSet::iterator first=elementSet.begin(n), last=elementSet.end(n);

As I said, this relies on the knowledge that an element with hash value h goes
to the bucket in the position h%bucket_count. So, my strong advise is *not to
use this*. The correct approach is the one you are already exploring below.

> Currently, I'm using a trick with supplying custom hashing/equality
> functors, but probably there's some more straightforward way?
[...]
> struct ElementEq
> {
>   bool operator()(size_t x, const Element &y) const
>   {
>     return x == boost::hash<Element>()(y);
>   }
> };

Strictly speaking, your ElementEq struct has to provide also the
operator()(const Element&,size_t):

  struct ElementEq
  {
    bool operator()(const Element &x, size_t y) const
    {
      return boost::hash<Element>()(x) == y;
    }
    bool operator()(size_t x, const Element &y) const
    {
      return x == boost::hash<Element>()(y);
    }
  };

(In practice it works with the second oeprator() only, but this is again
undocumented).

[...]
> int main()
> {
>   ElementSet elementSet;
>   //....
>   // I've got here a hash-value of an element, and I wish to find it in the set.
>   ElementSet::iterator pos = elementSet.find(hashValue,
> ElementHashHasher(), ElementEq());
> }

You have to take into account that there is a possibility that find() gets you
a distinct element with the same hash value, so you'd better use
equal_range() and postprocess the obtained range to find the exact element
you're after. Other than this, the technique you describe is absolutely OK and
the one I'd recommend to do what you want. Is it not working for you?
I've written a small code snippet to try it myself and everything seems to
work OK (attached).

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo