Python dictionary实现

一直对这个蛮有兴趣的，其实只要去看一下源码就可以了，而实际上不用看源码，源码中的注释就已经解释了核心的实现细节：

* 这个hash表的hash算法是看不到的（起码在上面链接的这个文件中看不到），这涉及Python对象的hash处理，但对于int和string，Python居然使用了最最简单的hash算法，这确实让我跌碎眼睛啊。
* 发生冲突时的解决方法很有意思，冲突时不是使用链表，而是使用Open Address方法，即按照一个给定的计算方法计算下一个存储位置，这样的好处应该是可以省去链表带来的内存申请和释放。而这个计算方法也很奇怪，不是+1（这个最简单啊），而是
j = (5*j) + 1 + perturb;
perturb >>= PERTURB_SHIFT;
这个看起来确实是有些复杂，Python的注释解释了， 5*j+1是保证了2**N元素表中可以遍历所有元素（这个怎么证明？），但如果只有5*j+1则生成的遍历顺序总是相同的，意味着冲突可能会累积，所以加上perturb来达到一定的随机效果，当然每次perturb要右移以保证一定次数后，perturb会成为0，这样才能保证遍历性，而perturb的初值就是hashcode。

这叫一个绕啊，今天算是发现我数据结构与算法的知识已经基本上还给亲爱的大学老师了，怎么这些东西好像从未学过的样子啊。。。