3
$\begingroup$

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<size_t>:::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.
$\endgroup$
1
$\begingroup$

I read that passage as saying that Tavori and Dreizin introduced the terminology/concept of a "range-hashing function". Presumably, that's a name they use for a hash function with some special properties. In other words, I read that as implying not that Tavori and Dreizen introduced a specific hash function, but that they talk about a category of hash functions and gave it a name.

I don't know if that is what the authors actually meant; that's just how i would interpret it.

I tried searching on Google Scholar for these names and found nothing that seemed relevant. A quick search turns up a reference to Ami Tavori at IBM (a past student of Prof. Meir Feder, working on computer science), but I don't know if that's who this is referring to.

$\endgroup$
1
  • $\begingroup$ That makes sense. Thank you for the response. $\endgroup$ – moarCoffee Dec 4 '16 at 23:40
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.