c# – 列表中的哈希函数独立于其中的项目顺序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了c# – 列表中的哈希函数独立于其中的项目顺序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1411字，纯文字阅读大概需要3分钟。

内容图文

我想要一个字典,为一组整数赋值.

例如,键是[1 2 3],值将具有特定值.

问题是[3 2 1]需要在我的情况下处理相同所以哈希需要相等,如果我采用哈希方法.

该套装将有2到10件物品.

项目总和通常是固定的,因此我们不能根据总和制作哈希码,这是第一个自然的想法.

不是作业任务,实际上在我的代码中遇到了这个问题.

这个集合基本上是IEnumerable< int>在C#中,所以任何数据结构都可以存储它们.

任何帮助赞赏.性能在这里也非常重要.

一个直接的想法：我们可以总结项目^ 2并且已经获得某种更好的哈希,但我仍然想听到一些想法.

编辑：嗯真的很抱歉伙计们,每个人都建议订购,我没想到我需要说实际订购和散列是我使用的当前解决方案,我正在考虑更快的替代方案.

解决方法:

基本上,这里的所有方法都是同一模板的实例化.将x1,…,xn映射到f(x1)op … op f(xn),其中op是某些集合X上的可交换关联操作,f是从项目到X的映射.此模板已使用了几次以可证明是好的方式.

>在[1,p – 1]中选择随机大素数p和随机残基b.设f(x)= bx mod p,并将op加法.我们基本上将一个集合解释为多项式,并使用Schwartz–Zippel lemma来约束碰撞的概率(=非零多项式将b作为根mod p的概率).
>让op为XOR,让f为随机选择的表.这是Zobrist hashing并且通过简单的线性代数参数最小化了期望碰撞的数量.

模幂运算很慢,所以不要使用它.对于具有300万个项目的Zobrist散列,表f可能不适合L2,尽管它确实设置了一个主存储器访问的上限.

我宁愿把Zobrist哈希作为一个出发点,寻找一个像随机函数一样的廉价函数f.这基本上是非加密伪随机生成器的工作描述 – 我会尝试通过用x播种快速PRG并生成一个值来计算f.

编辑：假设集合都具有相同的和,不要选择f为1次多项式(例如,线性同余生成器的阶梯函数).

内容总结

以上是互联网集市为您收集整理的c# – 列表中的哈希函数独立于其中的项目顺序全部内容，希望文章能够帮你解决c# – 列表中的哈希函数独立于其中的项目顺序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端