在SWI-Prolog中实现哈希表

Question

所以我必须实现一个ADT，在这种情况下是SWI-Prolog中的哈希表。我需要帮助，因为我是这种编程语言的新手，并且不知道如何开始。

这开始是python（3）中的一个实现，我在其中定义了一个类并添加了要使用的函数（add，is_empty？，delete，rehash，hash等）。但现在，我需要在prolog中做类似的事情。

我已经访问过类似我的其他一些stackoverflow问题，但我仍然无助。

我希望定义一个基本的哈希表，并能够添加键+值数据和一些其他基本功能。我不太确定这是否已在其他地方实施。请帮忙。

Answer 1

几个Prolog系统提供术语哈希内置或库谓词。例如，SWI-Prolog提供term_hash/2和term_hash/4内置谓词。这些谓词通常与第一个参数索引相结合。一个简单的例子：

% dynamic predicate to hold hash table entries
% with the term hash used as first argument to
% take advantage of first-argument indexing
%
% hash_table(Hash, Term).
:- dynamic(hash_table/2).

add_hash_table_entry(Term) :-
    nonvar(Term),
    term_hash(Term, Hash),      % or term_hash/4
    assertz(hash_table(Hash, Term)).

del_hash_table_entry(Term) :-
    nonvar(Term),
    term_hash(Term, Hash),  % or term_hash/4
    retractall(hash_table(Hash, _)).

hash_table_entry(Term) :-
    (   var(Term) ->
        hash_table(_, Term) 
    ;   term_hash(Term, Hash),  % or term_hash/4
        hash_table(Hash, Term)
    ). 

Answer 2

这听起来像是一个被误导的想法。这个“哈希表”将如何使用？您期望不同的操作具有哪些算法复杂度？为什么要使用不需要用户实现的哈希表的语言实现哈希表？

唯一不太合适的方法是对表使用一个平坦的术语，每个桶使用一个参数。如果你有k个桶，那么你使用一个带有该k的项，所以对于256个桶，你得到hash_table/256。

empty_hash_table(T) :-
    length(Buckets, 256),
    maplist(=(nil), Buckets),
    T =.. [hash_table|Buckets].

您现在可以使用arg/3在恒定时间内获得一个桶。你可以使用setarg/3来改变它们。

但这一切都开始听起来非常可疑。你需要更好地解释你的理由。为什么要在Prolog中实现哈希表？怎么用？