这是一个非常普遍的基于计算机科学的问题，但基于关于它们如何工作的文献似乎并不直观。这是一个与语言无关的问题，但与Set数据类型如何在内部工作有关。
我已多次使用它们，建议使用它们来存储唯一值并快速访问它们。据推测，在Big-O表示法中，每次访问Set时，其时间和复杂度为O（1）。如果Set可能包含数千个项目，那怎么可能？即使物品是独一无二的。
为了在集合中找到一个项目，它仍然必须扫描每个唯一的项目，其中Big-O的时间和复杂度为O（n）。这里有什么我想念的吗？
在此先感谢您的帮助！最彻底的答案得到了投票！
Set是一种更普遍的物体的例子，统称为HashedCollections。这些使用某种HashTable来实际存储和检索它们的元素。
给定任何element，这些表计算一个整数值，命名为hash。有几种众所周知的技术可以定义元素和它们的hash值之间的映射。有些是内在的，在某种意义上，hash不依赖于element的属性，这可能会改变，因此hash在element的生命中保持不变。其他人是外在的，因为他们可能依赖于属性。然而，在后一种情况下，假设特定元素在从HashedCollection引用时不会被修改（否则HashedCollection必须是rehashed）。
存储element的程序如下：
hash是为element计算的。index计算为hash的其余部分，模数为表格的length。index的槽，则应用一些策略来解决冲突。第一步应该是非常快的（例如，hash没有cryptographic力量）。
步骤2假设（在大多数情况下）表的长度是素数（也使用2的幂）
步骤3可以基本上以两种不同的方式解决：
j次，直到index + j的插槽空闲，或index（桶）处碰撞的元素集合中此外，如果没有足够的空槽（这会增加碰撞的概率），表格会被放大并且rehashed（因为modulo改变了）。
利用足够的空闲时隙和索引机制的相当随机分布，在O(1)中找到所需时隙的概率非常高。当然，如果太多元素发生碰撞，平均复杂性不再是O(1)，但这可以通过不断增长的政策（+ rehash）来缓解。
检索类似。为了检查element是否属于集合，计算其hash和modulo，并将element与目标槽的内容进行比较。如果比较失败，则搜索在桶中线性进行。
当没有bucket而且indexes增加时，元素的去除有点困难，但你明白了。
如果你真的希望看到所有这些工作，请继续调试任何Smalltalk方言中的HashedCollections的基本操作。保证很多乐趣。