core/hashtables/hashtables-docs.factor

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