How does contains in HashSet in Java run in O(1) time?

Question

Is it only O(1) when there are no collision. Im talking about a hash table that has Linked Lists in each slot to hold the values.

The dictionary lookup is obviously constant time. The collision lookup can be made small and essentially constant by using a decent hash function with enough slots. — ditkin, Jan 28 '15 at 05:01

score 1 · Answer 1 · answered Jan 28 '15 at 04:49

1

The average number of collisions is O(1), and if your hash function is essentially random you can prove that it's extremely improbable that there are many collisions.

answered Jan 28 '15 at 04:49

Louis Wasserman

191,574
25
345
413

score 1 · Answer 2 · answered Jan 28 '15 at 04:50

1

Yes it is O(1) if you have unique hash for keys and LinkedList or Binary Tree has only one item,

With Java 7 collision resolves to binary tree instead of LinkedList so it is not O(N) for collision

answered Jan 28 '15 at 04:50

jmj

237,923
42
401
438

It is *1* under those circumstances. It is *O(1)* under all non-degenerate circumstances. – user207421 Jan 28 '15 at 04:52
@EJP o(1) if you have hashcode generator generating static value (for example: 1) ? – jmj Jan 28 '15 at 04:53
OK, under all non-degenerate circumstances. – user207421 Jan 28 '15 at 04:54

How does contains in HashSet in Java run in O(1) time?

2 Answers2