# Key Concepts, Weakness and Benchmark on Hash Table Data Structures
## 3 Results
### Results from the Benchmark Cases
#### 3.2.1 Cases A and B  
These cases are designed to find the influence of ranging hashing and qualified collision in the different options. The influence is evident, for instance, Figure 1, shows the lookup speeds against the \(\lambda\), that is, the value that multiplies all consecutive integers before using them as keys. The values correspond to the standard implementation of a hash table in C++, namely std::unordered_map. The speed is ranged from nearly \(4\cdot 10^{4}\) loop iterations per millisecond to under \(3.5\cdot 10^{4}\), so there is enough difference to infer that there is an influence but not a clear tendency, except the fact that the lowest value is at \(\lambda=13\), a prime number. In Java, the same behaviour is observed, but lower values seem to take place at even numbers, specially at those that are powers of 2. For instance, Figure 2 shows the building speed vs. \(\lambda\) using the OpenJDK implementation of the class HashMap. Although the speed values are different in the three speeds of the case A: building, lookup and removing, the curves are very similar for the three steps. The lowest speeds are for Python. Its curves are similar to Java, with lower performance at even numbers. This case is also computed using higher values of \(\lambda\), following powers of 2 beginning at 16. The Figure 3 shows one of these samples: the removal speed vs. \(\lambda\) for the Python standard map: the dictionary (dict class). In all programming language a clear minimum speed could be observed based on these graphics: 64, 128 or 256 are typical values, but they are not the same either among languages or case steps. For instance, the minimum building speed in C++ is at 64 while for removal speed is at 256. Figure 1: Case A. C++ std::unordered_map lookup speeds (\(size=2^{20}\)). Figure 2: Case A. Java HashMap building speeds (\(size=2^{20}\)). Case B is designed to evaluate the combined influence of \(\lambda\) and _size_. It is essential to state that the expected theoretical performance should be constant speed when the size changes. In this case, the focus will be on the lookup step, although all step speeds can be reviewed using the resources located in the repository. The samples in these cases have been parameterized with \(\lambda=\{1,32,1024\}\), thus avoiding the worst values obtained from the previous case and therefore producing a fair comparison between languages. In this case, a lot of samples have been executed, since almost all data structures, standard or not, have been used in this case. All the graphics in Case B have 3 different curves for each data structure, one for each value of \(\lambda\). The speed is displayed vs. the size (number of inserted elements). Both axes have logarithmic scale. For instance, the Figure 4 displays the data for the std::map in C++. This data structure is a tree and the results are not a surprise: its performance decreases with the size (as expected) and \(\lambda\) has very little influence since there is no hash involved. However, displaying the same graphic with std::unordered_map yields surprising results. Figure 5 shows a sharp decline in the standard C++ hash table starting at \(2^{17}\) and well, that is not expected because theoretically the speed should be almost constant, that is, it should keep its value about \(8\cdot 10^{4}\) iterations/ms as it does until that limit. On a first thought, the number of collisions could be blamed for this strange effect, so it was decided to get another reference of complexity \(\mathcal{O}(1)\) and that is the reason for the array adapter. Since in this case the keys are consecutive integers, they could be used directly as indexes in an array, and due to the flexibility of C++ templates, it is possible to program such a not-so-practical data structure without any problem. On the other hand, the influence of the \(\lambda\) parameter is far less important as the effect of the size.