数组寻址容易,插入和删除困难;链表寻址困难,插入和删除容易;哈希表插入和删除的时间均取决于查找时间.哈希表在数据和数据存储位置之间建立了确定的函数关系,所以获得了高效的查询效率,而线性表和树,数据项在结构中的位置是随机的,和数据项取值没有确定的关系,这种结构上进行查找数据项是基于"比较",查找效率依赖比较次数.
在维基百科中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的维基百科
