Английская Википедия:Bidirectional map

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:No footnotes In computer science, a bidirectional map is an associative data structure in which the <math>(key, value)</math> pairs form a one-to-one correspondence. Thus the binary relation is functional in each direction: each <math>value</math> can also be mapped to a unique <math>key</math>. A pair <math>(a, b)</math> thus provides a unique coupling between <math>a</math> and <math>b</math> so that <math>b</math> can be found when <math>a</math> is used as a key and <math>a</math> can be found when <math>b</math> is used as a key.

Mathematically, a bidirectional map can be defined a bijection <math>f: X \to Y</math> between two different sets of keys <math>X</math> and <math>Y</math> of equal cardinality, thus constituting an injective and surjective function:

<math display="block">\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)</math>

External links


Шаблон:Datastructure-stub