• 散列

    散列

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

    hash(Term,MaxInt)
    返回一个在1..MaxInt范围内的整数。

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

    程序9.4

    1. -module(tupleStore).
    2. -export([new/0,new/1,lookup/2,add/3,delete/2]).
    3.  
    4. new() ->
    5.     new(256).
    6.  
    7. new(NoOfBuckets) ->
    8.     make_tuple(NoOfBuckets, []).
    9.  
    10. lookup(Key, Tuple) ->
    11.     lookup_in_list(Key, element(hash(Key, size(Tuple)), Tuple)).
    12.  
    13. add(Key, Value, Tuple) ->
    14.     Index = hash(Key, size(Tuple)),
    15.     Old   = element(Index, Tuple),
    16.     New   = replace(Key, Value, Old, []),
    17.     setelement(Index, Tuple, New).
    18.  
    19. delete(Key, Tuple) ->
    20.     Index = hash(Key, size(Tuple)),
    21.     Old   = element(Index, Tuple),
    22.     New   = delete(Key, Old, []),
    23.     setelement(Index, Tuple, New).
    24.  
    25. make_tuple(Length, Default) ->
    26.     make_tuple(Length, Default, []).
    27.  
    28. make_tuple(0, _, Acc) ->
    29.     list_to_tuple(Acc);
    30. make_tuple(N, Default, Acc) ->
    31.     make_tuple(N-1, Default, [Default|Acc]).
    32.  
    33. delete(Key, [{Key,_}|T], Acc) ->
    34.     lists:append(T, Acc);
    35. delete(Key, [H|T], Acc) ->
    36.     delete(Key, T, [H|Acc]);
    37. delete(Key, [], Acc) ->
    38.     Acc.
    39.  
    40. replace(Key, Value, [], Acc) ->
    41.     [{Key,Value}|Acc];
    42. replace(Key, Value, [{Key,_}|T], Acc) ->
    43.     [{Key,Value}|lists:append(T, Acc)];
    44. replace(Key, Value, [H|T], Acc) ->
    45.     replace(Key, Value, T, [H|Acc]).
    46.  
    47. lookup_in_list(Key, []) ->
    48.     undefined;
    49. lookup_in_list(Key, [{Key, Value}|_]) ->
    50.     {value, Value};
    51. lookup_in_list(Key, [_|T]) ->
    52.     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。