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.
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.
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.
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,
__eq__ → Avoid the cost of eq```It has been devised.
__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?
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
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.
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.
Recommended Posts