Simple hash table implementation

A question for readers, cc: @lkedward , @wclodius :

Recently there was a link posted to a project online (GitHub?) that had various hash functions (DJB2, MD5, SHA*, and more) coded up in Fortran. I’ve misplaced the link, can someone who may recall please post it here? Thanks,

While I have coded up a number of hash functions, none of them is a cryptographic hash such as MD5 and SHA*. I am not aware of anyone else that has coded them up.

Here’s a SHA-256 module: GitHub - leetmaa/bitsy: A fortran module for SHA-256 hashing.

1 Like

Apologies, I do not recall such a collection of Fortran hash implementations – I would certainly be interested in it if found!

Thank you very much @wclodius , @milancurcic , @lkedward for your responses.

I might have been thinking of this GitHub - dbartilson/fh_table: Modern Fortran hash functions and hash tables but, as I mentioned, I have unfortunately misplaced/lost my notes and my memory fails me. However fh_table is close enough to what I wanted to review so that gives me a start.

Regards,

2 Likes

For the sake of completeness, I want to point to a MD5 implementation, which resides inside a High-Energy Physics Monte Carlo program written in (mostly) modern Fortran (I am affiliated with the program, but forgot about its MD5 implementation until it popped up here):

https://whizard.hepforge.org/downloads/

You can find the MD5 implementation (stripped of comments) under src/combinatorics/md5.f90, and the documented source code in share/doc/whizard.pdf.

2 Likes

ftlHashMap
An associative containers that stores elements formed by the combination of a key value and a mapped value, and which allows for fast retrieval of individual elements based on their keys. It’s basically a dictionary that internally uses a hash table to allow constant time retrieval of elements. ftlHashMap is very similar to C++'s std::unordered_map (though its interface is a bit less awkward).

2 Likes

I had the same question and problem about 6 years ago. So my 2 cents here - relatively simple implementation of the non-generic hash table with related modules (linked list, and simple hash functions): zmi_sll_hashtable_module

2 Likes

Thanks, and welcome to Fortran Discourse. The fortran_notes library is now listed at the Fortran Wiki. Your interesting essay What does Fortran need in 2020 to survive? raises issues that are discussed here and which fortran-lang projects are trying to address.

3 Likes

Dear @zmi,
Please if possible correct that page on your Github. It’s too discouraging for a person attempting to learn Fortran. I think some of them are actively being addressed here.

I am deeply sorry for that, but unfortunately, with a single exception of the website/forum for the language, all problems mentioned there, are still not solved. And that text has been written (approx 2017) not to promote the language to the novices. Nevertheless, you are very welcome to write another essay on the topic and to purify all misapprehensions there…

5 Likes

@zmi, I think your blog is fair and accurate and consistent with my view of where things stand though I could not have expressed and distilled my thoughts as well as you did. It was cathartic too in a way for I thought of Veritas liberabit when I read it!! After all things cannot improved if many remain in denial of the reality!!

3 Likes

There is still no book in Fortran for OOP

This was not quite true at the time the essay was written, as Scientific Software Design (by @rouson ) was already available, and recently @milancurcic published his book (Modern Fortran) providing more OO examples.

I don’t disagree much with the rest of what you wrote, but I think we have made good progress within the last year or so towards addressing many of the concerns. Here’s hoping we can continue the momentum.

6 Likes

I would like to clarify some points:

no, I’m not an opponent or a hater of the Fortran language. Yes, it also hurts me when I reread it. Yes, I am worried about the feature of this language, and I wish only stability and prosperity for this project, for the stdlib, and for this very nice Fortran community in the future. I find decreased popularity and poor reputation of the language extremely tragic and unfair. But I also see a bunch of objective reasons why it is happening.

Indeed, there are some exaggerations/hyperbole in the text. If the community believes that it would be wiser to remove this text, I will do it. However, please note, that I did not promote that text in any media and I wrote it rather on strong emotions/after a deep frustration and with a hidden belief and hope that I will be able to write a refutation to each sentence (after a new standard becomes published). I’m sorry that this still has not happened, despite all the efforts of this community.

2 Likes

You make valid points that need to be addressed (and I hope that we are and/or will address them all), and you’re not the only one to have expressed similar opinions. I don’t think you have any reason to take it down. We need people to hold our feet to the fire and encourage us to continually improve. It’s part of how progress is made.

4 Likes

Hi @zmi, thanks for the feedback and the document you wrote. Why don’t you join us at the next Fortran video call and let’s discuss? I agree with almost everything you wrote (the little things I might disagree are not important to discuss right now). That is the main reason I got involved, because at around the same time you wrote this, I realized the same thing. Here are my thoughts how to fix pretty much everything you mentioned as well as our current progress / status:

Resurrecting Fortran

And yes, things are not fixed yet, but I believe we have a plan and initial implementation or effort of almost everything you mentioned. Yes, all this work should have been started 20 years ago, and yes, it cannot be fixed over night, so even though we started serious work on fixing all that, it’s is still not fixed. I believe a reasonable time frame is 3 years from now to either fix or make very serious progress on all these fronts.

But the way I see it is really simple: we either give up on Fortran, and then nothing gets fixed. Or we try fixing it. I chose the latter and that is precisely what we are doing.

If you see any of your points that you think we are not fixing, please let me know and let’s discuss.

1 Like

Dear @certik ,
There used to be person with profile name “difference scheme” who is a strong supporter of Fortran OO’s superiority. What happened to his profile and posts ? He posted a lot on
https://fortran-lang.discourse.group/t/oo-capabilities-of-fortran-2018-vs-c/1076?u=ashok

Moreover I have one question - forgive me if it is wrong.
Why are we trying to implement data structures like Hash tables, Trees … in Fortran? These are already implemented in C and can be easily implemented in C. Why to do them in Fortran, when Fortran is interoperable with C? Why not exploit that feature (interop with C) for data structures and algorithms in stdlib ? If python people thought they would code entire Numpy and Scipy in Python, now there would be none of them. So why not code the data structures in C and provide a Fortran interface.

I am sorry if my idea is a flawed one - but just expressing my thoughts. May be I am not getting interop with C around my head !

1 Like

Maybe I am off the mark but I think part of the development of these structures in Fortran is not to get them into Fortran but to ensure that the facilities exists in the language to develop similar structures and algorithms.

2 Likes

He asked me to delete his account (which deletes his posts). I tried to convince him to stay, but he insisted, so I respect that. “difference scheme”, if you are reading this, you are welcome to come back anytime.

I think languages have to interoperate, and Fortran must interoperate well with other languages and make it easy to use code not only from C, but also C++, Python and others languages.

I think there are two issues with regards to hash tables:

  • Having this capability in the first place: For that, indeed we can either implement in Fortran or another language and expose. It needs to be well supported and stdlib seems like a good place for this. It does not require to modify the language, nor include this in the language itself.

  • Nice syntax: that would require to modify the language. In some sense this is orthogonal to the previous point. I think we should first concentrate on the previous point before trying to tackle this one.

3 Likes

See also here for MD5 and SHA1: petaca/src/secure_hash at master · nncarlson/petaca · GitHub

4 Likes