这是一个非常普遍的计算机科学基础的问题，而是一个看似直观的基于它们是如何工作的文献中没有。 这是一个语言无关的问题，而是涉及到一组数据类型的内部工作原理。
我已经使用了他们很多次，并建议使用它们来存储独特的价值观和快速访问它们。 据说在大O符号的时间复杂度为O（1）每一个设置访问时间。 这怎么可能，如果集可以包含上千项？ 即使项目是独一无二的。
为了找到在设置的项目，它仍然能够扫描每一个独特的项目，这在大澳是在时间和复杂度为O（n）。 有什么我丢失在这里吗？
在此先感谢您的帮助！ 最彻底的回答得到了票！
甲Set是更一般的一种统称为对象的例子HashedCollections 。 这些使用某种形式的HashTable实际存储和检索它们的元素。
鉴于任何element ，这些表计算的整数值，为它命名的hash 。 有几种熟知的技术来定义元素和它们之间的映射hash值。 有些是内在的 ，在这个意义上， hash不依赖于属性element ，这可能会改变，因此hash仍沿的寿命相同element 。 其他是外在的，因为它们可能取决于属性的意义。 然而，在后一种情况下，假设的是，虽然它们是从一个引用的特定元素将不会被修改HashedCollection （否则HashedCollection必须rehashed ）。
用于存储该程序element的工作原理如下：
hash计算的element 。 index作为所述的其余部分表中被计算hash模的length的表。 index如此计算已被使用，一些政策适用于解决冲突 。 第1步应该是非常快（例如， hash也没有cryptographic强度）。
步骤2假设（在大多数情况下），该表的长度是质数（权力2也使用）
第3步可以基本上两种不同的方法来解决：
j次，直到在槽index + j是免费的，或者 index （ 斗 ） 另外，如果没有足够的空槽（这增加了冲突的概率），该表被放大并rehashed （因为modulo改变）。
具有足够的空闲时隙和所述分度机构的一个相当随机的分布，发现在所需时隙的概率O(1)是非常高的。 当然，如果太多的元素碰撞，平均复杂性不再是O(1)但推测这是由不断增长的政策（+缓解rehash ）。
检索与此类似。 要检查是否element集合中属于，其hash和modulo被计算并且该element与所述目标插槽的内容进行比较。 如果比较失败，搜索在桶直线前进。
元素的去除较为困难时，有没有bucket ，取而代之的是indexes增加，但你的想法。
如果你真的想看到这一切在工作中，继续和调试的基本操作HashedCollections任何的Smalltalk方言。 有趣的很多保障。
