數組尋址容易,插入和删除困難;連結清單尋址困難,插入和删除容易;哈希表插入和删除的時間均取決于查找時間.哈希表在資料和資料存儲位置之間建立了确定的函數關系,是以獲得了高效的查詢效率,而線性表和樹,資料項在結構中的位置是随機的,和資料項取值沒有确定的關系,這種結構上進行查找資料項是基于"比較",查找效率依賴比較次數.
在維基百科中Hash表中slot和bucket是同等的概念:
在dict的實作中,Segment,Slot,bucket是三個逐漸逐漸變小的概念,從fetch可以看出它們的關系:
Segment大小固定我們隻需要随着資料大小不斷修改頂層tuple的size就可以.Segments tuple的最後一個元素是一個空的segment用于後續擴充.Segments每次成倍擴充收縮,這對性能并無很大損害.注意dict對外暴露的接口并沒有包含資料實際的位置資訊.store/3,append/3,append_list/3,update/3,update/4,update_counter/3這些接口都檢查是否需要進行擴充,
filter/2 erase/2會檢查是否需要進行收縮.由于dict能夠随着資料量的變化動态調整進行縮放,兼顧了記憶體消耗和通路效率.
在建立一個dict的時候,Empty會初始化成為一個資料模版
-define(kv(K,V), [K|V]). % Key-Value pair format
dict的鍵值存儲不是improper list,看下面append_bkt的實作,猜測這樣做的目的是把Bag當做一個整體處理.
由于接口和orddict一緻,是以不再贅述,常用接口可以看下下面的兩篇文章
[1] ERLANG DICTIONARY EXAMPLE
<a href="http://abel-perez.com/erlang-dictionary-example">http://abel-perez.com/erlang-dictionary-example</a>
[2] Working with dictionaries in Erlang
<a href="http://www.techrepublic.com/article/working-with-dictionaries-in-erlang/6310730">http://www.techrepublic.com/article/working-with-dictionaries-in-erlang/6310730</a>
Hash Table的維基百科
