Hashable in python

The goal of this story

dictionary

One of Python's built-in types is the dictionary.

>>> d = {"zero": False, "one": True}
>>> d["zero"]
False
>>> d["one"]
True
>>> type(d)
<class 'dict'>

Dictionaries are modules without having to use them explicitly in the program

>>> type(__builtins__.__dict__)
<class 'dict'>
>>> import os
>>> type(os.__dict__)
<class 'dict'>

And class attributes

>>> class MyClass(object):
...     def __init__(self):
...         self.a = 1
...
>>> x = MyClass()
>>> x.__dict__
{'a': 1}

It is used implicitly in various places.

Type error when using dictionary

If you specify it as a dictionary key, an error may occur. For example

>>> a = dict()
>>> type(a)
<class 'dict'>
>>> a[[0]] = 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

If you try to use a list as a dictionary key like this, you will get angry because it is an unhashable type. Let's see why there are such restrictions.

What is hash

https://ja.wikipedia.org/wiki/ハッシュ関数

Hash function(Hash function)Or what is a summary function?
An operation to obtain a numerical value representing the data given a certain data, or
A function to obtain such a numerical value.

The meaning of "representing data" is that the value obtained by the hash function

a == b (a.__eq__(b) == True)Then hash(a) == hash(b) (a.__hash__() == b.__hash__())

That it meets.

Significance of hash functions in dictionaries

In dictionaries, hash functions are used to meet the demand for low-cost processing, avoiding the entire search by `` `eq``` when setting and retrieving values.

In CPython's dict implementation,

It has been devised.

Is it hashable if there is a `` `hash``` method?

__hash__Is it hashable as long as there is a method? According to the documentation

http://docs.python.jp/2.7/glossary.html#term-hashable

A hashable object has a hash value that does not change for the rest of its life.(__hash__()Need a method)、...

And it is required that the hash value does not change during the lifetime. However, that is generally not possible, so the dictionary value setting implementation only checks if the hash function can be called.

The classification of builtin objects is

However, what is included in the hashable here is guaranteed that the hash value does not change during the lifetime. But what about user-defined objects?

For user-defined objects

unhashable key

http://docs.python.jp/2.7/reference/datamodel.html#object.hash

The class defines a modifiable object and__cmp__()Or__eq__()Method
If implemented,__hash__()Must not be defined. This is a hash in the dictionary implementation
Because the value is required to be immutable.(When the hash value of an object changes,
Hash bucket with wrong key:It will be in the hash bucket)。

Let's try an example that actually bypasses the key type check. In the example below, UnhashableInFact has a hash function, but the hash value changes during the lifetime of the instance.

wrong_bucket.py


# -*- coding: utf-8 -*-
class UnhashableInFact(object):
    def __init__(self, n):
        self.n = n

    def __hash__(self):
        return hash(self.n)

    def __eq__(self, other):
        return self.n == other.n


if __name__ == '__main__':
    a = UnhashableInFact(1)
    b = UnhashableInFact(2)
    mydict = {a: "value for 1", b: "value for 2"}
    print(mydict[a], mydict[b]) # (1)
    a.n = 2                     #→ Hash value changes
    print(mydict[a], mydict[b]) # (2)
    c = UnhashableInFact(1)
    print(c in mydict)          # (3)

When I executed this, the behavior was as follows.

% python wrong_bucket.py
('value for 1', 'value for 2') # (1)You can retrieve the value from each bucket
('value for 2', 'value for 2') # (2)Both"value for 2"Will take out
False                          # (3)Even if you bring something equal to the original key"value for 1"Cannot be taken out

Why did it behave like this? The dictionary entry is

cpython/Include/dictobject.h


typedef struct {
    /* Cached hash code of me_key.  Note that hash codes are C longs.
     * We have to use Py_ssize_t instead because dict_popitem() abuses
     * me_hash to hold a search finger.
     */
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

It has become

To declare that it is unhashable

http://docs.python.jp/2.7/reference/datamodel.html#object.hash

From the parent class__hash__()Inherit the method,__cmp__()Or__eq__()Meaning of
Changing(For example, changing from a value-based equivalence relation to an identity-based equivalence relation)
Since the hash value of the class is no longer valid__hash__ =Write None in the class definition
You can explicitly declare that it is not hashable.

Let's try it.

unhashable.py


class Unhashable(object):
    __hash__ = None

    def __init__(self, n):
        self.n = n

    def __eq__(self, other):
        return self.n == other.n


if __name__ == '__main__':
    a = Unhashable(1)
    {a: "value for 1"}

That way, you can play it when you use it as a dictionary key:

% python unhashable.py
Traceback (most recent call last):
  File "unhashable.py", line 13, in <module>
    {a: "value for 1"}
TypeError: unhashable type: 'Unhashable'

In Python3, overriding __eq__ will automatically set it to None.

http://docs.python.jp/3/reference/datamodel.html#object.hash

__eq__()Overriding__hash__()Classes that do not define are implicit
Was set to None__hash__()Have. class__hash__()The method is
If None, it is appropriate to try to get the hash value of an instance of that class
TypeError is thrown and isinstance(obj, collections.Hashable)check
Then it will be correctly recognized as non-hashable.

hashable and immutable

http://docs.python.jp/2.7/glossary.html#term-immutable

An object with a fixed value. Immutable objects include numbers, strings,
And tuples and so on. The values of these objects cannot be changed. Another value
You have to create a new object to remember.
Immutable objects play an important role in situations where fixed hash values are required.
An example is a key in a dictionary.

Keys in dictionaries are mentioned as a use of immutable.

Summary

Recommended Posts

Hashable in python
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
SendKeys in Python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
N-Gram in Python
Programming in python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
LINE-Bot [0] in Python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
nCr in Python.
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Quad-tree in Python
Reflection in Python
Chemistry in Python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
Sorted list in Python
Daily AtCoder # 36 in Python
Clustering text in Python
Daily AtCoder # 2 in Python
Implement Enigma in python
Daily AtCoder # 32 in Python
Daily AtCoder # 6 in Python
Daily AtCoder # 18 in Python
Edit fonts in Python
Singleton pattern in Python
File operations in Python
Read DXF in python
Daily AtCoder # 53 in Python
Key input in Python
Use config.ini in Python
Daily AtCoder # 33 in Python
Solve ABC168D in Python
Logistic distribution in Python
Daily AtCoder # 7 in Python
LU decomposition in Python
Simple gRPC in Python
Daily AtCoder # 24 in Python
Solve ABC167-D in Python