问题标签 [hash]

I've found the standard hashing function on VS2005 is painfully slow when trying to achieve high performance look ups. What are some good examples of fast and efficient hashing algorithms that should void most collisions?

这个问题来自关于tuples的讨论。

我开始考虑元组应该具有的哈希码。如果我们接受 KeyValuePair 类作为元组呢？它不会覆盖 GetHashCode() 方法，所以它可能不会知道它的“孩子”的哈希码......所以，运行时将调用 Object.GetHashCode()，它不知道实物结构。

然后我们可以创建一些引用类型的两个实例，它们实际上是 Equal，因为重载了 GetHashCode() 和 Equals()。并将它们用作元组中的“孩子”来“欺骗”字典。

但它不起作用！运行时以某种方式计算出我们的元组的结构并调用我们类的重载 GetHashCode！

它是如何工作的？Object.GetHashCode() 做了什么分析？

当我们使用一些复杂的键时，它会在一些糟糕的情况下影响性能吗？（可能，不可能的情况......但仍然）

以这段代码为例：

更新我想我已经找到了对此的解释，如下所述。它的主要成果是：

• 小心你的密钥和它们的哈希码:-)
• 对于复杂的字典键，您必须正确覆盖 Equals() 和 GetHashCode()。

像你们中的许多人一样，我使用 ReSharper 来加快开发过程。当您使用它来覆盖类的相等成员时，它生成的代码生成GetHashCode()如下所示：

当然我也有一些我自己的成员，但我想知道为什么是 397？

• 编辑：所以我的问题的措辞会更好，397素数除了是素数之外还有什么“特殊”吗？

我们有一个系统，我们希望防止为两个不同的帐户注册相同的信用卡号。由于我们没有在内部存储信用卡号 - 只是最后四位数字和到期日期 - 我们不能简单地比较信用卡号和到期日期。

我们目前的想法是在信用卡注册时在我们的信用卡信息系统中存储一个哈希值（SHA-1），并比较哈希值以确定一张卡之前是否被使用过。

通常，使用盐来避免字典攻击。我假设在这种情况下我们很容易受到攻击，所以我们可能应该将盐与哈希一起存储。

大家觉得这个方法有什么缺陷吗？这是解决这个问题的标准方法吗？

首先：我正在使用一个相当晦涩的嵌入 javascript 实现作为 Adob​​e InDesign CS3 的脚本引擎。这种实现有时与“标准”javascript不同，因此是我的问题。

我正在使用John Resig 的 jsdiff 库（来源此处）来比较两个文档之间的文本选择。jsdiff 使用 vanilla 对象作为关联数组来将文本中的单词映射到另一个对象。（参见 jsdiff.js 中的“ns”和“os”变量，第 129 行左右。）

当文本中出现“反射”这个词时，我的头痛就开始了。“反射”是所有对象的默认只读属性。当 jsdiff 尝试将关联数组上的值分配给 ns['reflect'] 时，一切都会爆炸。

我的问题：有没有办法解决这个问题？有没有办法在不使用明显的香草对象的情况下在 javascript 中做一个哈希表？

基本规则：切换脚本引擎不是一种选择。:)

有没有一种简单的方法可以在 awk 中执行以下任何操作？

• 按数据对数组/哈希进行排序
• 通过它的字符串键对哈希进行排序

我有一个 Perl 脚本，我在其中使用哈希表维护一个非常简单的缓存。一旦它占用超过 n 个字节，我想清除哈希，以避免 Perl（32 位）内存不足和崩溃。

我可以检查键值对的数量：

但是是否可以检查散列占用的实际内存？

我们如何决定hashCode()集合方法的最佳实现（假设 equals 方法已被正确覆盖）？

我有很多不相关的命名事物，我想对其进行快速搜索。“土豚”总是到处都是“土豚”，因此散列字符串并重用整数可以很好地加快比较速度。整个名称集是未知的（并且随着时间的推移而变化）。什么是快速字符串散列算法，它将生成小（32 或 16）位值并具有低冲突率？

我希望看到特定于 C/C++ 的优化实现。

Python 中的基本数据结构之一是字典，它允许记录“键”以查找任何类型的“值”。这是在内部作为哈希表实现的吗？如果不是，那是什么？