core/handbook/hashtables.facts

   1 USING: hashtables hashtables-internals help io-internals kernel
   2 kernel-internals namespaces queues ;
   3
   4 ARTICLE: "hashtables" "Hashtables"
   5 "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."
   6 $terpri
   7 "Hashtable words are in the " { $vocab-link "hashtables" } " vocabulary. Unsafe implementation words are in the " { $vocab-link "hashtables-internals" } " vocabulary."
   8 $terpri
   9 "Hashtables form a class of objects."
  10 { $subsection hashcode }
  11 { $subsection hashtable? }
  12 "You can create a new hashtable with an initial capacity."
  13 { $subsection <hashtable> }
  14 "If you don't care about initial capacity, a more elegant way to create a new hashtable is to write:"
  15 { $code "H{ } clone" }
  16 "There are some primitive operations on hashes, and many utilities."
  17 { $subsection "hashtables-lookup" }
  18 { $subsection "hashtables-mutation" }
  19 { $subsection "hashtables-combinators" }
  20 { $subsection "hashtables-utilities" }
  21 { $subsection "hashtables-internals" } ;
  22
  23 ARTICLE: "hashtables-lookup" "Looking up keys in hashtables"
  24 { $subsection hash }
  25 { $subsection hash* }
  26 { $subsection ?hash }
  27 { $subsection ?hash* }
  28 { $subsection hash-member? } ;
  29
  30 ARTICLE: "hashtables-mutation" "Storing keys in hashtables"
  31 { $subsection set-hash }
  32 { $subsection remove-hash }
  33 { $subsection clear-hash } ;
  34
  35 ARTICLE: "hashtables-combinators" "Hashtable combinators"
  36 "We have the standard functional programming idioms."
  37 { $subsection hash-each }
  38 { $subsection hash-all? }
  39 { $subsection hash-subset }
  40 "There are curried forms of the above."
  41 { $subsection hash-each-with }
  42 { $subsection hash-all-with? }
  43 { $subsection hash-subset-with }
  44 "Two oddball combinators."
  45 { $subsection cache }
  46 { $subsection map>hash } ;
  47
  48 ARTICLE: "hashtables-utilities" "Hashtable utilities"
  49 "Set-theoretic operations exploit the expected constant lookup time of a hashtable."
  50 { $subsection hash-intersect }
  51 { $subsection hash-diff }
  52 { $subsection hash-union }
  53 { $subsection hash-update }
  54 { $subsection remove-all }
  55 "A combinator used to implement notions of nested scope. This includes various fundamental abstractions like variables, vocabulary search and cascading styles."
  56 { $subsection hash-stack } ;
  57
  58 ARTICLE: "hashtables-internals" "Hashtable implementation details"
  59 "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."
  60 { $terpri }
  61 "There are two special objects: the " { $link ((tombstone)) } " marker and the " { $link ((empty)) } " marker. Neither of these markers can be used as hashtable keys."
  62 { $terpri }
  63 "The " { $link hash-count } " slot is the number of entries including deleted entries, and " { $link hash-deleted } " is the number of deleted entries."
  64 { $subsection <hash-array> }
  65 { $subsection nth-pair }
  66 { $subsection set-nth-pair }
  67 { $subsection each-pair }
  68 { $subsection all-pairs? } ;
  69
  70 ARTICLE: "namespaces" "Variables and namespaces"
  71 "A variable is an entry in a hashtable of bindings, with the hashtable being implicit rather than passed on the stack. These hashtables are termed " { $emphasis "namespaces" } ". Nesting of scopes is implemented with a search order on namespaces, defined by a " { $emphasis "namestack" } ". Since namespaces are just hashtables, any object can be used as a variable, however by convention, variables are keyed by symbols (see " { $link "symbols" } ")."
  72 $terpri
  73 "The " { $snippet "get" } " and " { $snippet "set" } " words read and write variable values. The " { $snippet "get" } " word searches up the chain of nested namespaces, while " { $snippet "set" } " always sets variable values in the current namespace only. Namespaces are dynamically scoped; when a quotation is called from a nested scope, any words called by the quotation also execute in that scope."
  74 { $subsection get }
  75 { $subsection set }
  76 "Various utility words abstract away common variable access patterns:"
  77 { $subsection "namespaces-change" }
  78 { $subsection "namespaces-combinators" }
  79 { $subsection "namespaces-utilities" }
  80 "A useful facility for constructing sequences by holding an accumulator sequence in a variable:"
  81 { $subsection "namespaces-make" }
  82 "Implementation details your code probably does not care about:"
  83 { $subsection "namespaces-internals" } ;
  84
  85 ARTICLE: "namespaces-combinators" "Namespace combinators"
  86 { $subsection make-hash }
  87 { $subsection with-scope }
  88 { $subsection bind } ;
  89
  90 ARTICLE: "namespaces-change" "Ways to change variable values"
  91 { $subsection on }
  92 { $subsection off }
  93 { $subsection inc }
  94 { $subsection dec }
  95 { $subsection change } ;
  96
  97 ARTICLE: "namespaces-utilities" "Namespace utilities"
  98 { $subsection namespace }
  99 { $subsection nest }
 100 { $subsection global }
 101 { $subsection set-global } ;
 102
 103 ARTICLE: "namespaces-make" "Constructing sequences"
 104 "There is a lexicon of words for constructing sequences without passing the partial sequence being built on the stack. This reduces stack noise."
 105 { $subsection make }
 106 { $subsection , }
 107 { $subsection % }
 108 { $subsection # } ;
 109
 110 ARTICLE: "namespaces-internals" "Namespace implementation details"
 111 "The namestack holds namespaces."
 112 { $subsection namestack }
 113 { $subsection set-namestack }
 114 "A pair of words push and pop namespaces on the namestack."
 115 { $subsection >n }
 116 { $subsection n> } ;