我对哈希集的理解正确吗？（Python）

Question

我正在通过这本python书自学数据结构，如果我错了，如果有人能纠正我，我将不胜感激，因为哈希集似乎与哈希映射极其相似。在

实施： Hashset是一个list[]或数组，其中每个索引都指向linkedlist的头

所以一些散列（some\u item）-->；key，然后list[key]，然后添加到LinkedList的头上。这发生在O（1）时间内

当从linkedlist中删除一个值时，在python中我们用占位符替换它，因为hashset不允许有Null/None值，对吗？在

当列表[]超过某个加载/满度百分比时，我们将其复制到另一个列表中

关于时间复杂性的混淆： 所以有一个问题是，如果给定索引的linkedlist中可以有N个条目的列表，那么为什么平均搜索/访问是O（1）？在

一般情况下，searchitem不在索引链接列表的中间，所以应该是O（n/2）->O（n）？

另外，在删除一个项目时，如果我们要用占位符值替换它，如果从未使用占位符，这不是在浪费内存吗？在

最后，除了HashMaps可以有null之外，这个和HashMap有什么区别？HashMaps是key/value，而hashset只是value？在

Answer 1

这里已经写了很多关于开放哈希表的文章，但是有些基本点却被忽略了。在

实际实现通常有O（1）查找和删除，因为它们保证bucket不会包含超过固定数量的项（loadfactor）。但这意味着它们只能实现摊销O（1）时间插入，因为表需要随着表的增长定期重组。在

（有些人可能会选择在删除时重新组织，也可以在负载因子达到某个底部阈值时收缩表，这只会影响空间，而不影响渐近运行时间。）

重组意味着增加（或减少）存储桶的数量，并将所有元素重新分配到新的存储桶位置。有一些方案，例如，可扩展散列，可以使其更便宜一些。但一般来说，这意味着要接触表中的每个元素。在

重组，那么，是O（n）。当任何一个给定的人都可能产生这种成本时，怎么可能是O（1）呢？秘诀是摊销和权力的力量。当表格增长时，它必须由一个大于1的因子来增长，其中两个是最常见的。如果表以1个bucket开始，并且每次负载因子达到F时加倍，那么N个重组的成本是

F + 2F + 4F + 8F ... (2^(N-1))F = (2^N - 1)F

此时，表包含(2^(N-1))F元素，即上次重组期间表中的数字。一、 我们已经做了(2^(N-1))F插入，重组的总成本如右图所示。有趣的是表中每个元素的平均成本（或插入，自选）：

^{pr2}$

这就是摊销O（1）的来源。在

另外一点是，对于现代处理器来说，链表并不是存储桶列表的好主意。对于8字节指针，开销是有意义的。更重要的是，单个列表中堆分配的节点在内存中几乎永远不会是连续的。遍历这样一个列表会降低缓存性能，这会使缓存速度降低一个数量级。在

数组（对包含元素的数据数量使用整数计数）可能效果更好。如果负载因子足够小，只需分配一个大小与第一个元素插入bucket时的负载因子相等的数组。否则，以与桶数组相同的方式按因子增长这些元素数组！所有的东西仍将摊销到O（1）。在

要从这样的bucket中删除一个项目，不要将其标记为已删除。只需将最后一个数组元素复制到已删除元素的位置并减少元素计数。当然，如果允许外部指针进入散列桶，这当然行不通，但无论如何，这是个坏主意。在

Answer 2

查找时间不会是O(n)，因为不是所有的项目都需要搜索，它还取决于存储桶的数量。更多的吊桶会降低碰撞的概率并缩短链条的长度。在

通过根据需要调整哈希表的大小，bucket的数量可以保持为条目数量的常量因子。与平均分布值的哈希函数一起，这使期望的链长度有界，从而提供恒定的时间查找。在

hashmaps和hashsets使用的哈希表除了存储不同的值外是相同的。哈希集将包含对单个值的引用，而哈希映射将包含对键和值的引用。哈希集可以通过委托给键和值相同的hashmap来实现。在

Answer 3

对于第一个问题-为什么查找的平均时间复杂度是O（1）？-一般来说，只有当你有一个好的哈希函数时，这个语句才是正确的。一个理想的散列函数是一个在其元素上产生良好扩散的函数。特别是，哈希函数的选择通常使得任意两个元素碰撞的概率很低。在这个假设下，可以正式证明要检查的元素的预期数量是O（1）。如果你在网上搜索“通用散列函数族”，你可能会找到这个结果的一些很好的证明。在

至于使用占位符-有几种不同的方法来实现哈希表。您所使用的方法称为“封闭寻址”或“带链接的散列”，在这种方法中，几乎没有理由使用占位符。然而，也存在其他哈希策略。一种常见的方法称为“开放寻址”（其中最著名的是线性探测散列），在这些设置中，占位符元素是必要的，以避免错误的否定查找。在网上搜索这方面的更多细节可能会给你一个很好的解释。在

至于这与HashMap有何区别，HashMap只是一种可能的映射抽象实现，由哈希表支持。Java的HashMap确实支持null，而其他方法则不支持