Let U be a domain (e.g., the integers, or the strings of 3 characters). A hash-table algorithm needs to map elements of U "uniformly" into the range [0,..., m - 1] (where m is a non-negative integral value, and is, in general, time varying). I.e., the algorithm needs a ranged-hash function

f : U × Z₊ → Z₊

such that for any u in U ,

0 ≤ f(u, m) ≤ m - 1

From the above, it is obvious that given g and h, f can always be composed (however the converse is not true). The standard's hash-based containers allow specifying a hash function, and use a hard-wired range-hashing function; the ranged-hash function is implicitly composed.

The above describes the case where a key is to be mapped into a single position within a hash table, e.g., in a collision-chaining table. In other cases, a key is to be mapped into a sequence of positions within a table, e.g., in a probing table. Similar terms apply in this case: the table requires a ranged probe function, mapping a key into a sequence of positions withing the table. This is typically achieved by composing a hash function mapping the key into a non-negative integral type, a probe function transforming the hash value into a sequence of hash values, and a range-hashing function transforming the sequence of hash values into a sequence of positions.

g(r, m) = ⌈ u/v ( a r mod v ) ⌉

and

g(r, m) = ⌈ u/v ( r² mod v ) ⌉

respectively, for some positive integrals u and v (typically powers of 2), and some a. Each of these range-hashing functions works best for some different setting.

The division method (see above) is a very common choice. However, even this single method can be implemented in two very different ways. It is possible to implement using the low level % (modulo) operation (for any m), or the low level & (bit-mask) operation (for the case where m is a power of 2), i.e.,

and

respectively.

The % (modulo) implementation has the advantage that for m a prime far from a power of 2, g(r, m) is affected by all the bits of r (minimizing the chance of collision). It has the disadvantage of using the costly modulo operation. This method is hard-wired into SGI's implementation .

The & (bit-mask) implementation has the advantage of relying on the fast bit-wise and operation. It has the disadvantage that for g(r, m) is affected only by the low order bits of r. This method is hard-wired into Dinkumware's implementation.

where a is some non-negative integral value. This is the standard string-hashing function used in SGI's implementation (with a = 5). Its advantage is that it takes into account all of the characters of the string.

Now assume that s is the string representation of a of a long DNA sequence (and so S = {'A', 'C', 'G', 'T'}). In this case, scanning the entire string might be prohibitively expensive. A possible alternative might be to use only the first k characters of the string, where

|S|^k ≥ m ,

i.e., using the hash function

requiring scanning over only

k = log₄( m )

characters.

Other more elaborate hash-functions might scan k characters starting at a random position (determined at each resize), or scanning k random positions (determined at each resize), i.e., using

f₃(s, m) = ∑ _{i = r}0^{r₀ + k - 1} s_i aⁱ mod m ,

or

f₄(s, m) = ∑ _{i = 0}^{k - 1} s_ri a^r_i mod m ,

respectively, for r₀,..., r_k-1 each in the (inclusive) range [0,...,t-1].

It should be noted that the above functions cannot be decomposed as per a ranged hash composed of hash and range hashing.

Denote the probability that a probe sequence of length k appears in bin i by p_i, the length of the probe sequence of bin i by l_i, and assume uniform distribution. Then

P(l₁ ≥ k) =

P(l₁ ≥ α ( 1 + k / α - 1) ≤ (a)

e ^ ( - ( α ( k / α - 1 )² ) /2)

P ( ∑ _{i = 1}^m I(l_i ≥ k) ≥ 1 ) =

P ( ∑ _{i = 1}^m I ( l_i ≥ k ) ≥ m p₁ ( 1 + 1 / (m p₁) - 1 ) ) ≤ (a)

e ^ ( ( - m p₁ ( 1 / (m p₁) - 1 ) ² ) / 2 ) ,

node_update (an instantiation of Node_Update) must define metadata_type as the type of metadata it requires. For order statistics, e.g., metadata_type might be size_t. The tree defines within each node a metadata_type object.

node_update must also define the following method for restoring node invariants:

	      void 
	      operator()(node_iterator nd_it, const_node_iterator end_nd_it)
	    

In this method, nd_it is a node_iterator corresponding to a node whose A) all descendants have valid invariants, and B) its own invariants might be violated; end_nd_it is a const_node_iterator corresponding to a just-after-leaf node. This method should correct the node invariants of the node pointed to by nd_it. For example, say node x in the graphic below label A has an invalid invariant, but its' children, y and z have valid invariants. After the invocation, all three nodes should have valid invariants, as in label B.

To complete the description of the scheme, three questions need to be answered:

The first two questions are answered by the fact that node_update (an instantiation of Node_Update) is a public base class of the tree. Consequently:

A null policy class, null_node_update solves both these problems. The tree detects that node invariants are irrelevant, and defines all accordingly.