Ordered hash table in Fortran

What is an hash table

There are many web pages about this topic, see for example https://en.wikipedia.org/wiki/Hash_table.

What is an ordered hash table

In an ordered hash table, the entries are arranged so that the search for a non existing key is faster than in a normal hash table. Donald Knuth wrote an article about several search algorithms, among which the ordered hash table, in the April 1977 issue of Scientific American, pp 63-68. A somewhat more technical story can be found here.

Ordered hash table in Fortran 90

Searching for a Fortran 90 code implementing an hash table, ordered or not, yielded the following:

• http://fortranwiki.org/fortran/show/hash+table+example
  This is a normal hash table, using linked lists. It seems to be not very well tested, does not offer a possibility to resize the table, and does not offer the possibility to remove an entry.

libmodhash

So I created a simple implementation of an ordered hash table in Fortran 90. I took the liberty to incorporate some OO stuff and allocatable strings: you need gfortran-5 or better to use it.

Libmodhash allows you to create an hashtable, using strings for keys and values. If you want other types, use the TRANSFER function, the source code and man page show an example.

Performance of libmodhash

I compared the efficiency of libmodhash with C++'s std::map. Creating the table takes about three times more time than C++, looking up and replace take about 50% more than C++. So, this not ideal, but certainly workable. Suggestions for improvement are welcome!