\manpage {h\_array} {I,E} {Hashing Arrays} 
 
\definition
An instance $A$ of the parameterized data type \name\ (hashing array)
is an injective mapping from a hashed data type $I$ (cf. section 
\ref{Hashed Types}), called the index type of $A$, to the set of variables 
of arbitrary type $E$, called the element type of $A$. We use $A(i)$ to 
denote the variable indexed by $i$.
 
\creation A 
 
\create {(E\ x)}
   {
creates an injective function $a$ from $I$ to the set of unused variables of
type $E$, assigns $x$ to all variables in the range of $a$ and initializes $A$
with $a$.  }
 
 
\operations 2 4.5 
 
\arrop E\&  {I\ i}
         {  returns the variable $A(i)$ }
 
 
\op  bool defined {(I\ i)}
           {  returns true if $i \in dom(A)$, false otherwise; here
	     $dom(A)$ is the set of all $i\in I$ for which $A[i]$ has
	     already been executed. }
 
 

\bigskip
{\bf forall\_defined}($i,A$) 
$\{$ ``the elements from $dom(A)$ are successively assigned to $i$'' $\}$ 
 
\implementation
Hashing arrays are implemented by hashing with chaining. Access operations 
take expected time $O(1)$. In many cases, hashing arrays are more efficient 
than dictionary arrays (cf. \ref{Dictionary Arrays}).
 
