Bidirectional map

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations . Please help improve this article by introducing more precise citations. (April 2015) (Learn how and when to remove this message)

In computer science, a bidirectional map is an associative data structure in which the $(key,value)$ {\displaystyle (key,value)} pairs form a one-to-one correspondence. Thus the binary relation is functional in each direction: each $value$ {\displaystyle value} can also be mapped to a unique $key$ {\displaystyle key}. A pair $(a,b)$ {\displaystyle (a,b)} thus provides a unique coupling between $a$ {\displaystyle a} and $b$ {\displaystyle b} so that $b$ {\displaystyle b} can be found when $a$ {\displaystyle a} is used as a key and $a$ {\displaystyle a} can be found when $b$ {\displaystyle b} is used as a key.

Mathematically, a bidirectional map can be defined a bijection $f:X\to Y$ {\displaystyle f:X\to Y} between two different sets of keys $X$ {\displaystyle X} and $Y$ {\displaystyle Y} of equal cardinality, thus constituting an injective and surjective function:

${\begin{cases}&\forall x,x'\in X,f(x)=f(x')\Rightarrow x=x'\\&\forall y\in Y,\exists x\in X:y=f(x)\end{cases}}\Rightarrow \exists f^{-1}(x)$ {\displaystyle {\begin{cases}&\forall x,x'\in X,f(x)=f(x')\Rightarrow x=x'\\&\forall y\in Y,\exists x\in X:y=f(x)\end{cases}}\Rightarrow \exists f^{-1}(x)}