# Key Concepts, Weakness and Benchmark on Hash Table Data Structures
## 1 Introduction
### Theoretical and Math Background  
Many authors have described the _map_ (also known as _associative array_) data structure, although those definitions differ in their detail and approach, as a general one we can define as an abstract data type that represents a correspondence between two sets, that is, given two arbitrary sets \(\mathbb{K}\) and \(\mathbb{V}\), \(k\in\mathbb{K}\), \(v\in\mathbb{V}\), a map represents a general correspondence \(k\to v\). A map can also be interpreted as a set of pairs \(\langle k,v\rangle\) that meet the condition that there are no pairs with the same \(k\) values, i.e., \(\forall p,p^{\prime}\in\langle k,v\rangle\), \(p\
eq p^{\prime}\implies k\
eq k^{\prime}\). For now on, \(\mathbb{K}\) will be the set of _keys_ and \(\mathbb{V}\) the set of _values_.  
Maps are translated into programming languages with interfaces that, basically, allow to: insert pairs, get or update values using the key as a parameter, and remove pairs also using the key as parameter. Different programming languages name this abstract data type and its implementations differently. Thus, C++ uses _associate container_ as the name for the map _concept_ (requirement or interface) [1] and map and unordered_map as the names of the main implementation (models) of that concept; Java has an interface Map<K,V> [2] for _maps_ and several standard classes implementing that interface, for instance: HashMap, TreeMap or Hashtable; and Python has a standard class dict that implements the interface of a _map_[3], but note that there is no such a concept of _interface_ in Python. Whatever the names, _map_ implementations can be done using several families of data structures. These three are good examples: standard sequences, tree-like structures, and hash tables:  
* **Standard sequences (or Direct-address tables)** Ref. [4]. Although they are seldom used, arrays or lists can be used as maps as long as they store pairs \(\langle k,v\rangle\) as elements. Since the complexity of searching for a pair is \(\mathcal{O}(n)\) and searching pairs is usually the main application when using maps, this is very uncommon.
* **Tree-like structures.** Balanced Binary Trees [4], AVL Trees [5], or Tries [6] are some alternatives of tree-like structures that could be used for implementing a map. Tree-like data structures have an additional requirement with respect to the other alternatives: they need a sorting operation on the key set, \(\mathbb{K}\). Usually they have \(\mathcal{O}(\log n)\) complexity for accessing elements; thus, although they are used in some applications they are being replaced by hash tables.
* **Hash tables** Ref. [4]. A hash table is basically an array containing the values or other data structures which can store chained values, such as linked lists, as in the std::unordered_map of the GCC implementation of the C++ standard library [7]. The indexes of the array are computed using a hash function. hash table structures have a remarkable property: most of their operations are (amortized, average, etc.) constant time, that is, their theoretical complexity is \(\mathcal{O}(1)\). Of course, such behavior is the most wanted characteristic in any context, and thus they became the object of our study.