當數(shù)據(jù)沒有明確的順序時，集合（sets）和字典（dictionaries）都是理想的數(shù)據(jù)結構侦锯，一個Key唯一對應一個存儲對象趾疚， Key可以是一個string，也可以是任意一個hashable的對象赞草。
字典和集合的插入和查詢的時間復雜度是O(1)，需要額外的內存開銷來支持吆鹤，但是實際上厨疙，插入和查詢的時間取決于在用的hash函數(shù)。dictionaries是Key－Value的集合疑务，sets是一個Key的集合沾凄。
插入和查詢
dictionaries和sets通過使用hash table達到O(1)的插入和查詢效率。對于一個hash表暑始，我們必須搞清楚這段連續(xù)內存里都存放了什么搭独，當我們插入新數(shù)據(jù)時，會產(chǎn)生兩個屬性廊镜，一個是Key的hash值牙肝，另一個是這個hash值和其他值的比較，當一個數(shù)據(jù)插入嗤朴，Key首先被hashed和masked配椭，key被轉化為一個List的高效索引。這個mask來確保雹姊，key的hash值可以為任意的整數(shù)股缸，通過mask可以讓hash值縮小至分配的buckets的范圍內，不會越界吱雏，其實敦姻，一個mask就是一段可變的二進制值0b111, 0b11111,通過mask和hash值的位操作，截斷hash值歧杏。
例如镰惦，如果一個hash表只分配了8塊內存，只能存儲8個對象犬绒，一個key的hash值為28975旺入，最后的index為28975 & 0b111 ＝ 7
當然，我們需要檢查被插入的hash值對應的這塊內存的狀態(tài)，如果這塊內存為空茵瘾，我們將hash值插入列表礼华，把對象復制進內存塊，如果這塊內存為in use拗秘，內存塊里的值為value圣絮，那么該對象已經(jīng)被添加過了，直接return聘殖，如果晨雳，內存塊里的值不為value行瑞，那么奸腺，我們必須找到新的位置去存放該對象。
找到新位置的方法稱為：probing血久，Python的probing機制引入原始hash值的高位bits因素突照，來幫助避免未來的hash沖突。另外氧吐， 一個評判hash表對應的數(shù)據(jù)分布情況的好壞的標準稱為‘load factor’讹蘑，和hash函數(shù)的熵有關。
接下來筑舅，我們看一下Python字典如何根據(jù)一個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現(xiàn)在的機制，linear probing只能處理hash值的最后幾位（比如mask為0b111翠拣，只能截斷最后三位版仔，意味著，當兩個key的最后三位是相同時误墓，不僅會得到相同的hash值蛮粮，而且，也會得到相同的index值谜慌，算法和計算順序無關的）然想，對比后，Python的算法是擾亂的（perturb）欣范，每次計算index時变泄，perturb都會變，也就是恼琼，相同的key的后幾位妨蛹，由于不同的計算順序，返回不同的index驳癌，這處理了hash沖突滑燃。
別忘了我們能這么做的原因是，我們存儲了原始的Key值颓鲜。當查詢時表窘，通過key的hash值得到index典予，對比index中的key值和被查詢的key值是否一致，如果一致返回對象乐严，如果不一致瘤袖，繼續(xù)查詢。
Resizing
當更多的元素被添加到hash表時昂验，hash表必須調整大小來適應捂敌。事實證明，當一個hash表只是2/3被利用時既琴，hash沖突的概率是可以接受的占婉。所以，當hash表的存儲達到這個點時甫恩，我們需要分配更大的hash表逆济，更多的內存塊被分配，mask也調整為新的長度的mask磺箕，所有舊hash表中的數(shù)據(jù)被重新添加到新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抢蚀，所以根據(jù)規(guī)則镀层，Python將分配2048個元素。
