哈希表 - 插入、查找和删除的复杂性
Hash tables - complexity of insert, search, and delete
我收到了两道关于散列 table 复杂度的作业，但我很难理解它们之间的区别。
他们如下：
考虑一个哈希函数，它接受 n 个输入并将它们映射到大小为 m 的 table。
写出哈希函数插入、搜索和删除的复杂度，该函数将所有 n 个输入均匀分布在哈希的桶上 table。
写下插入、搜索、删除的复杂度（假设完美但不现实）哈希函数永远不会有两个项目到同一个桶，即这个哈希函数永远不会导致碰撞.
我觉得这两个问题很相似，我不太确定它们的区别。
对于第一个问题，由于 n 个输入是均匀分布的，我们可以假设每个桶中将有零个或一个项目，因此所有插入、搜索和删除都是 O(1)。这是正确的吗？
那么问题二有何不同？如果该函数永远不会导致碰撞，那么所有项目将均匀分布，那么这不会导致每个操作的 O(1) 吗？
对于这些问题我的想法是正确的还是我遗漏了什么？
编辑：
我相信我已经确定哪里出了问题。 O(1) 对于问题 3 中的每个操作都是正确的，因为散列函数是理想的并且永远不会导致冲突。
但是对于问题 2，项目是均匀分布的，但这并不意味着每个桶中只有 1 个项目，例如，每个桶在链表中可以有 20 个项目。所以插入将是 O(1).
但是搜索呢？这将是 O(1) + 搜索链表的成本。但我们不知道大小，只知道它分布均匀。我们能否根据 n（输入数量）和 m（table 的大小）得到长度的表达式？
您的编辑是正确的。
Can we get an expression for the length in terms of n (number of inputs) and m (size of table)?
对于 1，如果散列 table 大小调整以某种方式被抑制，这意味着负载因子（即每个桶的项目数）n/m 大于 1 并且不恒定也不在恒定范围内边界，那么你可以假设一个关系 m = f(n)，那么负载因子将为 n / f(n)，因此复杂度也将为 O(n/f(n))。
在第二种情况下，复杂度总是O(1)。
我收到了两道关于散列 table 复杂度的作业，但我很难理解它们之间的区别。
他们如下：
考虑一个哈希函数，它接受 n 个输入并将它们映射到大小为 m 的 table。
写出哈希函数插入、搜索和删除的复杂度，该函数将所有 n 个输入均匀分布在哈希的桶上 table。
写下插入、搜索、删除的复杂度（假设完美但不现实）哈希函数永远不会有两个项目到同一个桶，即这个哈希函数永远不会导致碰撞.
我觉得这两个问题很相似，我不太确定它们的区别。
对于第一个问题，由于 n 个输入是均匀分布的，我们可以假设每个桶中将有零个或一个项目，因此所有插入、搜索和删除都是 O(1)。这是正确的吗？
那么问题二有何不同？如果该函数永远不会导致碰撞，那么所有项目将均匀分布，那么这不会导致每个操作的 O(1) 吗？
对于这些问题我的想法是正确的还是我遗漏了什么？
编辑：
我相信我已经确定哪里出了问题。 O(1) 对于问题 3 中的每个操作都是正确的，因为散列函数是理想的并且永远不会导致冲突。
但是对于问题 2，项目是均匀分布的，但这并不意味着每个桶中只有 1 个项目，例如，每个桶在链表中可以有 20 个项目。所以插入将是 O(1).
但是搜索呢？这将是 O(1) + 搜索链表的成本。但我们不知道大小，只知道它分布均匀。我们能否根据 n（输入数量）和 m（table 的大小）得到长度的表达式？
您的编辑是正确的。
Can we get an expression for the length in terms of n (number of inputs) and m (size of table)?
对于 1，如果散列 table 大小调整以某种方式被抑制，这意味着负载因子（即每个桶的项目数）n/m 大于 1 并且不恒定也不在恒定范围内边界，那么你可以假设一个关系 m = f(n)，那么负载因子将为 n / f(n)，因此复杂度也将为 O(n/f(n))。
在第二种情况下，复杂度总是O(1)。