Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Contains of HashSet<Integer> in Python

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?

like image 696
Borys Stepov Avatar asked Nov 03 '14 21:11

Borys Stepov


People also ask

Is there a HashSet in Python?

HashSet is used to store the values using a hash table. In this tutorial, we will cover HashSet in Python. We will also learn about how we can design HashSet in Python. HashSet data structure can be created without using any built-in hash table libraries.

Does HashSet O 1 contain?

On average, the contains() of HashSet runs in O(1) time. Getting the object's bucket location is a constant time operation. Taking into account possible collisions, the lookup time may rise to log(n) because the internal bucket structure is a TreeMap.

How do you check if a set contains an element in Python?

To check if the Set contains an element in Python, use the in keyword, which returns True if the specified Set contains an element and False otherwise. The in keyword checks if the item is present in a sequence like a list, range, string, set, etc.


2 Answers

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).

like image 112
tttthomasssss Avatar answered Sep 30 '22 19:09

tttthomasssss


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") 
like image 22
Da Yang Avatar answered Sep 30 '22 18:09

Da Yang