about __hash__

hash表是一个稀疏数组或者说是一个总也填不满的数组。
在标准的数据结构的课本中，hash表中的一个单元叫bucket.在字典中，每个键值对都拥有一个bucket。
在这个bucket中，一部分存储对key(键)的引用，一部分存储对value(值)的引用。由于所有的bucket具有一样的空间。
所以，从一个bucket到另外一个bucket可以通过偏移量(offset)进行转换。

在python的字典中，解释器保持着1/3的buckets空载。如果hash表太拥挤了，解释器会把这些buckets复制到一个有更多空间的地址上。
要在hash表中赋值，首先第一步就是要计算key(键)的哈希值，可以用hash(key)的方式求得。

Hashes and equality

内置函数hash()可以作用于内置类型和任何构造了__hash__方法的用户自定义类型。
如果两个对象相等，那么它们的哈希值必须相等。
比如，1 == 1.0 的结果为True， 那么hash(1) == hash(1.0)的结果也必须为True。
即使int和float的内部表示非常不同。

同样，为了更加有效率的进行索引，哈希值应该均匀分布在字典的索引空间中。
这相当于，值相近的对象的哈希值往往相差十万八千里。比如,
hash(1) = 1
hash(1.0001) = 230584300921345

从python3.3开始，对于str, bytes, datetime对象的哈希值而言，算法更加复杂。
计算这些类型的哈希值往往要加入随机的salt value。(俗称加盐)这个salt value与python的进程相关。
同样的进程中这个salt value 是不变的，当然，切换到另一个解释器后进程不同salt value自然不同。
这一“随机加盐”算法是用来防御DOS攻击的。具体细节在__hash__方法的文档(http://bit.ly/1FESm0m) 中，有所介绍。

hash 表算法

The C function that shuffles the hash bits in case of collision has a curious name: perturb. For all the details,
see dictobject.c in the CPython source code.(http://bit.ly/1FESm0m)

注意事项

字典中，key必须是hashable。
一个对象如果是hashable的，要满足以下几个条件：
1.支持hash()函数，并在这个对象的存在周期内，其hash()函数的返回值不变。
2.支持eq()函数
3.if a==b is True then hash(a) == hash(b) must be true

默认情况下，用户自定义的类型是hashable的，因为hash()函数返回的是其id()函数得到的值，并且彼此之间都不相同。
如果你在自定义的对象中，自定义了__eq__方法，那么你必须也实现__hash__方法，并且保证上面第3个条件的成立。
否则，会破坏hash算法的不变性，导致字典和集合不能可靠处理你的对象的严重后果。
如果自定义的__eq__方法依靠于可变的状态，那么__hash__会抛出TypeError unhashable type: ‘MyClass’类似的异常。

对一个字典增加键值对，会导致存在的键值对的顺序改变

只要你增加新的键值对，解释器就有可能决定增长hash表的空间。
这时，会创建一个新的更大的hash表，并把所有存在的键值对，复制到新的位置上。
这一过程中，会产生新的与旧的hash表中不同的collision，并导致键的排序发生变化。
所有这一过程是随机的，你不能预测发生了什么样的变化。
如果你正在遍历所有的键值对的同时，改变了部分键，你可能并不能遍历到所有的键，甚至那些在原始的表中就存在的键也不会被遍历到。

所以在遍历字典的时候并修改key是一个坏主意。如果需要扫描字典并加入新的键值对，应该分成两个步骤：
1.遍历字典并收集需要改变的键值对，作为第二个字典
2.把第二个字典的内容更新到原来的字典中

在python3中，.keys(), .item(), .values()函数返回的是dictionary view 对象，这一对象具有集合一样的行为。
并且，这种对象具有动态反射机制，实时反映着所属字典的变化。

1==1.0





True




print(hash(1))
print(hash(1.0001))

1
230584300921345



a = {'a':1,'b':2,'c':3}
keys = a.keys()
a['d'] = 4


'd' in keys




True