散列函数

类别：容器、函数对象	组件类型：概念

描述

散列关联容器 的性能至关重要的取决于其散列函数。对于散列函数来说，最小化冲突很重要，其中冲突被定义为散列到相同值的两个不同的自变量。散列值的分布均匀也很重要；也就是说，散列函数返回类型为size_t的任何特定值的概率

应该与它返回任何其他值的概率大致相同。 [1]

一元函数

在调用散列函数时返回的类型。结果类型必须为

表示法

定义

除了 一元函数 需求中描述的那些表达式之外，没有其他人。

表达式语义

复杂度保证

返回值仅取决于自变量，而不取决于散列函数对象的历史记录。只要自变量相同，返回值始终相同。

• 模型

哈希

[1] 请注意，这两个要求仅在某些特定输入值的分布环境中才有意义。举一个简单的例子，假设要散列的值是六个字符串“aardvark”、“trombone”、“history”、“diamond”、“forthright”和“solitude”。在这种情况下，一个合理的（且高效）的散列函数将只是每个字符串的第一个字符。另一方面，假设要散列的值是“aaa0001”、“aaa0010”、“aaa0011”、“aaa0100”、“aaa0101”和“aaa0110”。在这种情况下，不同的散列函数将更合适。这就是 散列关联容器 由散列函数参数化的原因：对于所有应用程序，没有一个散列函数是最好的。

请参见