Archive

Archive for February, 2015

Hash tables in bash scripts


I came across a legacy shell script which was using files to store the intermediate data to accomplish a task.
Looking at the code deeply, I was intrigued why they had written simple Hash Map kind of data structure in a much costly and complex file operations. The reason would be that they might have used to use < bash version 4 which doesn’t have the support for associative array concept.

The usage of associative arrays is simpler at the same time faster than much costlier file operations. File operations are costlier because it uses much slower secondary storage.Since associative array is similar to hash table the access to an element takes barely O(1) time complexity. Where as, if used files for every element one needs to grep or search an element. Assuming for ‘n’ elements the access takes O(n^2) + costly file operations.

There are many great resources online tutorials for associative arrays.

http://www.gnu.org/software/bash/manual/html_node/Arrays.html

http://www.linuxjournal.com/content/bash-associative-arrays

http://www.linuxjournal.com/content/bash-associative-arrays