文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 电脑基础知识 > Erlang dict
侵权投诉

Erlang dict

Erlang dict

Erlang dict

dict是动态哈希表实现的字典.在接口上和orddict保持一致,在实现上和array动态扩展的思路类似.dict使用的是动态哈希技术实现,理论依据是论文: "The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon" ,论文地址:

doc.guandang.net

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

Segment,Slot,bucket

在维基百科中Hash表中slot和bucket是同等的概念:

The hash function is used to transform the key into the index (the hash) of an element (the slot or bucket) where the corresponding value is to be sought.

在dict的实现中,Segment,Slot,bucket是三个逐渐逐渐变小的概念,从fetch可以看出它们的关系:

fetch(Key, D) ->

Slot = get_slot(D, Key),

Bkt = get_bucket(D, Slot),

try fetch_val(Key, Bkt)

catch

badarg -> erlang:error(badarg, [Key, D])

end.

%% get_slot(Hashdb, Key) -> Slot.

%% Get the slot. First hash on the new range, if we hit a bucket

%% which has not been split use the unsplit buddy bucket.

get_slot(T, Key) ->

H = erlang:phash(Key, T#dict.maxn),

if

H > T#dict.n -> H - T#dict.bso;

true -> H

end.

%% get_bucket(Hashdb, Slot) -> Bucket.

get_bucket(T, Slot) -> get_bucket_s(T#dict.segs, Slot).

Segment大小固定我们只需要随着数据大小不断修改顶层tuple的size就可以.Segments tuple的最后一个元素是一个空的segment用于后续扩展.Segments每次成倍扩展收缩,这对性能并无很大损害.注意dict对外暴露的接口并没有包含数据实际的位置信

第1页

你可能喜欢

热门文档

相关文档

  • Erlang的语言特性

    4.丰富的 libs Erlang中提供丰富的 libs stdlib中包含大量的数据结构如 lists, array, dict, gb_sets, gb_trees, ets, dets等 mnesia提供一个分布式的数据库...

  • Erlang

    无return 语句 进程 使用Erlang编写出的应用运行时通常由成千上万个轻量级进程组成...用来组织整套应用程序 4,application(通用应用程序) 1,Dict,ETS,Mneisa 之间的...

  • erlang环境配置

    然后添加 Erlang 模式,如下: (setq load-path (cons "C:/progra~1/erl5.8...(add-to-list 'ac-dictionary-directories "~/.emacs.d//ac-dict") (ac-...

  • Erlang Memcache

    Erlang Memcache_IT/计算机_专业资料。艾德思奇科技有限公司 www.adSage.cn ...Dict1 Memcache_dict Dict2 Memcache_controler Dict3 Formated key-value (odbc...

  • 基于Erlang的链接管理服务器

    基于Erlang的链接管理服务器_IT/计算机_专业资料。Erlang越来越受人们的青睐了...这个查找过 程一度成为瓶颈 方案性能对比查找方 案 ETS DICT gbtree Register ...

  • erlang闪电入门

    Erlang 闪电入门历史简介 1986 年 - Joe Armstrong 开始在 Ericsson CSLab 尝试...dict # Immutable dictionary data structure set # Immutable set data structure...

  • Erlang应用优化指南

    Erlang应用优化指南余 锋 2009/11/07 ?优化案例 Erlang应用优化案例 ? Ehttpd...? ? ? ? 进程和物理世界的对象1:1 多用ets tuple, list, array dict, ...

  • Erlang应用优化指南

    array dict, process dict 无锁结构有限的调度器 每个调度器一个slot 如何测量 测量什么热点 Erlang代码的热点 Erts的热点 OS的热点 延迟调度排队 抖动不是绝对...

  • erlang-opt-final1

    Erlang应用优化指南余 锋 2009/11/07 ?优化案例 Erlang应用优化案例 ? Ehttpd...? ? ? ? 进程和物理世界的对象1:1 多用ets tuple, list, array dict, ...

  • Windows 下 Emacs + Erlang 开发环境的配置

    Windows 下 Emacs + Erlang 开发环境的配置_IT/计算机_专业资料。Windows 下 ...(add-to-list 'ac-dictionary-directories "~/.emacs.d//ac-dict") 10 (...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email