HashSet大小操作

Question

HashSet常量时间操作的大小操作如何？
我读过包含和大小操作是恒定的时间。
虽然我明白如何包含恒定时间的操作，不会将大小操作与元素数量成比例（不是线性）？

Answer 1

简短的回答 - 它被缓存了。

较长的答案： HashSet是Set实现，持有HashMap，所有的值是相同的“虚拟价值”。这是size()方法只返回地图的size()。如果你看看HashMap的实现，你会发现它有一个size成员。将元素添加到地图（例如，使用put或putAll）可增加size，并从中删除元素可减少size。这样，因为size始终保持最新状态，所以在调用size()时可以简单地返回，保证持续执行时间。

Answer 2

HashSet内部存储它有多少个元素。

wouldnt size operation是否与元素数成比例（非线性）？

如果没有存储在现场记录保存，大小（）将正比于后盾哈希表的大小，而不是元素的数量，因为你必须在扫描所有的条目，看看是否有东西。除了散列表被分配为显着太大或者删除了很多元素之外，这些往往是相同的（2倍以内）。