Home Explore Help
Sign In
mthl
/
texinfo
Watch 1
Star 0
Fork 0
Files Issues 0 Pull Requests 0 Wiki
Tree: 99bb097093
Branches Tags
texinfo
/
js
/
examples
/
kawa
/
Hash-tables.xhtml

Hash-tables.xhtml 52 KB
History Raw

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725 
  1. <?xml version="1.0" encoding="UTF-8" standalone="no"?>
    2. 

  2. <!DOCTYPE html><html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:pls="http://www.w3.org/2005/01/pronunciation-lexicon" xmlns:ssml="http://www.w3.org/2001/10/synthesis" xmlns:svg="http://www.w3.org/2000/svg">
    3. 

  3.   <head>
    4. 

  4.     <title>Hash tables</title>
    5. 

  5.     <link rel="stylesheet" type="text/css" href="docbook-epub.css"/>
    6. 

  6.     <link rel="stylesheet" type="text/css" href="kawa.css"/>
    7. 

  7.     <script src="kawa-ebook.js" type="text/javascript"/>
    8. 

  8.     <meta name="generator" content="DocBook XSL-NS Stylesheets V1.79.1"/>
    9. 

  9.     <link rel="prev" href="Overall-Index.xhtml" title="Index"/>
    10. 

  10.     <link rel="next" href="Eval-and-Environments.xhtml" title="Eval and Environments"/>
    11. 

  11.   </head>
    12. 

  12.   <body>
    13. 

  13.     <header/>
    14. 

  14.     <section class="sect1" title="Hash tables" epub:type="subchapter" id="Hash-tables">
    15. 

  15.       <div class="titlepage">
    16. 

  16.         <div>
    17. 

  17.           <div>
    18. 

  18.             <h2 class="title" style="clear: both">Hash tables</h2>
    19. 

  19.           </div>
    20. 

  20.         </div>
    21. 

  21.       </div>
    22. 

  22.       <p>A <em class="firstterm">hashtable</em> is a data structure that
    23. 

  23. associates keys with values.
    24. 

  24. The hashtable has no intrinsic order for the (key, value) associations
    25. 

  25. it contains, and
    26. 

  26. supports in-place modification as the primary means of setting the contents
    27. 

  27. of a hash table.
    28. 

  28. Any object can be used as a key, provided a <em class="firstterm">hash function</em> and a suitable
    29. 

  29. <em class="firstterm">equivalence function</em> is available.
    30. 

  30. A hash function is a procedure that
    31. 

  31. maps keys to exact integer objects.
    32. 

  32. </p>
    33. 

  33.       <p>The hashtable provides key lookup and destructive update in amortised
    34. 

  34. constant time, provided that a good hash function is used. 
    35. 

  35. A hash function <em class="replaceable"><code>h</code></em> is acceptable for an equivalence predicate <em class="replaceable"><code>e</code></em> iff
    36. 

  36. <code class="literal">(<em class="replaceable"><code>e</code></em> <em class="replaceable"><code>obj1</code></em> <em class="replaceable"><code>obj2</code></em>)</code> implies
    37. 

  37. <code class="literal">(= (<em class="replaceable"><code>h</code></em> <em class="replaceable"><code>obj1</code></em>) (<em class="replaceable"><code>h</code></em> <em class="replaceable"><code>obj2</code></em>))</code>.
    38. 

  38. A hash function <em class="replaceable"><code>h</code></em> is good for a equivalence predicate <em class="replaceable"><code>e</code></em> if
    39. 

  39. it distributes the resulting hash values for non-equal objects
    40. 

  40. (by <em class="replaceable"><code>e</code></em>) as uniformly as possible over the range of hash
    41. 

  41. values, especially in the case when some (non-equal) objects resemble
    42. 

  42. each other by e.g. having common subsequences. This definition is
    43. 

  43. vague but should be enough to assert that e.g. a constant function is
    44. 

  44. not a good hash function.
    45. 

  45. </p>
    46. 

  46.       <p>Kawa provides two complete sets of functions for hashtables:
    47. 

  47. </p>
    48. 

  48.       <div class="itemizedlist" epub:type="list">
    49. 

  49.         <ul class="itemizedlist" style="list-style-type: disc; ">
    50. 

  50.           <li class="listitem" epub:type="list-item">
    51. 

  51.             <p>The functions specified by R6RS have names starting with <code class="literal">hashtable-</code>
    52. 

  52. </p>
    53. 

  53.           </li>
    54. 

  54.           <li class="listitem" epub:type="list-item">
    55. 

  55.             <p>The functions specified by the older
    56. 

  56. <a class="ulink" href="http://srfi.schemers.org/srfi-69/srfi-69.html" target="_top">SRFI-69</a> specifiation
    57. 

  57. have names starting with <code class="literal">hash-table-</code>
    58. 

  58. </p>
    59. 

  59.           </li>
    60. 

  60.         </ul>
    61. 

  61.       </div>
    62. 

  62.       <p>Both interfaces use the same underlying datatype, so it is possible 
    63. 

  63. to mix and match from both sets.
    64. 

  64. That datatype implements <code class="literal">java.util.Map</code>.
    65. 

  65. 

  66. 

  67. 

  68. Freshly-written code should probably use the R6RS functions.
    69. 

  69. </p>
    70. 

  70.       <section class="sect2" title="R6RS hash tables" epub:type="division" id="idm139667873522768">
    71. 

  71.         <div class="titlepage">
    72. 

  72.           <div>
    73. 

  73.             <div>
    74. 

  74.               <h3 class="title">R6RS hash tables</h3>
    75. 

  75.             </div>
    76. 

  76.           </div>
    77. 

  77.         </div>
    78. 

  78.         <p>To use these hash table functions in your Kawa program you must first:
    79. 

  79. </p>
    80. 

  80.         <pre class="screen">(import (rnrs hashtables))
    81. 

  81. </pre>
    82. 

  82.         <p>This section uses the <em class="replaceable"><code>hashtable</code></em> parameter name for arguments that
    83. 

  83. must be hashtables, and the <em class="replaceable"><code>key</code></em> parameter name for arguments that
    84. 

  84. must be hashtable keys.
    85. 

  85. </p>
    86. 

  86.         <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873519424" class="indexterm"/> <code class="function">make-eq-hashtable</code></p>
    87. 

  87.         <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873517008" class="indexterm"/> <code class="function">make-eq-hashtable</code> <em class="replaceable"><code><em class="replaceable"><code>k</code></em></code></em></p>
    88. 

  88.         <div class="blockquote">
    89. 

  89.           <blockquote class="blockquote">
    90. 

  90.             <p>Return a newly allocated mutable hashtable that accepts arbitrary
    91. 

  91. objects as keys, and compares those keys with <code class="literal">eq?</code>.  If an
    92. 

  92. argument is given, the initial capacity of the hashtable is set to
    93. 

  93. approximately <em class="replaceable"><code>k</code></em> elements.
    94. 

  94. </p>
    95. 

  95.           </blockquote>
    96. 

  96.         </div>
    97. 

  97.         <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873512528" class="indexterm"/> <code class="function">make-eqv-hashtable</code></p>
    98. 

  98.         <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873510112" class="indexterm"/> <code class="function">make-eqv-hashtable</code> <em class="replaceable"><code><em class="replaceable"><code>k</code></em></code></em></p>
    99. 

  99.         <div class="blockquote">
    100. 

  100.           <blockquote class="blockquote">
    101. 

  101.             <p>Return a newly allocated mutable hashtable that accepts arbitrary
    102. 

  102. objects as keys, and compares those keys with <code class="literal">eqv?</code>.  If an
    103. 

  103. argument is given, the initial capacity of the hashtable is set to
    104. 

  104. approximately <em class="replaceable"><code>k</code></em> elements.
    105. 

  105. </p>
    106. 

  106.           </blockquote>
    107. 

  107.         </div>
    108. 

  108.         <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873505600" class="indexterm"/> <code class="function">make-hashtable</code> <em class="replaceable"><code><em class="replaceable"><code>hash-function</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>equiv</code></em></code></em></p>
    109. 

  109.         <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873502096" class="indexterm"/> <code class="function">make-hashtable</code> <em class="replaceable"><code><em class="replaceable"><code>hash-function</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>equiv</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>k</code></em></code></em></p>
    110. 

  110.         <div class="blockquote">
    111. 

  111.           <blockquote class="blockquote">
    112. 

  112.             <p><em class="replaceable"><code>hash-function</code></em> and <em class="replaceable"><code>equiv</code></em> must be procedures.
    113. 

  113. <em class="replaceable"><code>hash-function</code></em> should accept a key as an argument and should return
    114. 

  114. a non–negative exact integer object.  <em class="replaceable"><code>equiv</code></em> should accept two
    115. 

  115. keys as arguments and return a single value.  Neither procedure should
    116. 

  116. mutate the hashtable returned by <code class="literal">make-hashtable</code>.
    117. 

  117. </p>
    118. 

  118.             <p>The <code class="literal">make-hashtable</code> procedure returns a newly allocated mutable
    119. 

  119. hashtable using <em class="replaceable"><code>hash-function</code></em> as the hash function and <em class="replaceable"><code>equiv</code></em>
    120. 

  120. as the equivalence function used to compare keys.  If a third argument
    121. 

  121. is given, the initial capacity of the hashtable is set to approximately
    122. 

  122. <em class="replaceable"><code>k</code></em> elements.
    123. 

  123. </p>
    124. 

  124.             <p>Both <em class="replaceable"><code>hash-function</code></em> and <em class="replaceable"><code>equiv</code></em> should behave like pure
    125. 

  125. functions on the domain of keys.  For example, the <code class="literal">string-hash</code>
    126. 

  126. and <code class="literal">string=?</code> procedures are permissible only if all keys are
    127. 

  127. strings and the contents of those strings are never changed so long as
    128. 

  128. any of them continues to serve as a key in the hashtable.  Furthermore,
    129. 

  129. any pair of keys for which <em class="replaceable"><code>equiv</code></em> returns true should be hashed to
    130. 

  130. the same exact integer objects by <em class="replaceable"><code>hash-function</code></em>.
    131. 

  131. </p>
    132. 

  132.             <div class="blockquote">
    133. 

  133.               <blockquote class="blockquote">
    134. 

  134.                 <p><span class="emphasis"><em>Note:</em></span> Hashtables are allowed to cache the results of calling the
    135. 

  135. hash function and equivalence function, so programs cannot rely on the
    136. 

  136. hash function being called for every lookup or update.  Furthermore any
    137. 

  137. hashtable operation may call the hash function more than once.
    138. 

  138. </p>
    139. 

  139.               </blockquote>
    140. 

  140.             </div>
    141. 

  141.           </blockquote>
    142. 

  142.         </div>
    143. 

  143.         <section class="sect3" title="Procedures" epub:type="division" id="idm139667873488544">
    144. 

  144.           <div class="titlepage">
    145. 

  145.             <div>
    146. 

  146.               <div>
    147. 

  147.                 <h4 class="title">Procedures</h4>
    148. 

  148.               </div>
    149. 

  149.             </div>
    150. 

  150.           </div>
    151. 

  151.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873487472" class="indexterm"/> <code class="function">hashtable?</code> <em class="replaceable"><code><em class="replaceable"><code>obj</code></em></code></em></p>
    152. 

  152.           <div class="blockquote">
    153. 

  153.             <blockquote class="blockquote">
    154. 

  154.               <p>Return <code class="literal">#t</code> if <em class="replaceable"><code>obj</code></em> is a hashtable, <code class="literal">#f</code> otherwise.
    155. 

  155. </p>
    156. 

  156.             </blockquote>
    157. 

  157.           </div>
    158. 

  158.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873482752" class="indexterm"/> <code class="function">hashtable-size</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em></p>
    159. 

  159.           <div class="blockquote">
    160. 

  160.             <blockquote class="blockquote">
    161. 

  161.               <p>Return the number of keys contained in <em class="replaceable"><code>hashtable</code></em> as an exact
    162. 

  162. integer object.
    163. 

  163. </p>
    164. 

  164.             </blockquote>
    165. 

  165.           </div>
    166. 

  166.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873478768" class="indexterm"/> <code class="function">hashtable-ref</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>key</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>default</code></em></code></em></p>
    167. 

  167.           <div class="blockquote">
    168. 

  168.             <blockquote class="blockquote">
    169. 

  169.               <p>Return the value in <em class="replaceable"><code>hashtable</code></em> associated with <em class="replaceable"><code>key</code></em>.  If
    170. 

  170. <em class="replaceable"><code>hashtable</code></em> does not contain an association for <em class="replaceable"><code>key</code></em>,
    171. 

  171. <em class="replaceable"><code>default</code></em> is returned.
    172. 

  172. </p>
    173. 

  173.             </blockquote>
    174. 

  174.           </div>
    175. 

  175.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873472048" class="indexterm"/> <code class="function">hashtable-set!</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>key</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>obj</code></em></code></em></p>
    176. 

  176.           <div class="blockquote">
    177. 

  177.             <blockquote class="blockquote">
    178. 

  178.               <p>Change <em class="replaceable"><code>hashtable</code></em> to associate <em class="replaceable"><code>key</code></em> with <em class="replaceable"><code>obj</code></em>, adding a
    179. 

  179. new association or replacing any existing association for <em class="replaceable"><code>key</code></em>, and
    180. 

  180. returns unspecified values.
    181. 

  181. </p>
    182. 

  182.             </blockquote>
    183. 

  183.           </div>
    184. 

  184.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873465760" class="indexterm"/> <code class="function">hashtable-delete!</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>key</code></em></code></em></p>
    185. 

  185.           <div class="blockquote">
    186. 

  186.             <blockquote class="blockquote">
    187. 

  187.               <p>Remove any association for <em class="replaceable"><code>key</code></em> within <em class="replaceable"><code>hashtable</code></em> and returns
    188. 

  188. unspecified values.
    189. 

  189. </p>
    190. 

  190.             </blockquote>
    191. 

  191.           </div>
    192. 

  192.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873460848" class="indexterm"/> <code class="function">hashtable-contains?</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>key</code></em></code></em></p>
    193. 

  193.           <div class="blockquote">
    194. 

  194.             <blockquote class="blockquote">
    195. 

  195.               <p>Return <code class="literal">#t</code> if <em class="replaceable"><code>hashtable</code></em> contains an association for <em class="replaceable"><code>key</code></em>,
    196. 

  196. <code class="literal">#f</code> otherwise.
    197. 

  197. </p>
    198. 

  198.             </blockquote>
    199. 

  199.           </div>
    200. 

  200.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873455152" class="indexterm"/> <code class="function">hashtable-update!</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>key</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>proc</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>default</code></em></code></em></p>
    201. 

  201.           <div class="blockquote">
    202. 

  202.             <blockquote class="blockquote">
    203. 

  203.               <p><em class="replaceable"><code>proc</code></em> should accept one argument, should return a single value, and
    204. 

  204. should not mutate <em class="replaceable"><code>hashtable</code></em>.
    205. 

  205. </p>
    206. 

  206.               <p>The <code class="literal">hashtable-update!</code> procedure applies <em class="replaceable"><code>proc</code></em> to the value
    207. 

  207. in <em class="replaceable"><code>hashtable</code></em> associated with <em class="replaceable"><code>key</code></em>, or to <em class="replaceable"><code>default</code></em> if
    208. 

  208. <em class="replaceable"><code>hashtable</code></em> does not contain an association for <em class="replaceable"><code>key</code></em>.  The
    209. 

  209. <em class="replaceable"><code>hashtable</code></em> is then changed to associate <em class="replaceable"><code>key</code></em> with the value
    210. 

  210. returned by <em class="replaceable"><code>proc</code></em>.
    211. 

  211. </p>
    212. 

  212.               <p>The behavior of <code class="literal">hashtable-update!</code> is equivalent to the following
    213. 

  213. code, but is may be (and is in Kawa) implemented more efficiently in cases
    214. 

  214. where the implementation can avoid multiple lookups of the same key:
    215. 

  215. </p>
    216. 

  216.               <pre class="screen">(hashtable-set!
    217. 

  217.   hashtable key
    218. 

  218.   (proc (hashtable-ref
    219. 

  219.          hashtable key default)))
    220. 

  220. </pre>
    221. 

  221.             </blockquote>
    222. 

  222.           </div>
    223. 

  223.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873442944" class="indexterm"/> <code class="function">hashtable-copy</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em></p>
    224. 

  224.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873439984" class="indexterm"/> <code class="function">hashtable-copy</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>mutable</code></em></code></em></p>
    225. 

  225.           <div class="blockquote">
    226. 

  226.             <blockquote class="blockquote">
    227. 

  227.               <p>Return a copy of <em class="replaceable"><code>hashtable</code></em>.  If the <em class="replaceable"><code>mutable</code></em> argument is
    228. 

  228. provided and is true, the returned hashtable is mutable; otherwise it is
    229. 

  229. immutable.
    230. 

  230. </p>
    231. 

  231.             </blockquote>
    232. 

  232.           </div>
    233. 

  233.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873434960" class="indexterm"/> <code class="function">hashtable-clear!</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em></p>
    234. 

  234.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873432000" class="indexterm"/> <code class="function">hashtable-clear!</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em> <em class="replaceable"><code><em class="replaceable"><code>k</code></em></code></em></p>
    235. 

  235.           <div class="blockquote">
    236. 

  236.             <blockquote class="blockquote">
    237. 

  237.               <p>Remove all associations from <em class="replaceable"><code>hashtable</code></em> and returns unspecified
    238. 

  238. values.
    239. 

  239. </p>
    240. 

  240.               <p>If a second argument is given, the current capacity of the hashtable is
    241. 

  241. reset to approximately <em class="replaceable"><code>k</code></em> elements.
    242. 

  242. </p>
    243. 

  243.             </blockquote>
    244. 

  244.           </div>
    245. 

  245.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873426592" class="indexterm"/> <code class="function">hashtable-keys</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em></p>
    246. 

  246.           <div class="blockquote">
    247. 

  247.             <blockquote class="blockquote">
    248. 

  248.               <p>Return a vector of all keys in <em class="replaceable"><code>hashtable</code></em>.  The order of the vector
    249. 

  249. is unspecified.
    250. 

  250. </p>
    251. 

  251.             </blockquote>
    252. 

  252.           </div>
    253. 

  253.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873422656" class="indexterm"/> <code class="function">hashtable-entries</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em></p>
    254. 

  254.           <div class="blockquote">
    255. 

  255.             <blockquote class="blockquote">
    256. 

  256.               <p>Return two values, a vector of the keys in <em class="replaceable"><code>hashtable</code></em>, and a vector
    257. 

  257. of the corresponding values.
    258. 

  258. </p>
    259. 

  259.               <p>Example:
    260. 

  260. </p>
    261. 

  261.               <pre class="screen">(let ((h (make-eqv-hashtable)))
    262. 

  262.   (hashtable-set! h 1 'one)
    263. 

  263.   (hashtable-set! h 2 'two)
    264. 

  264.   (hashtable-set! h 3 'three)
    265. 

  265.   (hashtable-entries h))
    266. 

  266. ⇒ #(1 2 3) #(one two three) ; two return values
    267. 

  267. </pre>
    268. 

  268.               <p>the order of the entries in the result vectors is not known.
    269. 

  269. </p>
    270. 

  270.             </blockquote>
    271. 

  271.           </div>
    272. 

  272.         </section>
    273. 

  273.         <section class="sect3" title="Inspection" epub:type="division" id="idm139667873417072">
    274. 

  274.           <div class="titlepage">
    275. 

  275.             <div>
    276. 

  276.               <div>
    277. 

  277.                 <h4 class="title">Inspection</h4>
    278. 

  278.               </div>
    279. 

  279.             </div>
    280. 

  280.           </div>
    281. 

  281.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873416000" class="indexterm"/> <code class="function">hashtable-equivalence-function</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em></p>
    282. 

  282.           <div class="blockquote">
    283. 

  283.             <blockquote class="blockquote">
    284. 

  284.               <p>Return the equivalence function used by <em class="replaceable"><code>hashtable</code></em> to compare keys.
    285. 

  285. For hashtables created with <code class="literal">make-eq-hashtable</code> and
    286. 

  286. <code class="literal">make-eqv-hashtable</code>, returns <code class="literal">eq?</code> and <code class="literal">eqv?</code>
    287. 

  287. respectively.
    288. 

  288. </p>
    289. 

  289.             </blockquote>
    290. 

  290.           </div>
    291. 

  291.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873410192" class="indexterm"/> <code class="function">hashtable-hash-function</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em></p>
    292. 

  292.           <div class="blockquote">
    293. 

  293.             <blockquote class="blockquote">
    294. 

  294.               <p>Return the hash function used by <em class="replaceable"><code>hashtable</code></em>.  For hashtables
    295. 

  295. created by <code class="literal">make-eq-hashtable</code> or <code class="literal">make-eqv-hashtable</code>,
    296. 

  296. <code class="literal">#f</code> is returned.
    297. 

  297. </p>
    298. 

  298.             </blockquote>
    299. 

  299.           </div>
    300. 

  300.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873404928" class="indexterm"/> <code class="function">hashtable-mutable?</code> <em class="replaceable"><code><em class="replaceable"><code>hashtable</code></em></code></em></p>
    301. 

  301.           <div class="blockquote">
    302. 

  302.             <blockquote class="blockquote">
    303. 

  303.               <p>Return <code class="literal">#t</code> if <em class="replaceable"><code>hashtable</code></em> is mutable, otherwise <code class="literal">#f</code>.
    304. 

  304. </p>
    305. 

  305.             </blockquote>
    306. 

  306.           </div>
    307. 

  307.         </section>
    308. 

  308.         <section class="sect3" title="Hash functions" epub:type="division" id="idm139667873400176">
    309. 

  309.           <div class="titlepage">
    310. 

  310.             <div>
    311. 

  311.               <div>
    312. 

  312.                 <h4 class="title">Hash functions</h4>
    313. 

  313.               </div>
    314. 

  314.             </div>
    315. 

  315.           </div>
    316. 

  316.           <p>The <code class="literal">equal-hash</code>, <code class="literal">string-hash</code>, and <code class="literal">string-ci-hash</code>
    317. 

  317. procedures of this section are acceptable as the hash functions of a
    318. 

  318. hashtable only if the keys on which they are called are not mutated
    319. 

  319. while they remain in use as keys in the hashtable.
    320. 

  320. </p>
    321. 

  321.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873397200" class="indexterm"/> <code class="function">equal-hash</code> <em class="replaceable"><code><em class="replaceable"><code>obj</code></em></code></em></p>
    322. 

  322.           <div class="blockquote">
    323. 

  323.             <blockquote class="blockquote">
    324. 

  324.               <p>Return an integer hash value for <em class="replaceable"><code>obj</code></em>, based on its structure and
    325. 

  325. current contents.  This hash function is suitable for use with
    326. 

  326. <code class="literal">equal?</code> as an equivalence function.
    327. 

  327. </p>
    328. 

  328.               <div class="blockquote">
    329. 

  329.                 <blockquote class="blockquote">
    330. 

  330.                   <p><span class="emphasis"><em>Note:</em></span> Like <code class="literal">equal?</code>, the <code class="literal">equal-hash</code> procedure must
    331. 

  331. always terminate, even if its arguments contain cycles.
    332. 

  332. </p>
    333. 

  333.                 </blockquote>
    334. 

  334.               </div>
    335. 

  335.             </blockquote>
    336. 

  336.           </div>
    337. 

  337.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873391088" class="indexterm"/> <code class="function">string-hash</code> <em class="replaceable"><code><em class="replaceable"><code>string</code></em></code></em></p>
    338. 

  338.           <div class="blockquote">
    339. 

  339.             <blockquote class="blockquote">
    340. 

  340.               <p>Return an integer hash value for <em class="replaceable"><code>string</code></em>, based on its current
    341. 

  341. contents.  This hash function is suitable for use with <code class="literal">string=?</code>
    342. 

  342. as an equivalence function.
    343. 

  343. </p>
    344. 

  344.             </blockquote>
    345. 

  345.           </div>
    346. 

  346.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873386592" class="indexterm"/> <code class="function">string-ci-hash</code> <em class="replaceable"><code><em class="replaceable"><code>string</code></em></code></em></p>
    347. 

  347.           <div class="blockquote">
    348. 

  348.             <blockquote class="blockquote">
    349. 

  349.               <p>Return an integer hash value for <em class="replaceable"><code>string</code></em> based on its current
    350. 

  350. contents, ignoring case.  This hash function is suitable for use with
    351. 

  351. <code class="literal">string-ci=?</code> as an equivalence function.
    352. 

  352. </p>
    353. 

  353.             </blockquote>
    354. 

  354.           </div>
    355. 

  355.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873382080" class="indexterm"/> <code class="function">symbol-hash</code> <em class="replaceable"><code><em class="replaceable"><code>symbol</code></em></code></em></p>
    356. 

  356.           <div class="blockquote">
    357. 

  357.             <blockquote class="blockquote">
    358. 

  358.               <p>Return an integer hash value for <em class="replaceable"><code>symbol</code></em>.
    359. 

  359. </p>
    360. 

  360.             </blockquote>
    361. 

  361.           </div>
    362. 

  362.         </section>
    363. 

  363.       </section>
    364. 

  364.       <section class="sect2" title="SRFI-69 hash tables" epub:type="division" id="idm139667873378016">
    365. 

  365.         <div class="titlepage">
    366. 

  366.           <div>
    367. 

  367.             <div>
    368. 

  368.               <h3 class="title">SRFI-69 hash tables</h3>
    369. 

  369.             </div>
    370. 

  370.           </div>
    371. 

  371.         </div>
    372. 

  372.         <p>To use these hash table functions in your Kawa program you must first:
    373. 

  373. </p>
    374. 

  374.         <pre class="screen">(require 'srfi-69)
    375. 

  375. </pre>
    376. 

  376.         <p>or
    377. 

  377. </p>
    378. 

  378.         <pre class="screen">(require 'hash-table)
    379. 

  379. </pre>
    380. 

  380.         <p>or
    381. 

  381. </p>
    382. 

  382.         <pre class="screen">(import (srfi 69 basic-hash-tables))
    383. 

  383. </pre>
    384. 

  384.         <section class="sect3" title="Type constructors and predicate" epub:type="division" id="idm139667873375216">
    385. 

  385.           <div class="titlepage">
    386. 

  386.             <div>
    387. 

  387.               <div>
    388. 

  388.                 <h4 class="title">Type constructors and predicate</h4>
    389. 

  389.               </div>
    390. 

  390.             </div>
    391. 

  391.           </div>
    392. 

  392.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873374128" class="indexterm"/> <code class="function">make-hash-table</code> [ <em class="replaceable"><code>equal?</code></em> [ <em class="replaceable"><code>hash</code></em> [ <em class="replaceable"><code>size-hint</code></em>]]] <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>hash-table</code></em></p>
    393. 

  393.           <div class="blockquote">
    394. 

  394.             <blockquote class="blockquote">
    395. 

  395.               <p>Create a new hash table with no associations.
    396. 

  396. The <em class="replaceable"><code>equal?</code></em> parameter is a predicate
    397. 

  397. that should accept two keys and return a boolean telling whether they
    398. 

  398. denote the same key value; it defaults to the <code class="literal">equal?</code> function.
    399. 

  399. </p>
    400. 

  400.               <p>The <em class="replaceable"><code>hash</code></em> parameter is a hash function, and defaults to an 
    401. 

  401. appropriate hash function
    402. 

  402. for the given <em class="replaceable"><code>equal?</code></em> predicate (see the Hashing section).
    403. 

  403. However, an
    404. 

  404. acceptable default is not guaranteed to be given for any equivalence
    405. 

  405. predicate coarser than <code class="literal">equal?</code>, except for <code class="literal">string-ci=?</code>.
    406. 

  406. (The function <code class="literal">hash</code> is acceptable for <code class="literal">equal?</code>, so if you
    407. 

  407. use coarser equivalence than <code class="literal">equal?</code> other than <code class="literal">string-ci=?</code>,
    408. 

  408. you must always provide the function hash yourself.)
    409. 

  409. (An equivalence predicate <em class="replaceable"><code>c1</code></em> is coarser than a equivalence
    410. 

  410. predicate <em class="replaceable"><code>c2</code></em> iff there exist values <em class="replaceable"><code>x</code></em> and <em class="replaceable"><code>y</code></em> such
    411. 

  411. that <code class="literal">(and (<em class="replaceable"><code>c1</code></em> <em class="replaceable"><code>x</code></em> <em class="replaceable"><code>y</code></em>) (not (<em class="replaceable"><code>c2</code></em> <em class="replaceable"><code>x</code></em> <em class="replaceable"><code>y</code></em>)))</code>.)
    412. 

  412. </p>
    413. 

  413.               <p>The <em class="replaceable"><code>size-hint</code></em> parameter can be used to suggested an approriate
    414. 

  414. initial size.  This option is not part of the SRFI-69 specification
    415. 

  415. (though it is handled by the reference implementation), so specifying
    416. 

  416. that option might be unportable.
    417. 

  417. </p>
    418. 

  418.             </blockquote>
    419. 

  419.           </div>
    420. 

  420.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873357984" class="indexterm"/> <code class="function">hash-table?</code> <em class="replaceable"><code>obj</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>boolean</code></em></p>
    421. 

  421.           <div class="blockquote">
    422. 

  422.             <blockquote class="blockquote">
    423. 

  423.               <p>A predicate to test whether a given object <em class="replaceable"><code>obj</code></em> is a hash table.
    424. 

  424. </p>
    425. 

  425.             </blockquote>
    426. 

  426.           </div>
    427. 

  427.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873353360" class="indexterm"/> <code class="function">alist-&gt;hash-table</code> <em class="replaceable"><code>alist</code></em> [ <em class="replaceable"><code>equal?</code></em> [ <em class="replaceable"><code>hash</code></em> [ <em class="replaceable"><code>size-hint</code></em>]]] <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>hash-table</code></em></p>
    428. 

  428.           <div class="blockquote">
    429. 

  429.             <blockquote class="blockquote">
    430. 

  430.               <p>Takes an association list <em class="replaceable"><code>alist</code></em> and creates a hash table
    431. 

  431. <em class="replaceable"><code>hash-table</code></em> which maps the <code class="literal">car</code> of every element in
    432. 

  432. <em class="replaceable"><code>alist</code></em> to the <code class="literal">cdr</code> of corresponding elements in
    433. 

  433. <em class="replaceable"><code>alist</code></em>. The <em class="replaceable"><code>equal?</code></em>, <em class="replaceable"><code>hash</code></em>, and <em class="replaceable"><code>size-hint</code></em>
    434. 

  434. parameters are interpreted as in <code class="literal">make-hash-table</code>. If some key
    435. 

  435. occurs multiple times in <em class="replaceable"><code>alist</code></em>, the value in the first
    436. 

  436. association will take precedence over later ones. (Note: the choice of
    437. 

  437. using <code class="literal">cdr</code> (instead of <code class="literal">cadr</code>) for values tries to strike
    438. 

  438. balance between the two approaches: using <em class="replaceable"><code>cadr</code></em> would render this
    439. 

  439. procedure unusable for <code class="literal">cdr</code> alists, but not vice versa.)
    440. 

  440. </p>
    441. 

  441.             </blockquote>
    442. 

  442.           </div>
    443. 

  443.         </section>
    444. 

  444.         <section class="sect3" title="Reflective queries" epub:type="division" id="idm139667873340864">
    445. 

  445.           <div class="titlepage">
    446. 

  446.             <div>
    447. 

  447.               <div>
    448. 

  448.                 <h4 class="title">Reflective queries</h4>
    449. 

  449.               </div>
    450. 

  450.             </div>
    451. 

  451.           </div>
    452. 

  452.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873339792" class="indexterm"/> <code class="function">hash-table-equivalence-function</code> <em class="replaceable"><code>hash-table</code></em></p>
    453. 

  453.           <div class="blockquote">
    454. 

  454.             <blockquote class="blockquote">
    455. 

  455.               <p>Returns the equivalence predicate used for keys of <em class="replaceable"><code>hash-table</code></em>.
    456. 

  456. </p>
    457. 

  457.             </blockquote>
    458. 

  458.           </div>
    459. 

  459.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873335936" class="indexterm"/> <code class="function">hash-table-hash-function</code> <em class="replaceable"><code>hash-table</code></em></p>
    460. 

  460.           <div class="blockquote">
    461. 

  461.             <blockquote class="blockquote">
    462. 

  462.               <p>Returns the hash function used for keys of <em class="replaceable"><code>hash-table</code></em>.
    463. 

  463. </p>
    464. 

  464.             </blockquote>
    465. 

  465.           </div>
    466. 

  466.         </section>
    467. 

  467.         <section class="sect3" title="Dealing with single elements" epub:type="division" id="idm139667873332080">
    468. 

  468.           <div class="titlepage">
    469. 

  469.             <div>
    470. 

  470.               <div>
    471. 

  471.                 <h4 class="title">Dealing with single elements</h4>
    472. 

  472.               </div>
    473. 

  473.             </div>
    474. 

  474.           </div>
    475. 

  475.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873330992" class="indexterm"/> <code class="function">hash-table-ref</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>key</code></em> [ <em class="replaceable"><code>thunk</code></em> ] <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>value</code></em></p>
    476. 

  476.           <div class="blockquote">
    477. 

  477.             <blockquote class="blockquote">
    478. 

  478.               <p>This procedure returns the value associated to <em class="replaceable"><code>key</code></em> in
    479. 

  479. <em class="replaceable"><code>hash-table</code></em>. If no value is associated to <em class="replaceable"><code>key</code></em> and
    480. 

  480. <em class="replaceable"><code>thunk</code></em> is given, it is called with no arguments and its value is
    481. 

  481. returned; if <em class="replaceable"><code>thunk</code></em> is not given, an error is signalled. Given a
    482. 

  482. good hash function, this operation should have an (amortised) complexity
    483. 

  483. of O(1) with respect to the number of associations in <em class="replaceable"><code>hash-table</code></em>.
    484. 

  484. </p>
    485. 

  485.             </blockquote>
    486. 

  486.           </div>
    487. 

  487.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873323072" class="indexterm"/> <code class="function">hash-table-ref/default</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>key</code></em> <em class="replaceable"><code>default</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>value</code></em></p>
    488. 

  488.           <div class="blockquote">
    489. 

  489.             <blockquote class="blockquote">
    490. 

  490.               <p>Evaluates to the same value as <code class="literal">(hash-table-ref <em class="replaceable"><code>hash-table</code></em>
    491. 

  491. <em class="replaceable"><code>key</code></em> (lambda () <em class="replaceable"><code>default</code></em>))</code>. Given a good hash function, this
    492. 

  492. operation should have an (amortised) complexity of O(1) with respect
    493. 

  493. to the number of associations in hash-table.
    494. 

  494. </p>
    495. 

  495.             </blockquote>
    496. 

  496.           </div>
    497. 

  497.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873316224" class="indexterm"/> <code class="function">hash-table-set!</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>key</code></em> <em class="replaceable"><code>value</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>void</code></em></p>
    498. 

  498.           <div class="blockquote">
    499. 

  499.             <blockquote class="blockquote">
    500. 

  500.               <p>This procedure sets the value associated to <em class="replaceable"><code>key</code></em> in
    501. 

  501. <em class="replaceable"><code>hash-table</code></em>. The previous association (if any) is removed. Given
    502. 

  502. a good hash function, this operation should have an (amortised)
    503. 

  503. complexity of O(1) with respect to the number of associations in
    504. 

  504. hash-table.
    505. 

  505. </p>
    506. 

  506.             </blockquote>
    507. 

  507.           </div>
    508. 

  508.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873310144" class="indexterm"/> <code class="function">hash-table-delete!</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>key</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>void</code></em></p>
    509. 

  509.           <div class="blockquote">
    510. 

  510.             <blockquote class="blockquote">
    511. 

  511.               <p>This procedure removes any association to <em class="replaceable"><code>key</code></em> in
    512. 

  512. <em class="replaceable"><code>hash-table</code></em>. It is not an error if no association for the
    513. 

  513. <em class="replaceable"><code>key</code></em> exists; in this case, nothing is done. Given a good hash
    514. 

  514. function, this operation should have an (amortised) complexity of O(1)
    515. 

  515. with respect to the number of associations in hash-table.
    516. 

  516. </p>
    517. 

  517.             </blockquote>
    518. 

  518.           </div>
    519. 

  519.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873304032" class="indexterm"/> <code class="function">hash-table-exists?</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>key</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>boolean</code></em></p>
    520. 

  520.           <div class="blockquote">
    521. 

  521.             <blockquote class="blockquote">
    522. 

  522.               <p>This predicate tells whether there is any association to <em class="replaceable"><code>key</code></em> in
    523. 

  523. <em class="replaceable"><code>hash-table</code></em>. Given a good hash function, this operation should
    524. 

  524. have an (amortised) complexity of O(1) with respect to the number of
    525. 

  525. associations in hash-table.
    526. 

  526. </p>
    527. 

  527.             </blockquote>
    528. 

  528.           </div>
    529. 

  529.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873298400" class="indexterm"/> <code class="function">hash-table-update!</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>key</code></em> <em class="replaceable"><code>function</code></em> [ <em class="replaceable"><code>thunk</code></em> ] <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>void</code></em></p>
    530. 

  530.           <div class="blockquote">
    531. 

  531.             <blockquote class="blockquote">
    532. 

  532.               <p>Semantically equivalent to, but may be implemented more efficiently than,
    533. 

  533. the following code:
    534. 

  534. </p>
    535. 

  535.               <pre class="screen">(hash-table-set! <em class="replaceable"><code>hash-table key</code></em>
    536. 

  536.                  (function (hash-table-ref <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>key</code></em> <em class="replaceable"><code>thunk</code></em>)))
    537. 

  537. </pre>
    538. 

  538.             </blockquote>
    539. 

  539.           </div>
    540. 

  540.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873290880" class="indexterm"/> <code class="function">hash-table-update!/default</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>key</code></em> <em class="replaceable"><code>function</code></em> <em class="replaceable"><code>default</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>void</code></em></p>
    541. 

  541.           <div class="blockquote">
    542. 

  542.             <blockquote class="blockquote">
    543. 

  543.               <p>Behaves as if it evaluates to
    544. 

  544. <code class="literal">(hash-table-update! <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>key</code></em> <em class="replaceable"><code>function</code></em> (lambda () <em class="replaceable"><code>default</code></em>))</code>.
    545. 

  545. </p>
    546. 

  546.             </blockquote>
    547. 

  547.           </div>
    548. 

  548.         </section>
    549. 

  549.         <section class="sect3" title="Dealing with the whole contents" epub:type="division" id="idm139667873283328">
    550. 

  550.           <div class="titlepage">
    551. 

  551.             <div>
    552. 

  552.               <div>
    553. 

  553.                 <h4 class="title">Dealing with the whole contents</h4>
    554. 

  554.               </div>
    555. 

  555.             </div>
    556. 

  556.           </div>
    557. 

  557.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873282240" class="indexterm"/> <code class="function">hash-table-size</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>integer</code></em></p>
    558. 

  558.           <div class="blockquote">
    559. 

  559.             <blockquote class="blockquote">
    560. 

  560.               <p>Returns the number of associations in <em class="replaceable"><code>hash-table</code></em>. This operation takes
    561. 

  561. constant time.
    562. 

  562. </p>
    563. 

  563.             </blockquote>
    564. 

  564.           </div>
    565. 

  565.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873277552" class="indexterm"/> <code class="function">hash-table-keys</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>list</code></em></p>
    566. 

  566.           <div class="blockquote">
    567. 

  567.             <blockquote class="blockquote">
    568. 

  568.               <p>Returns a list of keys in <em class="replaceable"><code>hash-table</code></em>.
    569. 

  569. The order of the keys is unspecified.
    570. 

  570. </p>
    571. 

  571.             </blockquote>
    572. 

  572.           </div>
    573. 

  573.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873272848" class="indexterm"/> <code class="function">hash-table-values</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>list</code></em></p>
    574. 

  574.           <div class="blockquote">
    575. 

  575.             <blockquote class="blockquote">
    576. 

  576.               <p>Returns a list of values in <em class="replaceable"><code>hash-table</code></em>. The order of the values is
    577. 

  577. unspecified, and is not guaranteed to match the order of keys in the
    578. 

  578. result of <code class="literal">hash-table-keys</code>.
    579. 

  579. </p>
    580. 

  580.             </blockquote>
    581. 

  581.           </div>
    582. 

  582.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873267664" class="indexterm"/> <code class="function">hash-table-walk</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>proc</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>void</code></em></p>
    583. 

  583.           <div class="blockquote">
    584. 

  584.             <blockquote class="blockquote">
    585. 

  585.               <p><em class="replaceable"><code>proc</code></em> should be a function taking two arguments, a key and a
    586. 

  586. value. This procedure calls <em class="replaceable"><code>proc</code></em> for each association in
    587. 

  587. <em class="replaceable"><code>hash-table</code></em>, giving the key of the association as key and the
    588. 

  588. value of the association as value. The results of <em class="replaceable"><code>proc</code></em> are
    589. 

  589. discarded. The order in which <em class="replaceable"><code>proc</code></em> is called for the different
    590. 

  590. associations is unspecified.
    591. 

  591. </p>
    592. 

  592.             </blockquote>
    593. 

  593.           </div>
    594. 

  594.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873260736" class="indexterm"/> <code class="function">hash-table-fold</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>f</code></em> <em class="replaceable"><code>init-value</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>final-value</code></em></p>
    595. 

  595.           <div class="blockquote">
    596. 

  596.             <blockquote class="blockquote">
    597. 

  597.               <p>This procedure calls <em class="replaceable"><code>f</code></em> for every association in <em class="replaceable"><code>hash-table</code></em>
    598. 

  598. with three arguments: the key of the association key, the value of the
    599. 

  599. association value, and an accumulated value, <em class="replaceable"><code>val</code></em>. The <em class="replaceable"><code>val</code></em>
    600. 

  600. is <em class="replaceable"><code>init-value</code></em> for the first invocation of <em class="replaceable"><code>f</code></em>, and for
    601. 

  601. subsequent invocations of <em class="replaceable"><code>f</code></em>, the return value of the previous
    602. 

  602. invocation of <em class="replaceable"><code>f</code></em>. The value <em class="replaceable"><code>final-value</code></em> returned by
    603. 

  603. <code class="literal">hash-table-fold</code> is the return value of the last invocation of
    604. 

  604. <em class="replaceable"><code>f</code></em>. The order in which <em class="replaceable"><code>f</code></em> is called for different
    605. 

  605. associations is unspecified.
    606. 

  606. </p>
    607. 

  607.             </blockquote>
    608. 

  608.           </div>
    609. 

  609.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873250368" class="indexterm"/> <code class="function">hash-table-&gt;alist</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>alist</code></em></p>
    610. 

  610.           <div class="blockquote">
    611. 

  611.             <blockquote class="blockquote">
    612. 

  612.               <p>Returns an association list such that the <code class="literal">car</code> of each element
    613. 

  613. in <em class="replaceable"><code>alist</code></em> is a key in <em class="replaceable"><code>hash-table</code></em> and the corresponding
    614. 

  614. <code class="literal">cdr</code> of each element in <em class="replaceable"><code>alist</code></em> is the value associated to
    615. 

  615. the key in <em class="replaceable"><code>hash-table</code></em>. The order of the elements is unspecified.
    616. 

  616. </p>
    617. 

  617.               <p>The following should always produce a hash table with the same mappings
    618. 

  618. as a hash table <em class="replaceable"><code>h</code></em>:
    619. 

  619. </p>
    620. 

  620.               <pre class="screen">(alist-&gt;hash-table (hash-table-&gt;alist <em class="replaceable"><code>h</code></em>)
    621. 

  621.                         (hash-table-equivalence-function <em class="replaceable"><code>h</code></em>)
    622. 

  622.                         (hash-table-hash-function <em class="replaceable"><code>h</code></em>))
    623. 

  623. </pre>
    624. 

  624.             </blockquote>
    625. 

  625.           </div>
    626. 

  626.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873240896" class="indexterm"/> <code class="function">hash-table-copy</code> <em class="replaceable"><code>hash-table</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>hash-table</code></em></p>
    627. 

  627.           <div class="blockquote">
    628. 

  628.             <blockquote class="blockquote">
    629. 

  629.               <p>Returns a new hash table with the same equivalence predicate, hash
    630. 

  630. function and mappings as in <em class="replaceable"><code>hash-table</code></em>.
    631. 

  631. </p>
    632. 

  632.             </blockquote>
    633. 

  633.           </div>
    634. 

  634.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873236192" class="indexterm"/> <code class="function">hash-table-merge!</code> <em class="replaceable"><code>hash-table1</code></em> <em class="replaceable"><code>hash-table2</code></em> <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>hash-table</code></em></p>
    635. 

  635.           <div class="blockquote">
    636. 

  636.             <blockquote class="blockquote">
    637. 

  637.               <p>Adds all mappings in <em class="replaceable"><code>hash-table2</code></em> into <em class="replaceable"><code>hash-table1</code></em> and
    638. 

  638. returns the resulting hash table. This function may modify
    639. 

  639. <em class="replaceable"><code>hash-table1</code></em> destructively.
    640. 

  640. </p>
    641. 

  641.             </blockquote>
    642. 

  642.           </div>
    643. 

  643.         </section>
    644. 

  644.         <section class="sect3" title="Hash functions" epub:type="division" id="idm139667873230176">
    645. 

  645.           <div class="titlepage">
    646. 

  646.             <div>
    647. 

  647.               <div>
    648. 

  648.                 <h4 class="title">Hash functions</h4>
    649. 

  649.               </div>
    650. 

  650.             </div>
    651. 

  651.           </div>
    652. 

  652.           <p>The Kawa implementation always calls these hash functions with a single
    653. 

  653. parameter, and expects the result to be within the entire
    654. 

  654. (32-bit signed) <code class="literal">int</code> range, for compatibility with
    655. 

  655. standard <code class="literal">hashCode</code> methods.
    656. 

  656. </p>
    657. 

  657.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873227664" class="indexterm"/> <code class="function">hash</code> <em class="replaceable"><code>object</code></em> [ <em class="replaceable"><code>bound</code></em> ] <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>integer</code></em></p>
    658. 

  658.           <div class="blockquote">
    659. 

  659.             <blockquote class="blockquote">
    660. 

  660.               <p>Produces a hash value for object in the range from 0 (inclusive) tp to
    661. 

  661. <em class="replaceable"><code>bound</code></em> (exclusive).
    662. 

  662. </p>
    663. 

  663.               <p>If <em class="replaceable"><code>bound</code></em> is not given, the Kawa implementation returns a value within
    664. 

  664. the range <code class="literal">(- (expt 2 32))</code> (inclusive)
    665. 

  665. to <code class="literal">(- (expt 2 32) 1)</code> (inclusive).
    666. 

  666. It does this by calling the standard <code class="literal">hashCode</code> method,
    667. 

  667. and returning the result as is.
    668. 

  668. (If the <em class="replaceable"><code>object</code></em> is the Java <code class="literal">null</code> value, 0 is returned.)
    669. 

  669. This hash function is acceptable for <code class="literal">equal?</code>.
    670. 

  670. </p>
    671. 

  671.             </blockquote>
    672. 

  672.           </div>
    673. 

  673.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873218560" class="indexterm"/> <code class="function">string-hash</code> <em class="replaceable"><code>string</code></em> [ <em class="replaceable"><code>bound</code></em> ] <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>integer</code></em></p>
    674. 

  674.           <div class="blockquote">
    675. 

  675.             <blockquote class="blockquote">
    676. 

  676.               <p>The same as <code class="literal">hash</code>, except that the argument string must be a string.
    677. 

  677. (The Kawa implementation returns the same as the <code class="literal">hash</code> function.)
    678. 

  678. </p>
    679. 

  679.             </blockquote>
    680. 

  680.           </div>
    681. 

  681.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873212960" class="indexterm"/> <code class="function">string-ci-hash</code> <em class="replaceable"><code>string</code></em> [ <em class="replaceable"><code>bound</code></em> ] <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>integer</code></em></p>
    682. 

  682.           <div class="blockquote">
    683. 

  683.             <blockquote class="blockquote">
    684. 

  684.               <p>The same as <code class="literal">string-hash</code>, except that the case of characters in
    685. 

  685. string does not affect the hash value produced.
    686. 

  686. (The Kawa implementation returns the same the <code class="literal">hash</code> function
    687. 

  687. applied to the lower-cased <em class="replaceable"><code>string</code></em>.)
    688. 

  688. </p>
    689. 

  689.             </blockquote>
    690. 

  690.           </div>
    691. 

  691.           <p class="synopsis" kind="Procedure"><span class="kind">Procedure</span><span class="ignore">: </span><a id="idm139667873206896" class="indexterm"/> <code class="function">hash-by-identity</code> <em class="replaceable"><code>object</code></em> [ <em class="replaceable"><code>bound</code></em> ] <em class="replaceable"><code>→</code></em> <em class="replaceable"><code>integer</code></em></p>
    692. 

  692.           <div class="blockquote">
    693. 

  693.             <blockquote class="blockquote">
    694. 

  694.               <p>The same as <code class="literal">hash</code>, except that this function is only guaranteed
    695. 

  695. to be acceptable for <code class="literal">eq?</code>.
    696. 

  696. Kawa uses the <code class="literal">identityHashCode</code> method of <code class="literal">java.lang.System</code>.
    697. 

  697. </p>
    698. 

  698.             </blockquote>
    699. 

  699.           </div>
    700. 

  700.         </section>
    701. 

  701.       </section>
    702. 

  702.     </section>
    703. 

  703.     <footer>
    704. 

  704.       <div class="navfooter">
    705. 

  705.         <ul>
    706. 

  706.           <li>
    707. 

  707.             <b class="toc">
    708. 

  708.               <a href="Hash-tables.xhtml#idm139667873522768">R6RS hash tables</a>
    709. 

  709.             </b>
    710. 

  710.           </li>
    711. 

  711.           <li>
    712. 

  712.             <b class="toc">
    713. 

  713.               <a href="Hash-tables.xhtml#idm139667873378016">SRFI-69 hash tables</a>
    714. 

  714.             </b>
    715. 

  715.           </li>
    716. 

  716.         </ul>
    717. 

  717.         <p>
    718. 

  718.           Up: <a accesskey="u" href="Data-structures.xhtml">Data structures</a></p>
    719. 

  719.         <p>
    720. 

  720.         Previous: <a accesskey="p" href="Arrays.xhtml">Multi-dimensional Arrays</a></p>
    721. 

  721.       </div>
    722. 

  722.     </footer>
    723. 

  723.   </body>
    724. 

  724. </html>
    725. 

  725.