首页 > Erlang并发教程 > 10.14 Erlang并发编程-散列
2013
11-20

10.14 Erlang并发编程-散列

BACK TOP文章索引

  1. 散列
  2. 共3条评论

散列

Erlang提供了一个可从任意项式产生一个整数散列值的BIF:

hash(Term, MaxInt)

返回一个在1..MaxInt范围内的整数。

借助hash BIF我们可以编写一个高效的字典查询程序。该程序的接口与第??节的二叉树实现的字典几乎完全一样。

程序9.4

-module(tupleStore).
-export([new/0,new/1,lookup/2,add/3,delete/2]).

new() ->
    new(256).

new(NoOfBuckets) ->
    make_tuple(NoOfBuckets, []).

lookup(Key, Tuple) ->
    lookup_in_list(Key, element(hash(Key, size(Tuple)), Tuple)).

add(Key, Value, Tuple) ->
    Index = hash(Key, size(Tuple)),
    Old   = element(Index, Tuple),
    New   = replace(Key, Value, Old, []),
    setelement(Index, Tuple, New).

delete(Key, Tuple) ->
    Index = hash(Key, size(Tuple)),
    Old   = element(Index, Tuple),
    New   = delete(Key, Old, []),
    setelement(Index, Tuple, New).

make_tuple(Length, Default) ->
    make_tuple(Length, Default, []).

make_tuple(0, _, Acc) ->
    list_to_tuple(Acc);
make_tuple(N, Default, Acc) ->
    make_tuple(N-1, Default, [Default|Acc]).

delete(Key, [{Key,_}|T], Acc) ->
    lists:append(T, Acc);
delete(Key, [H|T], Acc) ->
    delete(Key, T, [H|Acc]);
delete(Key, [], Acc) ->
    Acc.

replace(Key, Value, [], Acc) ->
    [{Key,Value}|Acc];
replace(Key, Value, [{Key,_}|T], Acc) ->
    [{Key,Value}|lists:append(T, Acc)];
replace(Key, Value, [H|T], Acc) ->
    replace(Key, Value, T, [H|Acc]).

lookup_in_list(Key, []) ->
    undefined;
lookup_in_list(Key, [{Key, Value}|_]) ->
    {value, Value};
lookup_in_list(Key, [_|T]) ->
    lookup_in_list(Key, T).

该程序与程序??.4的唯一区别就在于函数new/1,我们需要向该函数传入散列表的大小。

程序??.4是传统散列查找程序的一个简单实现。散列表T由一个定长元组表示。为了查找项式Key对应的值,需要计算出一个介于1..size(T)之间的散列索引Ielement(I, T)返回一个列表,包含散列索引相同的所有{Key, Value}键值对。在该列表中可以搜索到所需的{Key, Value}对。

向散列表中插入数据时,首先计算出Key的散列索引整数I,再向element(I, T)返回的列表中插入新的{Key, Value}对。原先与Key关联的值将被丢弃。

tupleStore模块提供了高效的字典。为了提高访问效率散列表的大小必须大于表中所插入的元素的数目。从这种结构中进行查询非常高效,但插入就逊色些。这是因为大部分Erlang视线中BIF setelement(Index, Val, T)每次都会创建一个新的元组T


10.14 Erlang并发编程-散列》有 3 条评论

  1. 因为他没有时间参加中忍考试

留下一个回复

你的email不会被公开。