# Key Concepts, Weakness and Benchmark on Hash Table Data Structures
## 4 Discussion  
The objective of this study was to assess how hash and ranging hash functions could cause a weakness in the standard implementation of hash table. In fact, the results of the case A show that weakness, although it has less importance than expected. Figure 16: Case E. Lookup Speed in C++. Figure 17: Case E. Lookup Speeds. Meanwhile, some unexpected results were found by varying the size, the number of elements, that is, the N, by its common symbol in complexity analysis.As already said, this finding reoriented the survey in order to isolate the influence of the size. One of the main decisions was to design the benchmark cases into two separated steps: building the map, that is the insertion of all elements, and running something else that involves lookup operations. The critical feature about the lookup step is that its loop has a fixed number of iterations. In addition, it makes some kind of accumulative computation to avoid being optimized out by compilers. That way it is possible to measure the times with high reliability, in fact, since the elapsed times are taken before and after the loop and the number of iterations is above hundreds thousands of times; the measure is quite deterministic and the error is very low. Nevertheless, strictly speaking, the measured times include more operations apart from looking up the hash table, but all of them are simple operations and none of them have anything involving a _size_. Note that the number of iterations is the same for all sizes. After these adjustments, it was clear from the facts that look-ups were not constant time. In all languages, in all implementation, sooner or later the look-up speed drops steeply at a size value. That is quite unexpected, all programmer manuals state one way or the other that (average, amortized,...etc.) constant time is guaranteed. None of them mention any limit for that property, but benchmark provides another evidence, that a limit exists. What is the cause of the behavior? Well, complexity analysis is about operations, it counts operations, the operations could be observed and count in source code, but what about memory use? Theoretically, memory use is evaluated in terms of memory limits, that is, nobody care about memory use with respect to performance unless it goes above the hardware limit (the RAM memory). Well, facts establish that memory use matters for algorithm performance. Our last benchmark tries to identify the performance dropping point, and there it was, that point is around the size where the data structure fills the L3 cache memory. That is something expected as cache memory is meant to do that. So, could hash tables be blamed for dropping their performance? The answer is no. As already said and shown in Figures 6 and 7, the performance of an array also drops at a given size, so the _fact_ is that no present or future hash table could achieve an _empirical_ time complexity of \(\mathcal{O}(1)\) because in their actual design they use arrays (the _buckets_) and reading a value from an array is not constant time, that is:  
\[array[i]\textbf{ is not empirically }\mathcal{O}(1) \tag{1}\]  
This is a consequence of the real architecture of modern computers. In the theoretical analysis on complexity, memory is modeled uniformly, but somehow that model is obsolete. Therefore, theory fails to estimate algorithm computing time cost because there is a substantial difference between the theoretical model and the real hardware. In addition to that main finding, the extraordinary importance of hash and ranging hashing was found again and again. For instance, it is really interesting that Java implementation goes faster than C++ in case E, Java has a reputation of being slow, but it wins clearly, and that is an unarguable evidence of the importance of hash function and it also tell us that the performance has no absolute reference between programming language, implementation matters. It is also worth mentioning that Java uses more than one CPU kernel.