HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Information on Tavori and Dreizin ranged hash function?

Submitted by: @import:stackexchange-cs··
0
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

Context

StackExchange Computer Science Q#66931, answer score: 2

Revisions (0)

No revisions yet.