arrays - 字符串数组作为哈希函数键？

Question

是否有可能在任何语言中（没关系）都有一个使用字符串数组作为键的哈希函数？

我的意思是这样的：

hash(["word1", "word2", ...]) = "element"

而不是经典的：

hash("word") = "element"

我需要这样的东西，因为我想用作键的每个单词都可以更改函数的输出元素。我有一个单词序列，我想要该序列的特定输出（顺序也可能会改变结果）。

Answer 1

当然。任何数据结构都可以被散列。您只需要提出一个严格的相等定义，然后确保 hash(A) == hash(B) if A == B。假设您的定义是 [s1, s2, ..., sm] == [t1, t2, ..., tn] 当且仅当 m == n 和 si == ti 对于 i = 1..m 和进一步的字符串 s == t 当且仅当 |s|==|t| s[i]==t[i] 表示 0<=i<|s|。您可以通过多种方式构建哈希：

• 连接列表中的所有字符串，并使用任何字符串散列函数对结果进行散列。
• 执行相同操作，添加逗号 (,) 等分隔符
• 单独散列每个字符串并对结果进行异或运算。
• 单独散列 eash 字符串，移动之前的散列值，并将新值异或到散列中。
• 无限更多的可能性...

严格的平等定义很重要。例如，如果列表中的顺序无关紧要，或者字符串比较不区分大小写，则哈希函数仍必须设计为确保 hash(A) == hash(B) 如果 A == B 。弄错这个会导致查找失败。

Java 是一种允许您为任何数据类型定义散列函数的语言。事实上，使用默认散列函数的字符串库列表可以作为键正常工作。

HashMap<ArrayList<String>, String> map = new HashMap<ArrayList<String>, String>();

ArrayList<String> key = new ArrayList<String>();
key.add("Hello");
key.add("World");

map.put(key, "It's me.");
// map now contains mapping ["Hello", "World"] -> "It's me."

Answer 2

是的，这是可能的，但在大多数情况下，您必须定义自己的哈希函数，将数组转换为哈希键。例如，在 java 中，array.hashCode() 基于 Object.hashCode() 函数，该函数基于 Reference 本身而不是 Object 的内容。

如果您对构建在数组之上的散列函数的实现感兴趣，您还可以查看java 中的 Arrays.deepHashCode() 函数。