# Key Concepts, Weakness and Benchmark on Hash Table Data Structures
## 2 Materials and Methods
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Case Id** & \(\mathbb{K}\) & \(\mathbb{V}\) & **Description** & **Motivation** \\ \hline \multirow{4}{*}{A} & 32-bit integer & double precision float & Keys are consecutive integers multiplied by a constant parameter (\(\lambda\)) and then shuffled before insertion. Values are random floats in [0].1 Iteration computes the average of values, the expected result should be approximately 0.5. & Searching for ranging hash weaknesses and _qualified collision_ resolution. \\  & & & Keys are consecutive integers multiplied by a constant parameter (\(\lambda\)) and then shuffled before insertion. Values are consecutive integers from 1 to Size. Iterations sum up the values and the result is checked with \(\sum_{k=1}^{K}k=\frac{n(n+1)}{2}\). & Separating the performance of access vs. removal/insertion operations. All operations are evaluated around the assigned size. & Separating the performance of access vs. removal/insertion operations. All operations are evaluated around the assigned size. & Separating the performance of access vs. removal/insertion operations. All operations are evaluated around the assigned size. & Separating the performance of access vs. removal/insertion operations. All operations are evaluated around the assigned size. & Separating general performance while using string keys. & Separating performance on noise-to-visual hash functions. Note that Java provides a default implementation. In Python, a tuple could be used for computing a default hash, but in C++ a custom hash is required. & Separating performance using strings once again, albeit this time are random numbers deliberately. \\  & & & Keys are strings, the same as in case D, but twice longer. Values are arrays of 8 random floats from 0 to 1. Iterations compute the average of all numbers. Expected result is 0.5. & Separating performance on bigger \((k,v)\) pairs. As a collateral effect, there are some extra operations per iteration, since up to 8 floats have to be added per element. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of Benchmark Cases. * Two dummy structures: an array adapter and a sequence-of-pairs adapter have been implemented in C++ modeling the map concept. The first is an array, it uses the keys directly as the array indexes, of course, it can only be used in cases A and B since in those cases the keys are consecutive integers and, knowing that, it is possible to skip the hash functions. The array adapter is expected to be the best solution (when applicable). The second is a sequence; in fact, a std::vector of pairs \(\langle k,v\rangle\), where pairs are searched one by one along the sequence when looking for a key. Obviously, this is expected to be the worst solution and, in fact, is only used for small sized cases. * A custom implementation of an Hashed Array-Mapped Trie (HAMT) [13; 14]. This data structure combines the properties of both tree-like structures and hash tables. For such goal, likewise other hash table-like structures, it takes a \(\langle k,v\rangle\) pair and hashes its key in order to compute the location of the value within the underlying structure, which is a custom retrievable tree, also known as trie [6], prefix trees or digital trees. Due to its trie nature, the resulting hash is splitted into several prefixes which will be used to traverse the tree and locate the node corresponding to the key. In our implementation, this size is set to 6 in order to force a size of \(2^{6}=64\) bits on several data structures used in the trie nodes whose memory size depends on the children's cardinality, such as bitmaps. This way these structures fit perfectly on a 64-bit computer word. A remarkable feature of the HAMT is that its nodes contain no null pointers representing empty subtrees. This allows it to optimize memory usage and only allocate pointers representing existing child nodes. Although the original design suggests several tweaks to optimize performance, those have not been included in our implementation.