散列

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

返回一个在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)之间的散列索引I。element(I,T)返回一个列表，包含散列索引相同的所有{Key,Value}键值对。在该列表中可以搜索到所需的{Key,Value}对。

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

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