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 { $subsections
  13     <hash-array>
  14     set-nth-pair
  15 }
  16 "If a hashtable's keys are mutated, or if hashing algorithms change, hashtables can be rehashed:"
  17 { $subsections rehash } ;
  18
  19 ARTICLE: "hashtables" "Hashtables"
  20 "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" } "."
  21 $nl
  22 "Words for constructing hashtables are in the " { $vocab-link "hashtables" } " vocabulary. Hashtables implement the " { $link "assocs-protocol" } ", and all " { $link "assocs" } " can be used on them; there are no hashtable-specific words to access and modify keys, because associative mapping operations are generic and work with all associative mappings."
  23 $nl
  24 "Hashtables are a class of objects."
  25 { $subsections
  26     hashtable
  27     hashtable?
  28 }
  29 "You can create a new hashtable with an initial capacity."
  30 { $subsections <hashtable> }
  31 "If you don't care about initial capacity, a more elegant way to create a new hashtable is to write:"
  32 { $code "H{ } clone" }
  33 "To convert an assoc to a hashtable:"
  34 { $subsections >hashtable }
  35 "Further topics:"
  36 { $subsections
  37     "hashtables.keys"
  38     "hashtables.utilities"
  39     "hashtables.private"
  40 } ;
  41
  42 ARTICLE: "hashtables.keys" "Hashtable keys"
  43 "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."
  44 $nl
  45 "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."
  46 $nl
  47 "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."
  48 $nl
  49 "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."
  50 { $subsections hashcode hashcode* identity-hashcode } ;
  51
  52 ARTICLE: "hashtables.utilities" "Hashtable utilities"
  53 "Utility words to create a new hashtable from a single key/value pair:"
  54 { $subsections
  55     associate
  56     ?set-at
  57 } ;
  58
  59 ABOUT: "hashtables"
  60
  61 HELP: hashtable
  62 { $description "The class of hashtables. See " { $link "syntax-hashtables" } " for syntax and " { $link "hashtables" } " for general information." } ;
  63
  64 HELP: hash@
  65 { $values { "key" "a key" } { "array" "the underlying array of a hashtable" } { "i" "the index to begin hashtable search" } }
  66 { $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." } ;
  67
  68 HELP: probe
  69 { $values { "array" "the underlying array of a hashtable" } { "i" "a search index" } }
  70 { $description "Outputs the next hashtable search index." } ;
  71
  72 HELP: key@
  73 { $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" } }
  74 { $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." } ;
  75
  76 { key@ new-key@ } related-words
  77
  78 HELP: new-key@
  79 { $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" } }
  80 { $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." } ;
  81
  82 HELP: set-nth-pair
  83 { $values { "value" "the second element of the pair" } { "key" "the first element of the pair" } { "seq" "a sequence" } { "n" "an index in the sequence" } }
  84 { $description "Stores a pair of values into the elements with index " { $snippet "n" } " and " { $snippet "n+1" } ", respectively." }
  85 { $warning "This word is in the " { $vocab-link "hashtables.private" } " vocabulary because it does not perform bounds checks." }
  86 { $side-effects "seq" } ;
  87
  88 HELP: reset-hash
  89 { $values { "n" "a positive integer specifying hashtable capacity" } { "hash" hashtable } }
  90 { $description "Resets the underlying array of the hashtable to a new array with the given capacity. Removes all entries from the hashtable." }
  91 { $side-effects "hash" } ;
  92
  93 HELP: hash-count+
  94 { $values { "hash" hashtable } }
  95 { $description "Called to increment the hashtable size when a new entry is added with " { $link set-at } }
  96 { $side-effects "hash" } ;
  97
  98 HELP: hash-deleted+
  99 { $values { "hash" hashtable } }
 100 { $description "Called to increment the deleted entry counter when an entry is removed with " { $link delete-at } }
 101 { $side-effects "hash" } ;
 102
 103 HELP: grow-hash
 104 { $values { "hash" hashtable } }
 105 { $description "Enlarges the capacity of a hashtable. User code does not need to call this word directly." }
 106 { $side-effects "hash" } ;
 107
 108 HELP: ?grow-hash
 109 { $values { "hash" hashtable } }
 110 { $description "Enlarges the capacity of a hashtable if it is almost full. User code does not need to call this word directly." }
 111 { $side-effects "hash" } ;
 112
 113 HELP: <hashtable>
 114 { $values { "n" "a positive integer specifying hashtable capacity" } { "hash" "a new hashtable" } }
 115 { $description "Create a new hashtable capable of storing " { $snippet "n" } " key/value pairs before growing." } ;
 116
 117 HELP: associate
 118 { $values { "value" "a value" } { "key" "a key" } { "hash" "a new " { $link hashtable } } }
 119 { $description "Create a new hashtable holding one key/value pair." } ;
 120
 121 HELP: ?set-at
 122 { $values
 123      { "value" object } { "key" object } { "assoc/f" "an assoc or " { $link f } }
 124      { "assoc" assoc } }
 125 { $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." } ;
 126
 127 HELP: >hashtable
 128 { $values { "assoc" assoc } { "hashtable" hashtable } }
 129 { $description "Constructs a hashtable from any assoc." } ;
 130
 131 HELP: rehash
 132 { $values { "hash" hashtable } }
 133 { $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." } ;