core/hashtables/hashtables-docs.factor

   1 USING: hashtables.private help.markup help.syntax
   2 kernel prettyprint generic sequences sequences.private
   3 namespaces assocs ;
   4 IN: hashtables
   5
   6 ARTICLE: "hashtables.private" "Hashtable implementation details"
   7 "This hashtable implementation uses only one auxilliary array in addition to the hashtable tuple itself. The array stores keys in even slots and values in odd slots. Values are looked up with a hashing strategy that uses linear probing to resolve collisions."
   8 $nl
   9 "There are two special objects: the " { $link ((tombstone)) } " marker and the " { $link ((empty)) } " marker. Neither of these markers can be used as hashtable keys."
  10 $nl
  11 "The " { $snippet "count" } " slot is the number of entries including deleted entries, and " { $snippet "deleted" } " is the number of deleted entries."
  12 { $subsection <hash-array> }
  13 { $subsection set-nth-pair }
  14 "If a hashtable's keys are mutated, or if hashing algorithms change, hashtables can be rehashed:"
  15 { $subsection rehash } ;
  16
  17 ARTICLE: "hashtables" "Hashtables"
  18 "A hashtable provides efficient (expected constant time) lookup and storage of key/value pairs. Keys are compared for equality, and a hashing function is used to reduce the number of comparisons made. The literal syntax is covered in " { $link "syntax-hashtables" } "."
  19 $nl
  20 "Hashtable words are in the " { $vocab-link "hashtables" } " vocabulary. Unsafe implementation words are in the " { $vocab-link "hashtables.private" } " vocabulary."
  21 $nl
  22 "Hashtables implement the " { $link "assocs-protocol" } "."
  23 $nl
  24 "Hashtables are a class of objects."
  25 { $subsection hashtable }
  26 { $subsection hashtable? }
  27 "You can create a new hashtable with an initial capacity."
  28 { $subsection <hashtable> }
  29 "If you don't care about initial capacity, a more elegant way to create a new hashtable is to write:"
  30 { $code "H{ } clone" }
  31 "To convert an assoc to a hashtable:"
  32 { $subsection >hashtable }
  33 "Further topics:"
  34 { $subsection "hashtables.keys" }
  35 { $subsection "hashtables.utilities" }
  36 { $subsection "hashtables.private" } ;
  37
  38 ARTICLE: "hashtables.keys" "Hashtable keys"
  39 "Hashtables rely on the " { $link hashcode } " word to rapidly locate values associated with keys. The objects used as keys in a hashtable must obey certain restrictions."
  40 $nl
  41 "The " { $link hashcode } " of a key is a function of the its slot values, and if the hashcode changes then the hashtable will be left in an inconsistent state. The easiest way to avoid this problem is to never mutate objects used as hashtable keys."
  42 $nl
  43 "In certain advanced applications, this cannot be avoided and the best design involves mutating hashtable keys. In this case, a custom " { $link hashcode* } " method must be defined which only depends on immutable slots."
  44 $nl
  45 "In addition, the " { $link equal? } " and " { $link hashcode* } " methods must be congruent, and if one is defined the other should be defined also. This is documented in detail in the documentation for these respective words." ;
  46
  47 ARTICLE: "hashtables.utilities" "Hashtable utilities"
  48 "Utility words to create a new hashtable from a single key/value pair:"
  49 { $subsection associate }
  50 { $subsection ?set-at } ;
  51
  52 ABOUT: "hashtables"
  53
  54 HELP: hashtable
  55 { $description "The class of hashtables. See " { $link "syntax-hashtables" } " for syntax and " { $link "hashtables" } " for general information." } ;
  56
  57 HELP: hash@
  58 { $values { "key" "a key" } { "array" "the underlying array of a hashtable" } { "i" "the index to begin hashtable search" } }
  59 { $description "Computes the index to begin searching from the hashcode of the key. Always outputs an even value since keys are stored at even indices of the underlying array." } ;
  60
  61 HELP: probe
  62 { $values { "array" "the underlying array of a hashtable" } { "i" "a search index" } }
  63 { $description "Outputs the next hashtable search index." } ;
  64
  65 HELP: key@
  66 { $values { "key" "a key" } { "hash" hashtable } { "array" "the underlying array of the hashtable" } { "n" "the index of the key" } { "?" "a boolean indicating whether the key was present" } }
  67 { $description "Searches the hashtable for the key using a linear probing strategy. Searches stop if either the key or an " { $link ((empty)) } " sentinel is found. Searches skip the " { $link ((tombstone)) } " sentinel." } ;
  68
  69 { key@ new-key@ } related-words
  70
  71 HELP: new-key@
  72 { $values { "key" "a key" } { "hash" hashtable } { "array" "the underlying array of the hashtable" } { "n" "the index where the key would be stored" } { "empty?" "a boolean indicating whether the location is currently empty" } }
  73 { $description "Searches the hashtable for the key using a linear probing strategy. If the key is not present in the hashtable, outputs the index where it should be stored." } ;
  74
  75 HELP: set-nth-pair
  76 { $values { "value" "the second element of the pair" } { "key" "the first element of the pair" } { "seq" "a sequence" } { "n" "an index in the sequence" } }
  77 { $description "Stores a pair of values into the elements with index " { $snippet "n" } " and " { $snippet "n+1" } ", respectively." }
  78 { $warning "This word is in the " { $vocab-link "hashtables.private" } " vocabulary because it does not perform bounds checks." }
  79 { $side-effects "seq" } ;
  80
  81 HELP: reset-hash
  82 { $values { "n" "a positive integer specifying hashtable capacity" } { "hash" hashtable } }
  83 { $description "Resets the underlying array of the hashtable to a new array with the given capacity. Removes all entries from the hashtable." }
  84 { $side-effects "hash" } ;
  85
  86 HELP: hash-count+
  87 { $values { "hash" hashtable } }
  88 { $description "Called to increment the hashtable size when a new entry is added with " { $link set-at } }
  89 { $side-effects "hash" } ;
  90
  91 HELP: hash-deleted+
  92 { $values { "hash" hashtable } }
  93 { $description "Called to increment the deleted entry counter when an entry is removed with " { $link delete-at } }
  94 { $side-effects "hash" } ;
  95
  96 HELP: grow-hash
  97 { $values { "hash" hashtable } }
  98 { $description "Enlarges the capacity of a hashtable. User code does not need to call this word directly." }
  99 { $side-effects "hash" } ;
 100
 101 HELP: ?grow-hash
 102 { $values { "hash" hashtable } }
 103 { $description "Enlarges the capacity of a hashtable if it is almost full. User code does not need to call this word directly." }
 104 { $side-effects "hash" } ;
 105
 106 HELP: <hashtable>
 107 { $values { "n" "a positive integer specifying hashtable capacity" } { "hash" "a new hashtable" } }
 108 { $description "Create a new hashtable capable of storing " { $snippet "n" } " key/value pairs before growing." } ;
 109
 110 HELP: associate
 111 { $values { "value" "a value" } { "key" "a key" } { "hash" "a new " { $link hashtable } } }
 112 { $description "Create a new hashtable holding one key/value pair." } ;
 113
 114 HELP: ?set-at
 115 { $values
 116      { "value" object } { "key" object } { "assoc/f" "an assoc or " { $link f } }
 117      { "assoc" assoc } }
 118 { $description "If the third input is an assoc, stores the key/value pair into that assoc, or else creates a new hashtable with the key/value pair as its only entry." } ;
 119
 120 HELP: >hashtable
 121 { $values { "assoc" "an assoc" } { "hashtable" "a hashtable" } }
 122 { $description "Constructs a hashtable from any assoc." } ;
 123
 124 HELP: rehash
 125 { $values { "hash" hashtable } }
 126 { $description "Rebuild the hashtable. This word should be called if the hashcodes of the hashtable's keys have changed, or if the hashing algorithms themselves have changed, neither of which should occur during normal operation." } ;