Fortran Wiki
Hash tables

Example libraries

• FLIBS contains generic source code for building hash tables in Fortran.
• The hash table example is an example of a dictionary, or hash table written in Fortran 2003. It contains methods to put and get strings (values) based on string key value pairs. Using the transfer intrinsic, it should be possible to extend this to handle arbitrary data, but for now it works with arbitrary length strings.
• fdict - Fortran type-free variable and type-free dictionary using hash-tables for fast lookups and the transfer intrinsic.
• Fortran Parameter List (FPL) - A Fortran 2003 dictionary to store application parameters.
• fhash - An object oriented implementation in Modern Fortran that supports arbitrary key types and value types. It uses a similar implementation as the GCC 4.8 STL unordered_map.
• ffhash - A generic hash table inspired by khash. Supports automatic resizing as well as custom hash functions. The implementation requires preprocessing of source code.
• fhash - fpm package implementing a hash table with support for generic keys and values.

Discussion

Hash tables are often implemented as an array of pointers which then point to a dynamic data type such as a linked list or a binary tree. They require some hash function as a means to map some key to the appropriate index of the array of pointers. Next, the dynamic data type is traversed, or searched for the corresponding key. If the key exists, then the value may be retrieved or overwritten. If the key does not exist then, if the hash table is being queried, the get method must indicate that the key value pair doesn’t exist. If a put method is being invoked then, if the key value pair is missing from the dynamic data type after, it must be appropriated inserted. The Practice of Programming has a good introductory discussion on page 55. Using a hash table with an appropriately large array of linked lists should provide O(1) lookup and put operations.

Below is a example schematic of a hash table implementation, generated using the graphviz dot language. The source is provided below the image. The image is licensed with a CC-BY-SA license.

Graphviz dot code to create the image above:

// Copyright (c) 2010 Izaak Beekman
// This work is licensed under the Creative Commons Attribution-Share Alike 3.0 United States License. 
// To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/3.0/us/ 
// or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.

// An example of an instantiated dictionary data structure using a Fortran hash table. 
// The outer most level of the object is an array, of pointers, each pointing 
// to a signly-linked list.  Put and get methods hash the key string and store and 
// retrieve the value string.

digraph g {
graph [
rankdir = "LR"
];
node [
fontsize = "8"
shape = "ellipse"
];
edge [
      ];
subgraph cluster_0 {
		style=filled;
		color=lightgrey;
		fontsize = "12";
		"node0" [
			 label = "<f0> vec(0)| <f1> vec(1)| <f2> vec(2)| <f3> ...| <f4> vec(n-1)| <f5> vec(n)"
			 shape = "record"
			 ];
		label = "hash_tbl_sll";
 	}
subgraph cluster_1 {
		style=filled;
		color=lightgrey;
		fontsize = "12";	
		"node1" [
			 label = "<f0> child| <f1> key = 'name'| <f2> val = 'Bob'"
			 shape = "record"
			 ];
		"node2" [
			 label = "<f0> child| <f1> key = 'ID'| <f2> val = '555-66-7777'"
			 shape = "record"
			 ];
		"node3" [
			 label = "<f0> child| <f1> key = 'fruit'| <f2> val = 'tomato'"
			 shape = "record"
			 ];
		"node1":f0 -> "node2";
		"node2":f0 -> "node3";
		label = "sllist 0";
	}
subgraph cluster_2 {
		style=filled;
		color=lightgrey;
		fontsize = "12";
		// "node4" [
		// 	 label = "<f0> child| <f1> key = null()| <f2> val = null()"
		// 	 shape = "record"
		// 	 ];
		"node6" [
			 label = "null()"
			 ];
		label = "sllist 1";
	}
		
"node5" [
label = "null()"
];

subgraph cluster_3 {
		style=filled;
		color=lightgrey;
		fontsize = "12";
		"node7" [
			 label = "<f0> child| <f1> key = 'user_name'| <f2> val = 'jsmith'"
			 shape = "record"
			 ];
		"node8" [
			 label = "<f0> child| <f1> key = 'dog'| <f2> val = 'boxer'"
			 shape = "record"
			 ];
		"node7":f0 -> "node8"
		label = "sllist 2";
	}

subgraph cluster_4 {
		style=filled;
		color=lightgrey;
		fontsize = "12";
		"node10" [
			 label = "<f0> child| <f1> key = 'pass_word'| <f2> val = 'Re411y_c00L'"
			 shape = "record"
			 ];
		label = "sllist n";
	}

subgraph cluster_5 {
		style=filled;
		color=lightgrey;
		fontsize = "12";
		"node12" [
			 label = "<f0> child| <f1> key = 'birthday'| <f2> val = '7/30/1964'"
			 shape = "record"
			 ];
		"node13" [
			 label = "<f0> child| <f1> key = 'car'| <f2> val = '1999 Ford Mustang'"
			 shape = "record"
			 ];
		"node14" [
			 label = "<f0> child| <f1> key = 'zip'| <f2> val = '08544'"
			 shape = "record"
			 ];
		"node15" [
			 label = "<f0> child| <f1> key = 'married'| <f2> val = 'no'"
			 shape = "record"
			 ];
		"node12":f0 -> "node13";
		"node13":f0 -> "node14";
		"node14":f0 -> "node15";
		label = "sllist n-1";
	}

"node9" [
label = "null()"
];

"node11" [
label = "null()"
];

"node16" [
label = "null()"
];

"node3":f0 -> "node5";
"node0":f0 -> "node1";
"node0":f1 -> "node6";
"node0":f2 -> "node7";
"node8":f0 -> "node9";
"node0":f4 -> "node12";
"node10":f0 -> "node11";
"node0":f5 -> "node10";
"node15":f0 -> "node16";

struct10 [
	  shape=plaintext
	  label=<
	  <TABLE BORDER="0">
	  <TR>
	  <TD><IMG SCALE="TRUE"  SRC="88x31-CC-by-sa.png"/></TD>
	  </TR>
	  </TABLE>
	  >
	  ];


}