Method ArraySet#contains(Object) works in linear time

[gvlasov]

Set#contains(Object) is usually supposed to work in constant time. If we pass an ArraySet somewhere as a Set and code there will start checking in a loop if that Set contains particular elements, then the user of this code may be really surprised with degrading performance.

I think it should be documented that ArraySet#contains(Object) is O(n).

[dmarkov]

@yegor256 dispatch this issue please

[yegor256]

@Suseika I think it's better to make it O(1) instead of documenting the bug

[dmarkov]

@suseika thanks for the ticket, your account was topped for 15 mins, payment AP-63B838642P325752Y

[dmarkov]

@amihaiemil can you please help? Keep in mind this. If you have any technical questions, don't hesitate to ask right here

Budget here is 30 mins (keep this principle in mind)

[amihaiemil]

@yegor256 You cannot perform search in an array in O(1), can you? (except the best case complexity, of course) As far as I know, the only structure that does the search in O(1) is a hashtable. In this case, we could turn the array into a hashset and call contains on that hashset.. something like this: public boolean contains(final Object key) { HashSet<T> valuesHashset = Sets.newHashSet(values); return valuesHashset.contains(key);

}

but then the overall complexity of our contains method stays O(n): the array iteration that was previously performed in ArrayList.contains() would now be performed in Sets.newHashSet()

The only possibility to make our contains run in O(1) is to have a HashSet class property to go along with T[]... but then everything loses its purpose, doesn't it? Then the class should be called ArrayHashSet

I will make a PR with only a warning in the javadoc as @Suseika initially said. If you have another suggestion, please let me know.

[amihaiemil]

@dmarkov I've created PR #30 for this issue.

[dmarkov]

@dmarkov I've created PR #30 for this issue.

@amihaiemil thanks

[amihaiemil]

@dmarkov The PR for this has been merged and closed successfully.

[amihaiemil]

@dmarkov This issue was closed.

[dmarkov]

@dmarkov The PR for this has been merged and closed successfully.

@amihaiemil OK

[dmarkov]

@amihaiemil 30 mins sent to your balance (ID AP-9S227435PA183603B), many thanks! It took 168 hours and 30 mins.... +30 to your rating, your total score is +60