Key already exists in unordered_map, but "find" returns as not found

Question

I constructed an unordered_map using key type rot3d, which is defined below:

#ifndef EPS6
#define EPS6 1.0e-6
#endif

struct rot3d
{
    double agl[3]; // alpha, beta, gamma in ascending order
    bool operator==(const rot3d &other) const
    {
        // printf("== used\n");
        return abs(agl[0]-other.agl[0]) <= EPS6 && abs(agl[1]-other.agl[1]) <= EPS6 && abs(agl[2]-other.agl[2]) <= EPS6;
    }
};

Equality of rot3d is defined by the condition that each component is within a small range of the same component from the other rot3d object.

Then I defined a value type RotMat:

struct RotMat // rotation matrix described by a pointer to matrix and trunction number
{
    cuDoubleComplex *mat = NULL;
    int p = 0;
};

In the end, I defined a hash table from rot3d to RotMat using self-defined hash function:

struct rot3dHasher
{
    std::size_t operator()(const rot3d& key) const
    {
        using std::hash;
        return (hash<double>()(key.agl[0]) ^ (hash<double>()(key.agl[1]) << 1) >> 1) ^ (hash<double>()(key.agl[2]) << 1);
    }
};

typedef std::unordered_map<rot3d,RotMat,rot3dHasher> HashRot2Mat;

The problem I met was, a key was printed to be in the hash table, but the function "find" didn't find it. For instance, I printed a key using an iterator of the hash table:

Key: (3.1415926535897931,2.8198420991931510,0.0000000000000000)

But then I also got this information indicating that the key was not found:

(3.1415926535897931,2.8198420991931505,0.0000000000000000) not found in the hash table.

Although the two keys are not 100% the same, the definition of "==" should ensure them to be equal. So why am I seeing this key in the hash table, but it was not found by "find"?

I suspect the problem may be that you aren't allowed to provide a hasher that produces different hash values for elements that compare equal. Values that are different but within `EPS6` of each other will compare equal while producing different hashes. — François Andrieux, Aug 13 '20 at 18:50
You have a tolerance defined in your equality operator. There is no such permissiveness in the hash function. Floating-point values need different data structures such as octtrees, a hashtable simply will not behave the way you hope. — Ben Voigt, Aug 13 '20 at 18:50
Your equality definition also has a root problem in that it's not transitive. With your definition it's possible that a == b and b == c but a != c. That's broken. — Michael Burr, Aug 13 '20 at 18:55

score 2 · Accepted Answer · answered Aug 13 '20 at 18:54

Hash-based equivalence comparisons are allowed to have false positives, which are resolved by calling operator==.

Hash-based equivalence comparisons are not allowed to have false negatives, but yours does. Your two "not 100% the same" keys have different hash values, so the element is not even found as a candidate for testing using operator==.

It is necessary that (a == b) implies (hash(a) == hash(b)) and your definitions break this precondition. A hashtable with a broken precondition can misbehave in many ways, including not finding the item you are looking for.

Use a different data structure that is not dependent on hashing, but nearest-neighbor matching. An octtree would be a smart choice.

I figured out the problem from the mechanism of a hash table. When a hash table searches for a key, it first uses a hash function to hash an index into buckets. If the index points to a solid bucket, then it retrieves the key from the bucket and compares it with the searched key. If the two keys are equal (this is where key comparison comes in), the key is found. The cause of my bug should be that, the key searched was in fact not the key stored, due to numerical errors, and the hash table never reached the bucket where the true key was stored, and the equality check "==" was not initiated. — Ziqi Fan, Aug 14 '20 at 10:27

score 1 · Answer 2 · answered Aug 13 '20 at 19:09

Equality of rot3d is defined by the condition that each component is within a small range of the same component from the other rot3d object.

This is not an equivalence. You must have that a==b and b==c implies a==c. Yours fails this requirement.

Using a non-equality in a std algorithm or container breaks the std preconditions, which means your program is ill-formed, no diagnostic required.

Also your hash hashes equivalent values differently. Also illegal.

One way to fix this is to build buckets. Each bucket has a size of your epsilon.

To find if a value is in your buckets, check the bucket you'd put the probe value in, plus all adjacent buckets (3^3 or 27 of them).

For each element, double check distance.

struct bucket; // array of 3 doubles, each a multiple of EPS6.  Has == and hash.  Also construct-from-rod3d that rounds.
bucket get_bucket(rot3d);

Now, odds are that you are just caching. And within EPS-ish is good enough.

template<class T, class B>
struct adapt:T{
  template<class...Args>
  auto operator()(Args&&...args)const{
    return T::operator()( static_cast<B>(std::forward<Args>(args))... );
  }
  using is_transparent=void;
};
std::unordered_map<bucket, RotMat, adapt<std::hash<rot3d>, bucket>, adapt<std::equal_to<>, bucket>> map;

here we convert rod3ds to buckets on the fly.

Key already exists in unordered_map, but "find" returns as not found

2 Answers2

Linked