如果有很多输入和删除，哈希集的 space 复杂度是否更差？
Are hash sets worse in space complexity if there are a lot of inputs and removals?
假设我有一个哈希集，我决定其中只包含 3 个元素。但是，例如，我随机插入和删除 N 个乱码，而一次集合中的元素从不超过 3 个。
这个集合的 space 复杂度是否仍然为 o(1)，或者我可能插入然后删除一百万（或其他）输入的事实是否会改变哈希集，以便集合的大小在某种程度上与 N 成正比？
哈希 table 的 space-complexity 是 O(N+H)，其中 N 是放置在哈希 table 中的元素的（最大）数量，H 是hash table的原始大小（通常是常数）。
例如，如果你的散列函数是X % 51，那么就有51个盒子来存放你的元素。这是 O(1)，固定大小。如果发生散列冲突，您可以使用链表（或其他散列函数）将多个元素存储在一个盒子中。这将增加与存储在散列中的元素数量成比例的内存需求 table，使得大小为 O(N)。
如果您不断插入和删除元素，使得哈希中存储的元素不超过 3 个 (N=3) table，则哈希的大小 table是 O(1)，因为原始大小和最大元素数都是常数。插入和删除元素不会以任何方式改变散列函数。
这将取决于您使用的特定哈希 table 实现，但是哈希 table 的“良好”实现应该可以在 O(1) space.
更具体地说：
如果您使用链式哈希 table，table 通常只会在负载因子（元素与 table 槽的比率）时调整大小超过某个阈值。如果元素总数始终最多为三个，则永远不会触发此条件。
如果您使用布谷鸟哈希 table，如情况 (1)，tables 只会在负载因子很高时调整大小，因此只有三个活动元素 table 一旦大到足以容纳三个项目并保持其负载系数，就不应调整大小。
对于线性探测 table 或其他开放式寻址 table（二次探测、双重哈希等），已删除的元素标有墓碑，这可能会导致table 在删除多个元素后用已用的插槽填充。但是，一旦墓碑数量太大，合理的 table 实现可以通过以当前大小重建 table 轻松解决此问题。因此，大小不应取决于过去插入的元素总数。
对于具有向后移位删除的 Robin Hood 哈希 table，不需要墓碑，并且 table 大小不应增加。
然而，这并不意味着哈希 tables 的所有实现实际上都会这样做。相反，它只是意味着没有“标准”哈希 table 实际上需要根据曾经添加的元素数量而不是在任何一点存储的最大元素数量来增长。
话虽这么说，但我确实想知道散列在这里是否是正确的想法。如果你知道你一次只会处理三个项目并且关心性能，那么只创建三个变量来保存你的三个项目然后检查每个项目可能会更快。
假设我有一个哈希集，我决定其中只包含 3 个元素。但是，例如，我随机插入和删除 N 个乱码，而一次集合中的元素从不超过 3 个。
这个集合的 space 复杂度是否仍然为 o(1)，或者我可能插入然后删除一百万（或其他）输入的事实是否会改变哈希集，以便集合的大小在某种程度上与 N 成正比？
哈希 table 的 space-complexity 是 O(N+H)，其中 N 是放置在哈希 table 中的元素的（最大）数量，H 是hash table的原始大小（通常是常数）。
例如，如果你的散列函数是X % 51，那么就有51个盒子来存放你的元素。这是 O(1)，固定大小。如果发生散列冲突，您可以使用链表（或其他散列函数）将多个元素存储在一个盒子中。这将增加与存储在散列中的元素数量成比例的内存需求 table，使得大小为 O(N)。
如果您不断插入和删除元素，使得哈希中存储的元素不超过 3 个 (N=3) table，则哈希的大小 table是 O(1)，因为原始大小和最大元素数都是常数。插入和删除元素不会以任何方式改变散列函数。
这将取决于您使用的特定哈希 table 实现，但是哈希 table 的“良好”实现应该可以在 O(1) space.
更具体地说：
如果您使用链式哈希 table，table 通常只会在负载因子（元素与 table 槽的比率）时调整大小超过某个阈值。如果元素总数始终最多为三个，则永远不会触发此条件。
如果您使用布谷鸟哈希 table，如情况 (1)，tables 只会在负载因子很高时调整大小，因此只有三个活动元素 table 一旦大到足以容纳三个项目并保持其负载系数，就不应调整大小。
对于线性探测 table 或其他开放式寻址 table（二次探测、双重哈希等），已删除的元素标有墓碑，这可能会导致table 在删除多个元素后用已用的插槽填充。但是，一旦墓碑数量太大，合理的 table 实现可以通过以当前大小重建 table 轻松解决此问题。因此，大小不应取决于过去插入的元素总数。
对于具有向后移位删除的 Robin Hood 哈希 table，不需要墓碑，并且 table 大小不应增加。
然而，这并不意味着哈希 tables 的所有实现实际上都会这样做。相反，它只是意味着没有“标准”哈希 table 实际上需要根据曾经添加的元素数量而不是在任何一点存储的最大元素数量来增长。
话虽这么说，但我确实想知道散列在这里是否是正确的想法。如果你知道你一次只会处理三个项目并且关心性能，那么只创建三个变量来保存你的三个项目然后检查每个项目可能会更快。