檢查項中是否存在項目由O設置（1）

Question

我正在使用項目的Set。

Set<Objects> myObjects 

此Set可能包含數千個項目。 O（1）可以檢查Set中的物品是否存在，這一點很重要。

我知道Set有一個contains方法，但它的工作順序是什麼？它由O（1）工作嗎？

另外，如果效率不高，如何通過O（1）檢查存在？

Answer 1

HashSet.contains()有O(1)

預期的運行時間從Javadoc：

這個類提供了基本操作（添加，刪除，包含和大小）一定時間的表現，假設哈希函數將元素在桶中正確地分散。迭代此集合需要的時間與HashSet實例的大小（元素數量）加上支持HashMap實例的「容量」（桶的數量）的總和成正比。因此，如果迭代性能很重要，不要將初始容量設置得太高（或者負載因子太低）是非常重要的。

Answer 2

該Set實施HashSet預計可通過O(1)找到值。但是，這意味着要存儲的對象提供hashCode。

在Java 8，你可以通過下面的代碼提供了一個良好的，高效的哈希：

Objects.hash(value1, value2, value3); 

如果使用得當的HashSet的contains - 方法應該按預期工作（即真快）。