什么散列函数应该散列一个有序的数字列表？

Question

考虑一个类型，它是int键到int值的映射。这些键的排序不及地图，并且地图可以被认为是扁平列表{key1，val1，key2，val2等}

我生成这些地图的列表，并希望能够识别相同的地图在小于O（n^2）的时间内。我打算散列每个地图一次来实现这一点。

我不确定散列函数最适合这个用途。我的密钥可以是非常大的数字（但仍然是int32），值往往很小，但我认为这样的考虑是不相关的，希望有一个我可以使用的散列函数，它适用于一般数字序列。

任何想法？谢谢。

Answer 1

大多数散列函数，特别是加密散列函数，都是在二进制数据上工作，所以任何可以表示为字节序列的东西都可以被处理。你只需要决定你将使用什么编码作为你的键值。

至于散列函数，由于您的问题与安全性无关，您可以选择任何您希望的功能。加密哈希函数提供了非常好的“混合”，有些非常快（与众所周知的非加密哈希函数如CRC32相比）。例如MD4。但是很可能你的编程语言（你没有说你使用哪种语言）已经提供了一个MD5的实现，这个实现还是相当快的。