hash_set: how to handle collisions?

M

Markus Dehmann

Do I have to handle hash collisions in a hash_set myself?

I did a test in which I use find() to look for objects in a hash_set.
These objects are definitely not contained, but find() sometimes finds
them anyway. See this code:

<code>
#include <iostream>
#include <stdexcept>
#include <ctime>
#include <set>
// also include header that defines gnu_namespace and includes
hash_set

class MyContainer {
std::vector<int> v;
public:
MyContainer(){}
std::size_t hashcode() const {
std::size_t hash = 0;
for(unsigned i=0; i<v.size(); ++i){ // sdbm function gives
collisions sometimes
hash = v + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
void add(int i){v.push_back(i);}
};

struct eqPtrs {
bool operator()(const MyContainer* h1, const MyContainer* h2) const
{
return h1->hashcode() == h2->hashcode(); // problematic b/c of
collisions?
}
};

namespace gnu_namespace {
template<> struct hash<const MyContainer*> {
inline size_t operator()(const MyContainer* d) const {
return d->hashcode();
}
};
}

int getRand(int min, int max){
return ((rand() % (max-min+1)) + min);
}

int main(int argc, char** argv){
srand(time(0));
typedef hash_set<const MyContainer*, hash<const MyContainer*>,
eqPtrs> MyMap;
MyMap myMap;
int repeat = 100000;
int size = 10;
for(int i=0; i<repeat; ++i){
MyContainer* h = new MyContainer();
for(int j=0; j<size; ++j){
h->add(getRand(0, 1000));
}
myMap.insert(h);
}
for(int i=0; i<repeat; ++i){
MyContainer* h = new MyContainer();
for(int j=0; j<size; ++j){
h->add(getRand(2000, 3000));
}
MyMap::const_iterator found = myMap.find(h);
assert(found == myMap.end()); // aborts!
}
// TODO: finally delete elements in myMap
return EXIT_SUCCESS;
}
</code>

The solution seems to be to adapt the equality condition in eqPtrs to
also test for actual equality of the members, not just equality of the
hash codes:

struct eqPtrs {
bool operator()(const MyContainer* h1, const MyContainer* h2) const
{
return h1->hashcode() == h2->hashcode() && haveSameElements(*h1,
*h2); // added condition
}
};

Is that the solution, or am I doing something wrong in general?
General comments on my code are welcome!

Markus
 
H

huili80

Do I have to handle hash collisions in a hash_set myself?

I did a test in which I use find() to look for objects in a hash_set.
These objects are definitely not contained, but find() sometimes finds
them anyway. See this code:

<code>
#include <iostream>
#include <stdexcept>
#include <ctime>
#include <set>
// also include header that defines gnu_namespace and includes
hash_set

class MyContainer {
  std::vector<int> v;
public:
  MyContainer(){}
  std::size_t hashcode() const {
    std::size_t hash = 0;
    for(unsigned i=0; i<v.size(); ++i){ // sdbm function gives
collisions sometimes
      hash = v + (hash << 6) + (hash << 16) - hash;
    }
    return hash;
  }
  void add(int i){v.push_back(i);}

};

struct eqPtrs {
  bool operator()(const MyContainer* h1, const MyContainer* h2) const
{
    return h1->hashcode() == h2->hashcode(); // problematic b/c of
collisions?
  }

};

namespace gnu_namespace {
  template<> struct hash<const MyContainer*> {
    inline size_t operator()(const MyContainer* d) const {
      return d->hashcode();
    }
  };

}

int getRand(int min, int max){
  return ((rand() % (max-min+1)) + min);

}

int main(int argc, char** argv){
  srand(time(0));
  typedef hash_set<const MyContainer*, hash<const MyContainer*>,
eqPtrs> MyMap;
  MyMap myMap;
  int repeat = 100000;
  int size = 10;
  for(int i=0; i<repeat; ++i){
    MyContainer* h = new MyContainer();
    for(int j=0; j<size; ++j){
      h->add(getRand(0, 1000));
    }
    myMap.insert(h);
  }
  for(int i=0; i<repeat; ++i){
    MyContainer* h = new MyContainer();
    for(int j=0; j<size; ++j){
      h->add(getRand(2000, 3000));
    }
    MyMap::const_iterator found = myMap.find(h);
    assert(found == myMap.end()); // aborts!
  }
  // TODO: finally delete elements in myMap
  return EXIT_SUCCESS;}

</code>

The solution seems to be to adapt the equality condition in eqPtrs to
also test for actual equality of the members, not just equality of the
hash codes:

struct eqPtrs {
  bool operator()(const MyContainer* h1, const MyContainer* h2) const
{
    return h1->hashcode() == h2->hashcode() && haveSameElements(*h1,
*h2); // added condition
  }

};

Is that the solution, or am I doing something wrong in general?
General comments on my code are welcome!

Markus
Click to expand...


You actually have already figured out. eqPrts should return true only
when the two myContainer's have the same elements.
Buy the way, doesn't having the same elements imply having the same
hashcode? Comparing hashcode in eqPrts is redundant.
On a different note, try use Boost.Pointer_container library, it's a
lot safer that what you have posted.
 
H

huili80

Do I have to handle hash collisions in a hash_set myself?
Click to expand...
I did a test in which I use find() to look for objects in a hash_set.
These objects are definitely not contained, but find() sometimes finds
them anyway. See this code:
Click to expand...
<code>
#include <iostream>
#include <stdexcept>
#include <ctime>
#include <set>
// also include header that defines gnu_namespace and includes
hash_set
Click to expand...
class MyContainer {
  std::vector<int> v;
public:
  MyContainer(){}
  std::size_t hashcode() const {
    std::size_t hash = 0;
    for(unsigned i=0; i<v.size(); ++i){ // sdbm function gives
collisions sometimes
      hash = v + (hash << 6) + (hash << 16) - hash;
    }
    return hash;
  }
  void add(int i){v.push_back(i);}
};
Click to expand...

struct eqPtrs {
  bool operator()(const MyContainer* h1, const MyContainer* h2) const
{
    return h1->hashcode() == h2->hashcode(); // problematic b/c of
collisions?
  }
};
Click to expand...

namespace gnu_namespace {
  template<> struct hash<const MyContainer*> {
    inline size_t operator()(const MyContainer* d) const {
      return d->hashcode();
    }
  };
}
Click to expand...

int getRand(int min, int max){
  return ((rand() % (max-min+1)) + min);
}
Click to expand...

int main(int argc, char** argv){
  srand(time(0));
  typedef hash_set<const MyContainer*, hash<const MyContainer*>,
eqPtrs> MyMap;
  MyMap myMap;
  int repeat = 100000;
  int size = 10;
  for(int i=0; i<repeat; ++i){
    MyContainer* h = new MyContainer();
    for(int j=0; j<size; ++j){
      h->add(getRand(0, 1000));
    }
    myMap.insert(h);
  }
  for(int i=0; i<repeat; ++i){
    MyContainer* h = new MyContainer();
    for(int j=0; j<size; ++j){
      h->add(getRand(2000, 3000));
    }
    MyMap::const_iterator found = myMap.find(h);
    assert(found == myMap.end()); // aborts!
  }
  // TODO: finally delete elements in myMap
  return EXIT_SUCCESS;}
</code>
Click to expand...

The solution seems to be to adapt the equality condition in eqPtrs to
also test for actual equality of the members, not just equality of the
hash codes:
Click to expand...

struct eqPtrs {
  bool operator()(const MyContainer* h1, const MyContainer* h2) const
{
    return h1->hashcode() == h2->hashcode() && haveSameElements(*h1,
*h2); // added condition
  }

Is that the solution, or am I doing something wrong in general?
General comments on my code are welcome!
Click to expand...
Markus
Click to expand...

You actually have already figured out. eqPrts should return true only
when the two myContainer's have the same elements.
Buy the way, doesn't having the same elements imply having the same
hashcode? Comparing hashcode in eqPrts is redundant.
On a different note, try use Boost.Pointer_container library, it's a
lot safer that what you have posted.
Click to expand...


Oops... Boost.Pointer_container doesn't seem to have hash_set or
hash_map ...
 
J

James Kanze

Do I have to handle hash collisions in a hash_set myself?
Click to expand...

Which hash_set? There is not, and almost certainly never will
be, a hash_set in C++.

Which is, of course, a technicality. There will be an
unordered_set, and most existing hash_set are only slightly
different (but in different and incompatible ways).
I did a test in which I use find() to look for objects in a
hash_set. These objects are definitely not contained, but
find() sometimes finds them anyway. See this code:
Click to expand...
<code>
#include <iostream>
#include <stdexcept>
#include <ctime>
#include <set>
// also include header that defines gnu_namespace and includes
// hash_set
Click to expand...

If you're asking specifics about the GNU implementation, you
should probably ask an implementation specific group. But
supposing that the issue is more general, and concerns what
unordered_set will guarantee in the end.
class MyContainer {
std::vector<int> v;
public:
MyContainer(){}
std::size_t hashcode() const {
std::size_t hash = 0;
for(unsigned i=0; i<v.size(); ++i){ // sdbm function gives
collisions sometimes
hash = v + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
void add(int i){v.push_back(i);}
};
Click to expand...

struct eqPtrs {
bool operator()(const MyContainer* h1, const MyContainer* h2) const
{
return h1->hashcode() == h2->hashcode(); // problematic b/c of
collisions?
}
};
Click to expand...

You've defined two objects to be equal if their hash codes are
equal. Is that really what you want?
namespace gnu_namespace {
template<> struct hash<const MyContainer*> {
inline size_t operator()(const MyContainer* d) const {
return d->hashcode();
}
};
}
Click to expand...
int getRand(int min, int max){
return ((rand() % (max-min+1)) + min);
}
Click to expand...
int main(int argc, char** argv){
srand(time(0));
typedef hash_set<const MyContainer*, hash<const MyContainer*>,
eqPtrs> MyMap;
MyMap myMap;
int repeat = 100000;
int size = 10;
for(int i=0; i<repeat; ++i){
MyContainer* h = new MyContainer();
for(int j=0; j<size; ++j){
h->add(getRand(0, 1000));
}
myMap.insert(h);
}
for(int i=0; i<repeat; ++i){
MyContainer* h = new MyContainer();
for(int j=0; j<size; ++j){
h->add(getRand(2000, 3000));
}
MyMap::const_iterator found = myMap.find(h);
assert(found == myMap.end()); // aborts!
Click to expand...

I'm not sure I understand. You create a random object, and
assert that it is in the container. Why should you expect it to
be in the container?
}
// TODO: finally delete elements in myMap
return EXIT_SUCCESS;}

The solution seems to be to adapt the equality condition in
eqPtrs to also test for actual equality of the members, not
just equality of the hash codes:
Click to expand...
struct eqPtrs {
bool operator()(const MyContainer* h1, const MyContainer* h2) const
{
return h1->hashcode() == h2->hashcode() && haveSameElements(*h1,
*h2); // added condition
}
};
Click to expand...
Is that the solution, or am I doing something wrong in general?
Click to expand...

I don't know. It's up to you to define what equality should
mean. The only requirement is that if two elements are equal,
they have the same hash code.
 
M

Markus Dehmann

I'm not sure I understand.  You create a random object, and
assert that it is in the container.  Why should you expect it to
be in the container?
Click to expand...

No, I define an object that is guaranteed *not* to be in the container
and ask the container to find it. The assertion says that the object
should not be found.

Markus
 
J

James Kanze

No, I define an object that is guaranteed *not* to be in the
container and ask the container to find it. The assertion says
that the object should not be found.
Click to expand...

Yes, I misread this part. Except that given the way you defined
equality, you didn't guarantee that an equal object wouldn't be
in the container.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

hash_set: problem with hash function? 3
STL hash_set problem, SGI impl 1
How to multiply two matrices of size in using inline assembly in C++ 3
Could you fix my code please? (i get no output after inputing the number) 1
newbie Q: how to use stl hash_set in gcc3.4.4 2
hash_set core dump on memory free 8
Chatbot 0
Custom matrix multiplication produces different results to glm 0

Members online

Total: 85 (members: 2, guests: 83)
Robots: 261

Forum statistics

Threads
473,968
Messages
2,570,153
Members
46,699
Latest member
AnneRosen

Latest Threads

Top