# Key Concepts, Weakness and Benchmark on Hash Table Data Structures
## 1 Introduction
### Concepts and Classification of Hash Tables  
Following the previous definitions, an array is a specialized map whose keys are consecutive nonnegative integers and values are any arbitrary type. Hash tables use an array as their base because accessing its elements by an index is classically a constant time operation. However, since we need a full map, there should be a method to produce integer indexes for arbitrary key sets and that is the role of the hash; in fact, the hash functions. Therefore, to define the hash table we need:  
1. An application \(h:\mathbb{K}\rightarrow\mathbb{Z}_{\geq 0}\), this is the _hash_ function, it needs to be an application because any arbitrary \(k\in\mathbb{K}\) needs a corresponding index to be stored in the array. 2. An array that maps: \(\mathbb{Z}_{\geq 0}\rightarrow\mathbb{V}\). That array or the elements of the array in this particular context is usually named _\"bucket\"_. In doing so, some issues arise:  
* It is not possible (neither practical) to have an unlimited size array. * Hash functions should distribute with \"good uniformity\" the images of the keys among the available integers, that is, within the range of indexes of the array. These two issues produce:  
* A new requirement: a new correspondence is needed in order to reduce the range of integers returned by the hash function. That is the real application between keys and indexes is the composition of \(h:\mathbb{K}\rightarrow\mathbb{Z}_{\geq 0}\) and \(h_{r}(N_{b}):\mathbb{Z}_{\geq 0}\rightarrow\{0\ldots N_{b}-1\}\) where \(\{0\ldots N_{b}-1\}\) is the target range of indexes, being \(N_{b}\) the size of the array of _buckets_. The requirement of \(h_{r}\) is seldom mentioned in the user manuals since it has no impact in the user interface. A simple implementation of this reduction is masking the original hash result to \(2^{N_{b}}-1\) which is equivalent to compute \(h(k)\mod N_{b}\). The \(h_{r}\) is called _range-hashing_ (According to [PERSON] and Dreizin nomenclature, \(h_{r}\), the ranged hashing has two parameters, but since the size of the bucket array is part of the state of the hash table object, it has been preferred to describe this function as having another side dependency, just as is \(N_{b}\) were a constant), the composition of the hash function, \(h\) and \(h_{r}\) produces the _composed hash function_ (Anew, in the [PERSON] and Dreizin document, there is not an specific name for this function composition. In their nomenclature, the ranged-hash function is defined as a whole not as a composition of two functions. Note that this ranged-hash function is not available for use in the standard implementation of hash tables (C++, Python, Java,... ). The one available for custom implementation is the hash function), \(h_{c}\), that solves the problem. That is, the composed hash function: \(h_{c}=h_{r}(N_{b})\circ h\), \(h_{c}:\mathbb{K}\rightarrow\{0\ldots N_{b}-1\}\) transforms the elements of the key set into valid indexes of a given array. [8]
* A new concept: the collision, that is, the coincidence of the values of the composed hashing function of two different keys. There is a collision when \(h_{c}(k_{1})=h_{c}(k_{2})\) where \(k_{1},k_{2}\in\mathbb{K}\) and \(k_{1}\
eq k_{2}\)[9]. Note that hash collisions are not the same as hash table collisions since there is an extra reduction step (in fact, \(h_{r}\)) that will necessarily produce more coincidences. Hereafter, these collisions will be denoted as _qualified collisions_. In all hash table designs, the hash function is external to the hash table data structure, for instance, in Java all objects have an inherited method that returns a default hash for the object. In this context, hash functions should be carefully design to produce uniform distributed integers values from arbitrary data but other requirements for a cryptography hash are just not needed. Not surprisingly, in Java and C++ the standard implementation for integer keys is the identity since doing nothing is the fastest alternative and there are no collisions.