想要理解Python中关于字典和集合中的一些特性，他们背后的散列表是非常关键的一环，它们之所以具有这样的性质，基本上全都因为哈希这一双大手在背后操纵，所以，如果读者现在还是不理解Hash——如果是我的学弟，可以去问问信息安全的CZZ老师，并代我向他致谢。
关于效率
我们几乎总是在强调，字典和集合“效率高”，那么，它们的效率究竟有多高？又为什么会出现这种现象？其实如果仅作为应用而言，只需要知道效率真的很高就好了，但如果想要“研究”一下Python，比如说今后想自己写个类库之类的，这样提升效率的方法，起码是可以借鉴。
通过书上的测试，字典的效率起码是列表的数倍，他们用了一个Corei7的电脑在10000000个键的字典里查找1000个数，平均每一个数字只需要0.000337s，然后又分别用List、Set做了各种各样的测试，当然，这个“数倍”只是一个大概齐的说法，因为随着数字数量的增多，这个倍数也在变化——反正，就是快很多。
至于为什么快，还是得看Hash：
散列表为什么会提速
其实对于Python的提速，除了设计更好的后部实现方法，还有嵌入C语言等多种方法，这样的办法我们就不说了，对于C-Python的联动，我打算以后抽空单独说一说。
Python内置了一个hash()函数，用来计算所有可散列的对象的哈希值，在空间上理想的散列表应该是排布得很满的一个表，但是这样的速度就实在有点慢，有时甚至退化到和遍历差不多少，而且学过数据机构的各位应该知道，Hash的退化如果弱到极致，甚至会比遍历还慢。而对于时间理想的Hash，应该具有这样的特征：越是相似但又不同的值，越应该离得远远的，在Python的散列表中，就很符合这样的要求，1.0001、1.0002、1.0003无论是从数值还是二进制还是各种补码反码都非常相似，但是Hash却差非常大。
Python散列表的冲突解决方案
冲突解决方案一直是Hash的重要部分，但是书里却写的非常含糊——也不是含糊吧，反正没有想学习数据结构时候讲的什么移位啊桶状啊这么详细，本菜鸡看了半天也没看出门道来，诸位，如果有谁找到了比较权威又容易懂的讲法，请务必私聊我。
多说两句
我不知道是不是这样——越是啥啥干不了的人，越是一肚子委屈。
网友评论