home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / h_array.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  1.4 KB  |  57 lines
  1. {\magonebf 4.5 Hashing arrays (h\_array)}
  2.  
  3. An instance $A$ of the data type $h\_array$ (hashing array) is an injective
  4. mapping from a data type $I$, called the index type of $A$, to a set of 
  5. variables of a data type $E$, called the element type of $A$.  $I$ must
  6. be $char$, $int$, a pointer type, or an item type.
  7.  
  8.  
  9. \bigskip
  10. {\bf 1. Declaration of an hashing array type}
  11.  
  12.  
  13. \decltwo h\_array I E 
  14.  
  15. introduces a new data type with name \name\ consisting of all h\_arrays 
  16. with index type $I$ and element type $E$.
  17.  
  18.  
  19. \bigskip
  20. {\bf 2. Creation of a h\_array }
  21.  
  22.  
  23. \create A (x)
  24.  
  25. creates an injective function $a$ from $I$ to the set of unused variables of 
  26. type $E$, assigns $x$ to all variables in the range of $a$ and initializes $A$
  27. with $a$.
  28.  
  29.  
  30.  
  31. \bigskip
  32. {\bf 3. \operations}
  33.  
  34. \+\cleartabs & \hskip 1.8truecm & \hskip 5truecm &\cr
  35. \+\opa E\&   {I\ x}  
  36.                       {returns the variable $A(x)$}
  37. \smallskip
  38. \+\op bool defined {I\ x}
  39.                 {returns true if $x \in dom(A)$, false otherwise; here}
  40. \+\nop          {$dom(A)$ is the set of all $x\in I$ for which $A[x]$ has}
  41. \+\nop          {already been executed.}
  42.  
  43. \bigskip
  44. {\bf 4. Iteration}
  45.  
  46. {\bf forall\_defined}($x,A$) 
  47. $\{$ ``the elements from $dom(A)$ are successively assigned to $x$'' $\}$
  48.  
  49.  
  50. \bigskip
  51. {\bf 5. Implementation}
  52.  
  53. Hashing arrays are implemented by dynamic perfect hashing ([DKMMRT88]). 
  54. Access operations $A[x]$ take time $O(1)$. Hashing arrays are more efficient 
  55. than dictionary arrays.
  56.  
  57.