unordered_map - 哈希函数无效

Question

为什么在下面的哈希函数(返回常量0)似乎没有产生任何影响？

由于散列函数返回常量,我期望输出所有值为3.但是std::vector,无论我的散列函数是否为常量,它似乎都将值唯一映射到唯一值.

#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>


// Hash returning always zero.
class TVectorHash {
public:
    std::size_t operator()(const std::vector<int> &p) const {
    return 0;
    }
};

int main ()
{
    std::unordered_map<std::vector<int> ,int, TVectorHash> table;

    std::vector<int> value1({0,1});
    std::vector<int> value2({1,0});
    std::vector<int> value3({1,1});

    table[value1]=1;
    table[value2]=2;
    table[value3]=3;

    std::cout << "\n1=" << table[value1];
    std::cout << "\n2=" << table[value2];
    std::cout << "\n3=" << table[value3];

    return 0;
}

获得的输出:

1=1
2=2
3=3

预期产量:

1=3
2=3
3=3

我对哈希有什么看法？

Answer 1

您误解了哈希函数的使用:它不用于比较元素.在内部,映射将元素组织到存储桶中,并且散列函数用于确定元素所在的存储桶.使用另一个模板参数执行元素的比较,查看模板的完整声明unordered_map:

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

哈希之后的下一个模板参数是关键比较器.要获得您期望的行为,您必须执行以下操作:

class TVectorEquals {
public:
    bool operator()(const std::vector<int>& lhs, const std::vector<int>& rhs) const {
        return true;
    }
};

std::unordered_map<std::vector<int> ,int, TVectorHash, TVectorEquals> table;

现在你的地图将有一个元素,你的所有结果都将是3.

Answer 2

即使在存在哈希冲突的情况下,理智的哈希表实现也不应丢失信息.有几种技术可以解决冲突(通常将运行时性能与数据完整性进行权衡).显然,std::unordered_map实现它.

请参阅:哈希碰撞解决方案