python-字典與"有序"字典

python中字典是由key及value所組成的一種容器，可儲存任意類型對象
字典的每個鍵值 key=>value 使用冒號 : 分割，每個鍵值對之間用逗號 , 分割，整個字典用大括號{} ,格式如下所示：

dict = {key1: value1, key2: value2, key3: value3}

鍵(key)是唯一的，由key值可以查找到對應的鍵值(value)
可以通過鍵(key)來引用其值(value)，但是不能通過值獲取鍵
值可以是任何數據類型，但鍵必須是不可變的。

但今天要講的不是字典如何使用
而是python字典的實現方式


一個 dictionary 中不能有重複的 key。給一個存在的 key 賦值會覆蓋原有的值。
Dictionary 沒有元素順序的概念,它們只是簡單排列。

在Python中，dictionary 是通過雜湊表(hash table)實現的。
也就是說，字典是一個陣列，而陣列的索引是鍵經過雜湊函數處理後得到的。雜湊函數的目的是使鍵均勻地分佈在陣列中。

對於hash table
wiki有說明:
雜湊表（Hash table，也叫哈希表），是根據鍵（Key）而直接查詢在內存存儲位置的資料結構。也就是說，它通過計算一個關於鍵值的函數，將所需查詢的數據映射到表中一個位置來查詢記錄，這加快了查找速度。這個映射函數稱做雜湊函數，存放記錄的數組稱做雜湊表。

以電腦的儲存方式來說為什麼要用hash table:
如果一種關鍵碼不能或者不適合作為資料存儲的旗標，可以考慮通過一個變換把它們映射到另一種旗標，這樣子就可以把基於關鍵碼的檢索轉換為基於整數旗標的直接元素訪問。

使用hash table使得python 字典的效率遠大於list

但在某些應用情況下，要使得字典為有序的
這時可以使用 collections

import collections
func = collections.OrderedDict()
func['a'] = 1
func['b'] = 2
print func

有序字典會因插入順序定義排列順序