详解python数据结构-----字典
在python中字典是一种很重要的数据结构，我们工作中也会他的一些基本操作，今天我们就不讲操作，就简单讲一下他是怎么进行插入和获取的。有需要知道操作的可以去菜鸟教程观看
我们都知道他查询的时间复杂度是O(1)是因为他是键值对的结构，那么我们知道他是怎么进行插入和查询的嘛？
首先我们就说下字典是怎么进行插入的：
插入数据的位置一般取决于数据的两个属性：1-键的哈希值（散列值）；2-该值与其他的值的比较。在我们插入数据的时候首先会通过hash的方法得到哈希值，然后得到的哈希值会和掩码进行进行计算的到一个有效的数组索引，然后将哈希值，键的指针，值的指针放入数组中。
举个例子来说假设初始分配了一个长度为8的数组(可以理解成8个块的内存)，然后我们要放入一个键是name，value是kingname的数据。首先我们会通过hash得出key的哈希值是1278649844881305901，然后我们分配的长度为8数组，掩码就是0b111，通过计算1278649844881305901& 0b111得出索引是5，将数据放到相应的索引位置上，如图所示
看上面得例子有人肯定会问，那肯定会出现相同的索引值，那不就是数据覆盖了吗？
我们上面说过插入数据的位置取决于两个因素，一个是键的哈希值比较，另外一个是该值与其他值的比较。如果索引值相同那么会进行比较，如果是值是相同的那么就不需要插入，反之掩码会使用高比特位进行寻找新的索引，这一个过程被称为嗅探。在这个过程中仅使用了哈希值最后3个字节作为初计算索引但没有考虑其他字节，如果发生哈希值碰撞，在python中会使用哈希值中更多的比特位来解决这个问题。索引上面求索引值实际上是901& 0b111得出索引值的
读取的时候python内部也是进行同样的步骤，先通过hash计算出哈希值，再去与掩码&位运算得出索引值，比较值相同则取出，否则使用高比特位在进行寻找新的索引。
最后我们简单了解下字典是怎么改变大小的，一般在小于50000时每次改变大小都是原来的四倍，大于50000时则为原来的两倍，每次改变大小的时候都是发生在插入的时候，强调一点就是每次改变大小之后原来的数据要重新通过哈希放入，因为长度改变了他的掩码也在变，所以需要重新放入（其实有了解java hashmap不用说就知道为什么，有空写一篇介绍hashmap）。还有一点：一般不超过大小的三分之二具有最佳空间节约的同时依然具有不错的哈希碰撞避免的概率。
这篇博客主要是看完python高性能编程后查阅资料后写出来的，有些名词做了简单的替换，换成更容易理解的。很久之前就想写了就是没时间，没懂得话可以去下面参考知乎上面人讲的，他们说的很清晰易懂。
最后的最后分享出来今天看python高性能看到一段代码，有点神似倒排索引：
很少写博客，有不足之处可以指点出来，谢谢