# Key Concepts, Weakness and Benchmark on Hash Table Data Structures
## 2 Materials and Methods  
To evaluate performance, several benchmark cases have been written in Java, C++ and Python (Some other languages have been considered and used, but the benchmark cases and result analysis in those languages are not finished). These programming languages have been chosen because they have high rank at the TIOBE index of popularity and have support for generic programming. In fact, C language has been excluded in this study because it does not support generic programming. All sources and materials needed to compile, run, and produce the data (and graphics) in this article are freely available for download or inspection at [[https://bitbucket.org/b-hashtree/b-hashtree/](https://bitbucket.org/b-hashtree/b-hashtree/)]([https://bitbucket.org/b-hashtree/b-hashtree/](https://bitbucket.org/b-hashtree/b-hashtree/)). Requirements to build or run the sources are minimum: a GNU/Linux distribution, a standard C++ compiler, a Java compiler and a Python 3 interpreter. For automatic building and execution _CMake_[11] should be used. To produce the data and graphics, it is also needed a bash shell and a LaTeX compiler with package _pgfplots_ installed. All cases consist of:  
* A program that runs operations on hash tables and other data structures (for comparison) written in at least Java, C++ and Python programming languages, using their standard or most common data structures to model a map. All benchmark cases have some trivial check in order to ensure that the operations are not optimized out and that the program actually does what it is supposed to do. All programs accept a parameter to pass the target size of the data structures (in \(\log_{2}(size)\) for simplicity), that is, the number of elements to be inserted; most of them accept another parameter to select the actual data structure to run the case (when more than one option is available), and some also accept other numerical data to assess the influence of specific factors in the performance. Whenever possible, the number of evaluated operations is also a parameter and does not depend on the size. All programs output the elapsed time or speed (in loop-iterations per millisecond) for some steps in the program. These steps include, at least, a preparation step to generate and insert the elements into the map and another loop executing the operations to be evaluated. Each iteration includes the operation of interest and some other sentences, including conditional sentences for introducing some _branches_ in the loops. Times are taken before and after running the loops using the standard function to access the system time in each language. * Some _Bash_ scripts and _CMake_ configuration files (_CMakelist.txt_). Using _CMake_ and the scripts it is possible to run automatically all the cases without manual manipulation. The result of the different targets is a collection of files (three files per benchmark case): the first one is the standard output of the program and includes the elapsed times and speed computed internally; the second is the output of the _GNU/Linux_ command /bin/time (it is not the time command embedded in Bash) and the third is a logging file with the content from the error standard stream. The first two files are formatted as TSV files and their data will be used without manual manipulation into the TeX documents that generate the graphics. Since all source files, _CMakelist.txt_ files and scripts could be read it is possible to review and validate the whole process. Of course, it is fully reproducible in any computer if the tools are installed. * Some TeX documents that generate the graphics to be displayed. The graphics in this article are a selection among all the graphics that are generated, these graphics already generated were uploaded to the download area in the repository to facilitate casual access. In the graphical representation of results, speed is preferred to time, that way, the bigger are the values, the better is the performance.