Hash tables in prolog

Some Prolog environments have Association lists, which can be used to create and edit a dictionary:

• SWI-Prolog
• SICStus Prolog

Edit:

You might be able to get better performance by implementing predicates in foreign languages, for example:

• SWI-Prolog Java or C++
• GNU Prolog C interface
• SICStus C, C++ and Java/.Net.

I just found out that:

SWI-Prolog version 7 introduces dicts as an abstract object with a concrete modern syntax and functional notation for accessing members and as well as access functions defined by the user.

The syntax is as follows:

Tag{Key1:Value1, Key2:Value2, ...}

See Dicts: structures with named arguments for the details.

Note that :

• These are first-class citizens of the language
• Semantics of unification between dicts may change in the future
• The ./2 operator, formerly used for cons-ing, has been repurposed to access dict members via an expressions like point{x:1,y:2}.x
• Dicts can be destructively modified but this is not recommended, being "non-logical", not to mention non-functional.
• The current underlying implementation is "a compound term using the functor dict. The first argument is the tag. The remaining arguments create an array of sorted key-value pairs"

The time-complexity of operations of the present (2019) implementation is given in the SWI Prolog manual under "5.4.5: Implementation Notes about dicts":

Dicts are currently represented as a compound term using the functor dict. The first argument is the tag. The remaining arguments create an array of sorted key-value pairs. This representation is compact and guarantees good locality. Lookup is order log( N ), while adding values, deleting values and merging with other dicts has order N. The main disadvantage is that changing values in large dicts is costly, both in terms of memory and time.

Future versions may share keys in a separate structure or use a binary trees to allow for cheaper updates. One of the issues is that the representation must either be kept cannonical or unification must be extended to compensate for alternate representations.

And also

The SWI-Prolog dicts are built-ins and an SWI-Prolog extension. An alternative is library(assoc), providing maps based on AVL trees via a library (thus available in other implementations, possibly).