patternMinor
Information on Tavori and Dreizin ranged hash function?
Viewed 0 times
tavorirangedfunctionhashdreizinandinformation
Problem
While doing some digging around in the GNU implementation of the C++ standard library I came across a section in
bits/hashtabe.h that refers to a hash function "in the terminology of Tavori and Dreizin" (see below). I have tried without success to find information on these people, in the hopes of learning about their hash function -- everything points to online versions of the file that the following extract is from. Can anyone give me some information on this?* @tparam _H1 The hash function. A unary function object with
* argument type _Key and result type size_t. Return values should
* be distributed over the entire range [0, numeric_limits:::max()].
*
* @tparam _H2 The range-hashing function (in the terminology of
* Tavori and Dreizin). A binary function object whose argument
* types and result type are all size_t. Given arguments r and N,
* the return value is in the range [0, N).
*
* @tparam _Hash The ranged hash function (Tavori and Dreizin). A
* binary function whose argument types are _Key and size_t and
* whose result type is size_t. Given arguments k and N, the
* return value is in the range [0, N). Default: hash(k, N) =
* h2(h1(k), N). If _Hash is anything other than the default, _H1
* and _H2 are ignored.Solution
Ami Tavory, Vladimir Dreizin (IBM), and Benjamin Kosnik (Red Hat) authored the "Policy-Based Data Structures" library. Ideas developed there were later used in the GNU implementation of the C++ standard library.
Link-only answers are typically discouraged, but let me post the link here anyway because it is not discoverable with Google in a simple way:
https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/
In particular, range hashing approach is described here:
https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/hash_based_containers.html
Link-only answers are typically discouraged, but let me post the link here anyway because it is not discoverable with Google in a simple way:
https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/
In particular, range hashing approach is described here:
https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/hash_based_containers.html
Context
StackExchange Computer Science Q#66931, answer score: 2
Revisions (0)
No revisions yet.