高性能Python－字典和集合

當數據沒有明確的順序時，集合（sets）和字典（dictionaries）都是理想的數據結構，一個Key唯一對應一個存儲對象， Key可以是一個string，也可以是任意一個hashable的對象。

字典和集合的插入和查詢的時間復雜度是O(1)，需要額外的內存開銷來支持，但是實際上，插入和查詢的時間取決于在用的hash函數。dictionaries是Key－Value的集合，sets是一個Key的集合。

插入和查詢

dictionaries和sets通過使用hash table達到O(1)的插入和查詢效率。對于一個hash表，我們必須搞清楚這段連續內存里都存放了什么，當我們插入新數據時，會產生兩個屬性，一個是Key的hash值，另一個是這個hash值和其他值的比較，當一個數據插入，Key首先被hashed和masked，key被轉化為一個List的高效索引。這個mask來確保，key的hash值可以為任意的整數，通過mask可以讓hash值縮小至分配的buckets的范圍內，不會越界，其實，一個mask就是一段可變的二進制值0b111, 0b11111,通過mask和hash值的位操作，截斷hash值。

例如，如果一個hash表只分配了8塊內存，只能存儲8個對象，一個key的hash值為28975，最后的index為28975 & 0b111 ＝ 7

當然，我們需要檢查被插入的hash值對應的這塊內存的狀態，如果這塊內存為空，我們將hash值插入列表，把對象復制進內存塊，如果這塊內存為in use，內存塊里的值為value，那么該對象已經被添加過了，直接return，如果，內存塊里的值不為value，那么，我們必須找到新的位置去存放該對象。

找到新位置的方法稱為：probing，Python的probing機制引入原始hash值的高位bits因素，來幫助避免未來的hash沖突。另外， 一個評判hash表對應的數據分布情況的好壞的標準稱為‘load factor’，和hash函數的熵有關。

接下來，我們看一下Python字典如何根據一個Key來確定index：

可以參考Python的源代碼dictobject.c

def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
    perturb = hash(key)
    i = perturb & mask
    yield i
    while True:
        i = ((i << 2) + i + perturb + 1)
        perturb >>= PERTURB_SHIFT
        yield i & mask

上面的這個算法是linear probing的升級版，也是Python現在的機制，linear probing只能處理hash值的最后幾位（比如mask為0b111，只能截斷最后三位，意味著，當兩個key的最后三位是相同時，不僅會得到相同的hash值，而且，也會得到相同的index值，算法和計算順序無關的），對比后，Python的算法是擾亂的（perturb），每次計算index時，perturb都會變，也就是，相同的key的后幾位，由于不同的計算順序，返回不同的index，這處理了hash沖突。

別忘了我們能這么做的原因是，我們存儲了原始的Key值。當查詢時，通過key的hash值得到index，對比index中的key值和被查詢的key值是否一致，如果一致返回對象，如果不一致，繼續查詢。

Resizing

當更多的元素被添加到hash表時，hash表必須調整大小來適應。事實證明，當一個hash表只是 2/3 被利用時，hash沖突的概率是可以接受的。所以，當hash表的存儲達到這個點時，我們需要分配更大的hash表，更多的內存塊被分配，mask也調整為新的長度的mask，所有舊hash表中的數據被重新添加到新hash表中，因為你mask改變了，這個操作需要重新計算所有的index，所以， 調整一個大hash表的開銷是十分昂貴的 。

最小的dictionaries和sets的大小是8(參見Python源碼dictobject.c),也就是說，當你只存儲3個KeyValue時，Python的字典也會分配8個內存塊。

每次resize時，當小于50000個原色時，內存每次隨之遞增4倍，大于50000個時，遞增2倍，也就是說，無論字典和集合內存儲多少個元素，分配的內存只會是如下的size：8，32，128，512，2048，8192，32768...還有很重要的一點不要忘了，我們要保障hash表只有2/3的負載，來確保可以接受的hash碰撞率。所以，當一個字典有1039個元素時，必須至少分配1039 * 5 / 3 = 1731個buckets，所以根據規則，Python將分配2048個元素。

來自：http://www.jianshu.com/p/006fcc73ec07