Hashable, immutable

by

Hashing is the process of converting some large amount of data into a much smaller amount (typically a single integer) in a repeatable way so that it can be looked up in a table in constant-time (O(1)), which is important for high-performance algorithms and data structures.

Immutability is the idea that an object will not change in some important way after it has been created, especially in any way that might change the hash value of that object.

The two ideas are related because objects which are used as hash keys must typically be immutable so their hash value doesn’t change. If it was allowed to change then the location of that object in a data structure such as a hashtable would change and then the whole purpose of hashing for efficiency is defeated.

To really grasp the idea you should try to implement your own hashtable in a language like C/C++, or read the Java implementation of the HashMap class.

More Related Contents:

  1. What would a “frozen dict” be?
  2. Python: why can I put mutable object in a dict or set?
  3. Immutable vs Mutable types
  4. About the changing id of an immutable string
  5. How to make an immutable object in Python?
  6. Why can tuples contain mutable items?
  7. hash function in Python 3.3 returns different results between sessions
  8. How to convert SQL Query result to PANDAS Data Structure?
  9. Hashing a dictionary?
  10. Time complexity of python set operations?
  11. Is a Python dictionary an example of a hash table?
  12. Python dictionary : TypeError: unhashable type: ‘list’
  13. Types that define `__eq__` are unhashable?
  14. How can I extract a single value from a JSON response?
  15. How to replace Django’s primary key with a different integer that is unique for that table
  16. Python string with space and without space at the end and immutability
  17. What does hash do in python?
  18. How to sum all the values in a dictionary?
  19. Using a Python Dictionary as a Key (Non-nested)
  20. Python references
  21. What is time complexity of a list to set conversion?
  22. Making a python user-defined class sortable, hashable
  23. How to make a dictionary that returns key for keys missing from the dictionary instead of raising KeyError?
  24. How can I extract a single value from a nested data structure (such as from parsing JSON)?
  25. Asking “is hashable” about a Python value
  26. Does Python have an immutable list?
  27. Python consistent hash replacement
  28. Why and how are Python functions hashable?
  29. Python frozenset hashing algorithm / implementation
  30. Unexpected Behavior of Extend with a list in Python [duplicate]

Leave a Comment