Set is a built-in data type present in both Python and Java but both of these languages handles the elements in a set differently. Though the underlying implementation of set is the same in both languages, Java lets you add mutable objects, such as a list to a set, whereas Python does not.
Python Restricts Adding A List To A Set
In python, when you try to add an entire list to a set, compiler throws an error:
Python restricts adding a list to a set
Python restricts adding a list to a set because ‘list’ is an unhashable type. To understand this better, lets first talk about hash values and hash tables.
Hash Value
A hash is a unique value assigned to an object using a hash function. If two objects are equal, then their hash will be the same and vice-versa. You can check the hash of any object in python by:
Hash Table
A hash table is a data structure to store a key-value pair. For any key-value pair, hashtable uses the hash function to compute the hash of the key, and uses that hash value as the memory address to store the data. During lookup of data by the key, the key is hashed and the resulting hash value indicates the location where the corresponding data is stored.
Storing data in hashtable by calculating hash of the key
A set uses a hashtable as its underlying data structure and stores the elements that we add to the set as a key-value pair, with the key as the set element and value as some dummy or null value. The hash of the key, which is the element that is added to the set, is computed and the data is stored at this memory address in the hashtable.
Only Immutable Objects Can Be Hashed
Python has two kinds of data types: mutable and immutable. A mutable object can change its contents whereas immutable objects cannot.
Mutable types: list, dict, set, byte array
Immutable types: int, float, complex, string, tuple, frozen set , bytes
In python, there is a condition for an object to have a hash value:
For an object to be hashable, it has to be immutable.
A list being mutable, cannot be hashed
This is because, once the hash of an object is calculated, it should remain the same across its lifetime. But if the value of an object can change, that is, if it is mutable, the hash will change when the value changes and would cause unexpected behaviours. Hence, python allows hash value for only immutable objects.
What Is The Unexpected Behaviour If Mutable Objects Can Be Hashed And Added To A Set?
Suppose we add a list to a set and assume that we can calculate the hash of this mutable list. The below diagram depicts how modifying the list, that was added to the set, would disrupt the implementation of the hash table.
Hence, if the values inside a set is mutable, there will be a mismatch in the memory location address and hash when the object is modified or updated. Therefore, in python, only immutable objects, like integers, strings or tuples, can be hashed and can be used as elements in a set or as keys of a dictionary even though the set or dictionary itself is mutable.
What Happens In Java?
Though Java uses hashmaps internally to store a HashSet, the core implementation is fundamentally the same as in Python. But as in the case with Python, Java does not restrict adding mutable objects to a set and mutables can also have a hash value.
But if you add a mutable object to a set, and if the object changes its state, the set implementation could cause some confusing behaviour. The object will still be present if you iterate through the set, but it may not appear to be present if you query the set with contains() method. The code below demonstrates this.
When adding objects of a class to a set, it will have this same side-effect if you change the value of any fields in the class, that contributes to the hashCode() of that class (This will not be encountered in the case when the class uses identity hash code and not any overridden implementation of hashCode()). Hence, in Java, it is always safer to remove and re-insert elements in a set after modification, if the modified element contributes to its hashCode().