散列函数（通用理论）

Question

我一直在寻找一个答案一段时间，我想知道如果有人知道如何显式定义（从头开始）在C＃中的散列函数。我明白，有预定义的数据结构具有List能力，但我试图理解这些对象的基础结构。

任何人都可以帮忙吗？例如，如果你有两个数组，你将如何从这个数据库创建一个哈希表？

Answer 1

关于hash tables和hash functions的维基百科文章是可笑的好。您还可以查看Volume 3 of TAOCP。最后，Reflector在System.Collections.Hashtable偷看可能是一个启发性的经验。

如果您有更具体的问题，我们可以提供更详细的见解。

Answer 2

为了能够散列两个数组，它的种类取决于数组所持有的数据类型。例如，如果你的意思是散列字符串数组，你需要一个额外的步骤来编码字符串和整数，然后再对它们进行散列，因为你实际需要的是将你的输入转换成散列表的索引，给定散列函数。当然，当你“转换你的输入”时，你必须解决你的密钥之间的冲突问题。换句话说，你必须尽量减少哈希到相同值的键的数量，这就是为什么数论（特别是使用素数）变得特别有用的原因。

我假设当你问了解如何从两个数组'创建一个哈希表'时，你的意思是这两个数组中的数据是表的关键字。在这种情况下，我看不出为什么你需要引用两个数组而不是一个包含两个数组的元素的较大数组，除非你正在处理一种静态类型的编程语言，并且这两个数组可以有不同的类型。在这种情况下，你需要想出一个方案将元素转换为整数。例如，如果要将字符串s的长度为n的字符串（其中s [i]是字符串中的第i个字符（指其ASCII值）转换为整数），则可以看一下如何用一个多项式以避免将不同的字符串散列到相同的整数。而基数为31的原因除了它是素数的事实之外，是因为乘以31接近2的幂，所以主要通过比特移位可以高效地完成31。

一旦你将所有的元素都以整数的形式表达出来，你就会得到真正的问题。有一些基本的技巧，我们可以从中进行精细的组合，只要组合的组成部分彼此相对主要，以便我们可以扩展到整个哈希表。两种基本方法是除法和的乘法法。这些方法本身，特别是分割方法是不够的，因为有人可能最终确定散列键的函数。我会试着解释构建哈希函数的常用方法，但我可能不会像解释它们那么好，而是可以用CLRS。在另一方面，我可以给你属性的列表，以满足：

• 你应该尽量减少冲突
• 你的功能应该能够哈希键给任何插槽
（以不违反 简单均匀散列）
• 你的功能应该是难以逆转工程师

记住，为了满足这最后一个属性通常散列函数的一些成分（S）至少应该引起他们的映射插槽到a的钥匙ppear随机。由于这个约束，我们仍然有一个非零概率的碰撞，所以你下一个要解决的问题是冲突解决。