language-agnostic - 可接受的类型用作HashTable中的键

Question

我必须承认对HashTables的工作原理只有基本的了解，尽管从我的一点了解来看，这似乎很简单。我的问题是这样的:似乎传统的智慧是对HashTable中的键使用简单的基本值类型，例如整数。但是，即使许多语言将字符串实现为引用类型，也经常使用字符串。我通常不鼓励使用复杂的引用类型。我猜这是因为这样做将需要较慢的哈希函数？但是，为什么这么普遍使用字符串呢？毕竟，字符串不是内部的char []数组吗(同样，在大多数语言中)？

最后，通常将哪些值类型视为在HashTable中用作键的“最佳”(甚至干脆是“可接受”)选择？并且是否有任何通常被认为是“不好的”选择(例如可能是字符串)？

Answer 1

这不是字符串与整数，值与引用的关系，而是可变键与不可变键的问题。 ，只要键是不可变的(因此它们的哈希值永远不变)，就可以为哈希表建立索引。例如，Java中的字符串是不可变的，因此非常适合作为哈希表键。

顺便说一句，如果一个数据类型足够简单，总是可以按值传递(例如标量)，那么它当然可以。

但是现在想象你使用了可变类型;如果您给我对这些对象之一的引用作为键，我将计算其哈希值，然后将其放入我的哈希表存储桶之一。但是，当您以后修改对象时，将无法通知我；并且该对象现在可能驻留在错误的存储桶中(如果其哈希值不同)。

希望这可以帮助。