Contains of HashSet<Integer> in Python

Question

In Java we have HashSet<Integer>, I need similar structure in Python to use contains like below:

A = [1, 2, 3]
S = set()
S.add(2)
for x in A:
    if S.contains(x):
        print "Example"

Could you please help?

Undressed

docs.python.org/2/library/sets.html – Crosshead

so if x in S means contains? – Undressed

Yes ! you are correct ! – Crosshead

Thank you! Now the question can be removed :) – Undressed

Answer 1

Just use a set:

>>> l = set()
>>> l.add(1)
>>> l.add(2)
>>> 1 in l
True
>>> 34 in l
False

The same works for lists:

>>> ll = [1,2,3]
>>> 2 in ll
True
>>> 23 in ll
False

Edit: Note @bholagabbar's comment below that the time complexity for in checks in lists and tuples is O(n) on average (see the python docs here), whereas for sets it is on average O(1) (worst case also O(n), but is very uncommon and might only happen if __hash__ is implemented poorly).

Sonnier

Complexity for searching an element in Lists and Tuples will be O(n) where as it will be O(1) in Sets and Dictionaries. Hence prefer the former – Cypress

@bholagabbar Hence prefer the latter* – Wolk

@sloreti: Thanks for pointing that out. SO won't let me edit my comment. Also, just as a note, it will be amortized O(1) in Sets and Dictionaries – Cypress

The worst case is O(n) when all hash vales collide, but that's very rare condition – Bodycheck

@tttthomasssss, Thank you for your nice answer. But I think the point mentioned by bholagabbar is very important. So would you mind editing your answer to incorporate the point mentioned by bholagabbar ? – V1

@Md.AbuNafeeIbnaZahid Thank you for your feedback. Have you downvoted my answer because of your question? – Sonnier

@tttthomasssss, Unfortunately yes. I think fundamental concept of HashSet is searching in O(1) which is O(n) in python list. And the current answer mentions about list but doesn't mention about the difference between list and HashSet in searching time complexity though the question was about HashSet. So in my opinion the current answer is somewhat misleading. I think incorporating that point will make your answer a better one and then will surely deserve an upvote. :) – V1

@Md.AbuNafeeIbnaZahid Ok, let me clarify one thing: Downvoting correct & complete (wrt the OPs question) answers is absolutely unacceptable community behaviour. If you have a question ask it in the comments. If you think an answer is incomplete, add an answer of your own (or a comment). And to be clear, nothing in my answer is misleading. It shows a) the python-equivalent to Java's s.contains(x) (ie what the OP asked), and b) that the same syntactic construct can be used to test for membership in lists. Having said that, I can include a pointer to bholagabbar's comment, if its helpful. – Sonnier

@bholagabbar you mean latter not former – Cruiser

For those non-native English speakers confused with former and later: set is a lot better for a contains operation "in" in python: if elem in myset is a lot faster than if elem in mylist – Meissner

Answer 2

In Python, there is a built-in type, set. The major difference from the hashmap in Java is that the Python set is not typed, i.e., it is legal to have a set {'2', 2} in Python.

Out of the box, the class set does not have a contains() method implemented. We typically use the Python keyword in to do what you want, i.e.,

A = [1, 2, 3]
S = set()
S.add(2)
for x in A:
  if x in S:
    print("Example")

If that does not work for you, you can invoke the special method __contains__(), which is NOT encouraged.

A = [1, 2, 3]
S = set()
S.add(2)
for x in A:
  if S.__contains__(x):
    print("Example")

Southeasterly

In python, if you use the in keyword, as in if x in A, the __contains__() method on A (i.e. a set's __contains__() method) will be invoked. Its true that you shouldn't invoke it directly, since its invoked by using the in keyword. – Sonnier