core/hashtables/hashtables-docs.factor

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