底层哈希算法对密钥的每个字符进行哈希处理,我理解这是 O(n),其中 n 是密钥的长度。
当哈希表的底层方法之一的复杂度为 O(n) 时,如何将其视为 O(1)?我认为最坏情况的复杂性优先。
这完全取决于您的假设,以及您在分析中将什么视为可变参数。
通常,当您谈论哈希表操作的复杂性时,您会忽略哈希函数的细节,并且(可能不切实际)假设它是 O(1),即与密钥长度无关,或者您隐含地假设密钥长度受常数限制。这意味着唯一感兴趣的参数通常是哈希表中的元素数量。
但是如果你想更深入地研究,你实际上是对的,人们也可以将密钥的长度视为复杂性分析的一个可测量参数。但这实际上取决于密钥的类型和哈希函数的细节。正如您所说,哈希函数本身的复杂性很可能与密钥的长度成线性关系(但不一定)。然后,您可以将复杂性指定为两个变量而不是一个变量的函数。
以 Mo B. 的有用答案为基础……
正如其他人所说,为了方便起见,我们通常将哈希函数视为 O(1)。但这与大 O 表示法的精神相反,大 O 表示法被定义为随着 n
变得
真正大,时间(或空间)需求将如何增长的上限,无论
n
可能指的是什么。因此,正如您所说,O(n) 应该反映“最坏情况”。通常人们在这种情况下使用 n
来指代输入元素的数量,所以我会这样做,并使用 k
作为哈希键的长度。
此外,当我们深入细节时,我们必须考虑哪些操作我们要求的时间复杂度。哈希表上最常见的操作是插入和查找,其中查找通常被认为是最重要的。正如您所暗示的,这两个操作都需要对密钥进行哈希处理等。对密钥进行哈希处理通常是 O(k)。
哈希表当然可以使用恒定大小的键来实现。如果您的密钥大小
n
不是基于 k
,这使得哈希计算相对于散列元素 n
的数量为 O(1)。但这并不能使查找时间复杂度为 O(1)。当哈希表中的元素数量超出可能的哈希值数量时,冲突就会增加,并且查找会变得更慢。例如,如果您的哈希桶是链表,则查找可能会变成 O(n)。
为了减少冲突,您必须增加哈希函数的输出范围,这最终(同样,随着元素数量变得非常大)意味着增加键的大小。 (固定大小的密钥具有固定的最大可能哈希数:例如,无论您的哈希函数有多好,32 位密钥都不能具有超过 2^32 个不同的哈希值。)
合理的策略是使密钥大小
k
大致与log(n)
成比例,其中n
是预期输入元素的数量;有了一个好的哈希函数,这应该会给你一些与 n
成比例的哈希值。这意味着哈希计算(即 O(k))将变为 O(log n),超过您在问题中所说的 O(1)。
因此,实际上,无论您是否使用固定大小的键,增加元素数量最终都会导致您的哈希操作相对于哈希元素数量超过 O(1) 时间复杂度。
有一些复杂而精细的哈希表算法可以在某些条件下保证 O(1) 时间复杂度,即使它们不能保证 O(1),它们在大多数情况下都可以很好地进行优化,即使在面对敌意的输入。是否值得实现(或使用此类算法的实现)取决于您的应用程序。
标准库通常不会在其哈希表实现中达到如此长度。所以关于时间复杂度的答案取决于实现。
但是你是对的,根据大 O 表示法的理论定义,哈希表的使用至少是 O(k),其中 k 是键大小,并且相对于哈希元素的数量超过 O(1)。