c++ - std::unordered_map 的哈希值

coder 2023-11-15 原文

根据标准，std::hash 中不支持容器(更不用说无序容器了)类(class)。所以我想知道如何实现它。我拥有的是:

std::unordered_map<std::wstring, std::wstring> _properties;
std::wstring _class;

我考虑过迭代条目，计算键和值的各个散列(通过 std::hash<std::wstring> )并以某种方式连接结果。

执行此操作的好方法是什么？如果未定义 map 中的顺序，这有什么关系吗？

注意:我不想使用 boost。

有人建议一个简单的异或，所以它会是这样的:

size_t MyClass::GetHashCode()
{
  std::hash<std::wstring> stringHash;
  size_t mapHash = 0;
  for (auto property : _properties)
    mapHash ^= stringHash(property.first) ^ stringHash(property.second);

    return ((_class.empty() ? 0 : stringHash(_class)) * 397) ^ mapHash;
}

我真的不确定那个简单的 XOR 是否足够。

最佳答案

响应

如果足够的话，你的意思是你的函数是否是单射的，答案是否定的。原因是你的函数可以输出的所有哈希值的集合具有基数 2^64，而你的输入空间是 < strong="">大得多。然而，这并不重要，因为考虑到输入的性质，您不能拥有单射哈希函数。一个好的哈希函数具有这些品质:

它不容易翻转。给定输出 k，在宇宙的生命周期内找到满足 h(m) = k 的 m 在计算上是不可行的。
范围均匀分布在输出空间。
很难找到满足 h(m) = h(m') 的两个输入 m 和 m'

当然，这些的范围实际上取决于您是想要加密安全的东西，还是想要获取一些任意数据 block 并只向它发送一些任意 64 位整数。如果您想要加密安全的东西，那么自己编写它并不是一个好主意。在这种情况下，您还需要保证函数对输入的微小变化敏感。 std::hash 函数对象不需要密码安全。它存在于与哈希表同构的用例中。 CPP Rerefence 说:

For two different parameters k1 and k2 that are not equal, the probability that std::hash<Key>()(k1) == std::hash<Key>()(k2) should be very small, approaching 1.0/std::numeric_limits<size_t>::max().

我将在下面说明您当前的解决方案如何不能真正保证这一点。

碰撞

我将针对您的解决方案的变体提供一些我的观察结果(我不知道您的 _class 成员是什么)。

std::size_t hash_code(const std::unordered_map<std::string, std::string>& m) {
    std::hash<std::string> h;
    std::size_t result = 0;
    for (auto&& p : m) {
        result ^= h(p.first) ^ h(p.second);
    }
    return result;
}

很容易产生碰撞。考虑以下 map :

std::unordered_map<std::string, std::string> container0;
std::unordered_map<std::string, std::string> container1;
container0["123"] = "456";
container1["456"] = "123";
std::cout << hash_code(container0) << '\n';
std::cout << hash_code(container1) << '\n';

在我的机器上，使用 g++ 4.9.1 编译，输出:

1225586629984767119
1225586629984767119

关于这是否重要的问题出现了。相关的是您将多久拥有一次键和值颠倒的映射。这些冲突将发生在键和值集相同的任何两个映射之间。

迭代顺序

具有完全相同键值对的两个 unordered_map 实例不一定具有相同的迭代顺序。 CPP Rerefence 说:

For two parameters k1 and k2 that are equal, std::hash<Key>()(k1) == std::hash<Key>()(k2).

这是哈希函数的一个微不足道的要求。您的解决方案避免了这种情况，因为迭代顺序无关紧要，因为 XOR 是可交换的。

一个可能的解决方案

如果您不需要加密安全的东西，您可以稍微修改您的解决方案以消除对称性。这种方法在实践中适用于哈希表等。这个解决方案也独立于 unordered_map 中的顺序未定义的事实。它使用与您的解决方案相同的属性(XOR 的交换性)。

std::size_t hash_code(const std::unordered_map<std::string, std::string>& m) {
    const std::size_t prime = 19937;
    std::hash<std::string> h;
    std::size_t result = 0;
    for (auto&& p : m) {
        result ^= prime*h(p.first) + h(p.second);
    }
    return result;
}

在这种情况下，您在哈希函数中所需要的只是一种将键值对映射到任意好的哈希值的方法，以及一种使用交换运算组合键值对的哈希值的方法。这样，顺序并不重要。在我写的例子hash_code中，键值对哈希值只是键的哈希和值的哈希的线性组合。您可以构建更复杂的东西，但没有必要。

关于c++ - std::unordered_map 的哈希值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31098482/

有关c++ - std::unordered_map 的哈希值的更多相关文章

ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2
我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat
ruby - 如何在 Grape 中定义哈希数组？ - 2
我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>
ruby - 在哈希的键数组中追加元素 - 2
查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？最佳答案如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用
ruby - 使用 `+=` 和 `send` 方法 - 2
如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:
ruby - 在 Ruby 中创建按公共(public)键值分组的新哈希 - 2
假设我有一个在Ruby中看起来像这样的哈希:{:ie0=>"Hi",:ex0=>"Hey",:eg0=>"Howdy",:ie1=>"Hello",:ex1=>"Greetings",:eg1=>"Goodday"}有什么好的方法可以将它变成如下内容:{"0"=>{"ie"=>"Hi","ex"=>"Hey","eg"=>"Howdy"},"1"=>{"ie"=>"Hello","ex"=>"Greetings","eg"=>"Goodday"}} 最佳答案您要求一个好的方法来做到这一点，所以答案是:一种您或同事可以在六个月后理解
ruby - 如何计算 Liquid 中的变量 +1 - 2
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。最佳答案因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我
ruby-on-rails - 使用作为方法的值在 ruby 中搜索哈希 - 2
我在搜索我的值是方法的散列时遇到问题。我只是不想运行plan_type与键匹配的方法。defmethod(plan_type,plan,user){foo:plan_is_foo(plan,user),bar:plan_is_bar(plan,user),waa:plan_is_waa(plan,user),har:plan_is_har(user)}[plan_type]end目前如果我传入“bar”作为plan_type，所有方法都会运行，我怎么能只运行plan_is_bar方法呢？最佳答案这个变体怎么样？defmethod
键删除后 ruby 哈希内存泄漏 - 2
你好，我无法成功如何在散列中删除key后释放内存。当我从哈希中删除键时，内存不会释放，也不会在手动调用GC.start后释放。当从Hash中删除键并且这些对象在某处泄漏时，这是预期的行为还是GC不释放内存？如何在Ruby中删除Hash中的键并在内存中取消分配它？例子:irb(main):001:0>`ps-orss=-p#{Process.pid}`.to_i=>4748irb(main):002:0>a={}=>{}irb(main):003:0>1000000.times{|i|a[i]="test#{i}"}=>1000000irb(main):004:0>`ps-orss=-p
Ruby 哈希直接访问与合并 - 2
有什么区别:@attr[:field]=new_value和@attr.merge(:field=>new_value) 最佳答案如果您使用的是merge!而不是merge，则没有区别。唯一的区别是您可以在合并参数中使用多个字段(意思是:另一个散列)。例子:h1={"a"=>100,"b"=>200}h2={"b"=>254,"c"=>300}h3=h1.merge(h2)putsh1#=>{"a"=>100,"b"=>200}putsh3#=>{"a"=>100,"b"=>254,"c"=>300}h1.merge!(h2)pu

c++ - std::unordered_map 的哈希值

响应

碰撞

迭代顺序

一个可能的解决方案

有关c++ - std::unordered_map 的哈希值的更多相关文章

随机推荐