哈希表中可用作键的可接受类型

Question

我必须承认我对哈希表的工作原理只有基本的了解，尽管从我所知道的一点来看，它似乎相当简单。我的问题就是：传统智慧似乎是使用简单的基本值类型，如整数作为哈希表中的键。然而，字符串也经常被用作键，尽管在许多语言中它们被实现为引用类型。通常不鼓励使用复杂的引用类型；我猜这是因为这样做会需要一个较慢的哈希函数？但那么为什么字符串如此常用呢？毕竟，字符串在内部不是一个char[]数组（在大多数语言中）吗？

最终，在哈希表中，哪些值类型通常被视为“最好的”（甚至只是“可以接受的”）选择？还有没有常用的选择被认为是“不好”的（例如字符串）？

- Dan Tao

Answer 1

这与字符串与整数，或者值与引用无关，而是可变键和不可变键的区别。只要键是不可变的（因此它们的哈希值永远不会变化），它们就可以用于索引哈希表。例如，在Java中，字符串是不可变的，因此非常适合作为哈希表键。顺便说一下，如果数据类型够简单，总是通过值传递（如标量），那当然也没问题。

但现在想象一下您使用了可变类型；如果您把这些对象之一的引用作为键给我，我将计算其哈希值，然后将其放入我的哈希表桶之一。但是当您稍后修改对象时，我将无法收到通知；并且该对象现在可能位于错误的桶中（如果其哈希值不同）。希望这有所帮助。

- Gyom

---

这是一个非常有帮助的答案；但我仍然想知道是否有某些类型比其他类型更适合用作键。例如，假设我已经定义了一个实际上是不可变的类，并将在其整个存在期间保持相同的哈希码。那么将其用作键是否完全可以，还是出于性能原因最好使用像整数这样的东西？对我来说，全面的答案可能是您（键必须是不可变类型）和spa（用作键的类型应具有高效的哈希函数）的组合... - Dan Tao

@Dan：一个特定的哈希表需要存储它需要存储的内容。如果你正在维护一个Web缓存，你将存储URL的内容。关键字必须是一个URL，它不能是一个整数，因为你不会查找整数。显然速度越快越好，但“慢速实现我的想法”总比“非常快但完全无用”的情况要好 :-) - Steve Jessop

需要注意的是，如果关键字的目的是标识特定对象，则使用可变类类型作为哈希表关键字没有任何问题。例如，在.net中，System.Windows.Forms.Form非常是一种可变类型（具有随时可以更改的位置等属性），但可以使用哈希表将表单与其他内容相关联。请注意，这样的表始终将视两个对不同窗体的引用为不相等，即使它们的所有属性（除了它们的标识）恰好匹配。 - supercat

Answer 2

大多数字符串实现，尽管它们在托管环境中可能会出现为引用类型，但它们的实现通常是不可变类型。

哈希函数的作用是将大量状态映射到较小的状态。

这就是为什么字符串哈希对于测试字符串相等性很好。您可以将该值映射到数组的索引，并快速查找有关该值的一些信息。您不需要将每个字符与其他每个字符在每个其他字符串中进行比较。您可以对任何事情做出类似的说法。这都是关于以某种有用的方式减少或指纹化任意数量的字节。

这就是讨论在哈希表中使用的键类型的类型无效的地方，因为将该值映射到较小的状态空间以及如何在内部使用它使其有用。整数通常对硬件友好，但32位并不是真正的大空间，并且对于任意输入，在该空间内发生冲突的可能性很大。

最终，当您使用哈希表时，计算哈希值的成本与将每个值与每个其他值在每个其他可能的位置进行比较所需的时间相比，成本是微不足道的（假设您的哈希表包含数百项）。

- John Leidegren

---

我知道哈希函数的工作原理是将一个（可能）很大的值映射到一个较小的空间，但哈希函数的速度不也取决于其输入的大小吗？这就是我认为通常不鼓励使用大型引用类型作为键的原因。如果事实并非如此，那么我想知道为什么还要这样做（也许是因为开发人员需要实现自己的高效哈希函数？）。 - Dan Tao

正如我所说，许多托管环境将字符串实现为不可变类型。当您拥有不可变类型时，哈希码不需要每次计算，因为该值是恒定的（一旦创建）。通常，您只需要为每个唯一字符串支付生成哈希码的成本一次。例如，.NET运行时维护内部字符串池以实现此目的。但是，从未知字符串生成哈希码的成本存在，但成本与用作键的字符串长度相关，而不是集合（或哈希表）的大小。 - John Leidegren

这对我来说相当反直觉。你是在说，如果我向哈希表中添加一个项，然后稍后按键检索该项，运行时将神奇地知道该键的哈希码，而无需执行哈希函数吗？这怎么可能呢？ - Dan Tao

是的，显然不是这样，但类似于这样。这不是魔法，而是字符串在运行时处理方式的副作用。其想法是所有相同的字符串值在内存中只表示一次。运行时仍然需要维护字符串池的成本，但您永远不会支付对一个字符串进行哈希的成本超过一次。 - John Leidegren

那么你的意思是运行时在内部维护了自己的类似字符串的对象，每个对象都有一个缓存值用于其哈希码（对吗？）... 这是我仍然不理解的地方：如果我实例化一个新的字符串 - 或者更确切地说，即使运行时实际上将其视为相同的字符串，它看起来像一个新的字符串 - 运行时如何知道它已经在内存中存在，而不使用HashTable？我所知道的唯一确定是否具有缓存哈希码的方法是通过在HashTable中查找键...这需要计算哈希码...我的意思清楚吗？ - Dan Tao

Answer 3

只要提供一个合适的哈希函数，所有类型都可以作为键。毕竟哈希表只是一个线性数组。哈希函数接受某种类型的键并计算哈希表数组中的索引（称为桶），值将存储在此处（尽管存在一些冲突问题）。

因此，真正棘手的部分是找到哈希函数。当然，它应该具有某些属性，如易于计算、混沌性（几乎相同的键应映射到完全不同的哈希表桶）、确定性（相同的键意味着相同的哈希表桶）、均匀性（所有可能的键均匀地映射到桶）或满足性（使用哈希表的所有桶）。

似乎更容易为整数等简单类型定义这样的函数。

- spa

---

这确实是真的。但是这是一个定义，说明哪些键被视为相等，哪些不相等。 - spa

Answer 4

最好的哈希键是那些具有以下特点的：

1. 拥有良好（指低碰撞率）的哈希值（参见.NET中的Object.GetHashCode，Java中的Object.hashcode）。
2. 快速比较（用于处理哈希冲突）。

总的来说，我认为在大多数情况下字符串是很好的哈希键，因为有许多优秀的字符串哈希实现。

- C. Ross

Answer 5

如果您使用复杂类型作为键，则：

• 哈希表实现将很难将项目分组到桶中以进行快速检索；它如何决定如何将一系列哈希分组到一个桶中？
• 哈希表可能需要对类型有深入的了解才能选择一个桶。
• 存在对象属性更改的风险，导致项目最终进入错误的桶中。哈希必须是不可变的。

整数通常被用作键，因为它们易于分成对应于桶的范围，它们是值类型，因此是不可变的，并且它们相当容易生成。

- GraemeF