Pass a parameter to an unordered_map (or set) hash struct

Question

I have the following struct:

array<int, 2> map_size;

struct Node{
    int id;
    array<int, 2> pos;
    vector<Node*> nbs;
    bool in_open;
    bool in_closed;
};

Every Node has a position (pos) that is in range of map_size (global variable).

And I'm using the following unordered map

struct PosHash{
    public:
    size_t operator()(array<int, 2> const& pos) const{
        return pos[1] + pos[0]*map_size[1];
    }
};

struct PosCompare{
    bool operator()(const array<int, 2>& pos1, const array<int, 2>& pos2) const{
        if (pos1[0] == pos2[0] and pos1[1] == pos2[1]){
            return true;
        }
        else{
            return false;
        }
    }
};

unordered_map<array<int, 2>, Node*, PosHash, PosCompare> nodes;

map_size is a global variable used in the hash function and allows me to get a perfect hash. However, I would like to pass map_size as a parameter to PosHash and this way, avoid using global variables. How can I do this?

PD: map_size value is determined in execution time

How about having a ```map_size``` data member for ```PosHash```. Have it's constructor intialize it. Then pass this object to the constructor of the ```unordered_map``` (at appropriate position) — User 10482, Aug 24 '20 at 16:46
`pos[]` are variables inside `Node`, which in turn is the mapped value inside your `unordered_map`. The hash function `PosHash` should receive key values and yield out `Node`s, that is, `pos[]`. How come the hash function needs mapped values to yield mapped values? — Giogre, Aug 24 '20 at 17:02
@User10482 I think that's the way. But I don't know how to pass the parameter in the unordered_map line (map_size is determined in execution time) — BMarin, Aug 24 '20 at 17:09
@Lingo This is for A*. In A* I get the start and goal positions as array, not nodes. — BMarin, Aug 24 '20 at 17:13
@BMarin: Template parameters to `unordered_map` are . You are mapping an `array`, presumably the `map position`, to `Node*`, have I understood correctly? — Giogre, Aug 24 '20 at 17:18

User 10482 · Answer 1 · 2020-08-24T17:31:25.803

1

You can have map_size as a data member inside PosHash struct.

struct PosHash{
    public:
    size_t operator()(array<int, 2> const& pos) const{
        return pos[1] + pos[0]*map_size[1];
    }

    // Contructor that initializes the data member
    PosHash(std::intializer_list<int> map_dim) : map_size(map_dim) {
      // Other stuff
    };
    
    std::array<int, 2> map_size; // data member of the struct
};

Then you can construct a PosHash object with required map_size array. Pass this object to your unordered_map

PosHash myPosHash({1, 2});

std::unordered_map<array<int, 2>, Node*, PosHash, PosCompare> nodes(\\intial args\\, myPosHash);

Check out the different available constructors for std::unordered_map here. You need to explicitly specify all the arguments before the hasher argument. Those would depend on your needs. The simplest I can think of is

nodes(0, myPosHash);  //initial #buckets, hasher object

edited Aug 24 '20 at 17:31

answered Aug 24 '20 at 17:23

User 10482

855
1
9
22

And how do I initialize the unordered_map? – BMarin Aug 24 '20 at 17:24
@BMarin Added. You can have the constructor for ```PosHash``` and other details your way. Hope this helps. – User 10482 Aug 24 '20 at 17:33
Tony Delroy's answer has the correct way to initialize the map, which differs slightly, thanks anyway! – BMarin Aug 24 '20 at 18:17

Tony Delroy · Accepted Answer · 2020-08-24T17:36:54.230

1

Here's a complete program showing how to construct a PosHash object storing a specific value. Note that you don't need a custom comparison - std::arrays are compared the same way anyway.

#include <iostream>
#include <array>
#include <unordered_map>

using Pos = std::array<int, 2>;

struct PosHash {
    PosHash(int m) : m_{m} { }
    size_t operator()(const Pos& pos) const {
        return pos[1] + pos[0] * m_;
    }
    int m_;
};

int main()
{
    static constexpr size_t initial_bucket_count = 5;
    // for illustrative purposes, will just map to ints
    std::unordered_map<Pos, int, PosHash> m{initial_bucket_count, PosHash{4}};
    m[Pos{2, 3}] = 23;
    m[Pos{1, 1}] = 11;
    m[Pos{3, 1}] = 11;
    m[Pos{3, 2}] = 32;
    for (const auto& x : m)
        std::cout << x.first[0] << ',' << x.first[1] << '=' << x.second << '\n';
}

More generally, this is a "weak" hash function. It may be "perfect" in producing hash values spread out enough to avoid collisions in the hash value space, but that doesn't mean you won't get collisions if you're folding that space into a lesser number of buckets.

edited Aug 24 '20 at 17:36

answered Aug 24 '20 at 17:30

Tony Delroy

102,968
15
177
252

Thanks! This is exactly what i needed. I didn't know how to pass the map size to the unordered_map. Anyways, I know this hash function is perfect as nodes with same positions are always the same node. This Hash function returns the position in the 1-dim array of the map. – BMarin Aug 24 '20 at 17:53
Now I'm aware that the problem is the amount of buckets, and with limited buckets it would be better to use a standard string hash function like djb2 – BMarin Aug 24 '20 at 19:25
1

@BMarin: oh good - I was wondering if I should try to explain further or not. A reasonable general-purpose way to combine hashes for multi-part keys is [`hash_combine`](https://stackoverflow.com/q/35985960/410767) - you'd basically say `size_t seed = 0; hash_combine(seed, pos[0]); hash_combine(seed, pos[1]);` then use `seed` as your hash value. – Tony Delroy Aug 24 '20 at 19:31

Pass a parameter to an unordered_map (or set) hash struct

2 Answers2