perl-Algorithm-MinPerfHashTwoLevel - construct a "two level" minimal perfect hash

Property Value
Distribution ALT Linux Sisyphus
Repository Autoimports i586
Package filename perl-Algorithm-MinPerfHashTwoLevel-0.10-alt1.i586.rpm
Package name perl-Algorithm-MinPerfHashTwoLevel
Package version 0.10
Package release alt1
Package architecture i586
Package type rpm
Category Development/Perl
Homepage -
License -
Maintainer -
Download size 67.64 KB
Installed size 67.64 KB
This module implements an algorithm to construct (relatively efficiently) a
minimal perfect hash using the "two level" algorithm. A perfect hash is one
which has no collisions for any keys, a minimal perfect hash has exactly the
same number of buckets as it has keys. The "two level" algorithm involves
computing two hash values for each key. The first is used as an initial lookup
into the bucket array to find a mask value which is used to modify the second
hash value to determine the actual bucket to read from. This module computes
the appropriate mask values.
In this implementation only one 64 bit hash value is computed, but the high
and low 32 bits are used as if there were two hash values. The hash function
used is stadtxhash. (The full 64 bit hash is called h0, the high 32 bits are
called h1, and the low 32 bits are called h2.)
Computing the hash and mask is done in C (via XS).
The process for looking up a value in a two level hash with n buckets is
as follows:
0. compute the h0 for the key. (h1 = h0 >> 32; h2 = h0 & 0xFFFFFFFF;)
1. compute idx = h1 % n;
2. find the xor_val for bucket[idx]
3. if the xor_val is zero we are done, the key is not in the hash
4. compute idx
if variant == 0 or (int)xor_val > 0
idx = (h2 ^ xor_val) % n;
idx = -xor_val-1
5. compare the key data associated with bucket[idx] with the key provided
6. if they match return the desired value.
This module performs the task of computing the xor_val for each bucket.
*NOTE* in Perl a given string may have differing binary representations
if it is encoded as utf8 or not. This module uses the same conventions
as Perl itself, which is that keys are stored in their minimal form when
possible, and are only stored in their unicode (utf8) form when they
cannot be downgraded to latin-1. This ensures that the unicode and latin-1
representations of a given string are treated as the same key. This module
deals with this by "normalizing" the keys and values into latin-1, but


Package Version Architecture Repository
perl-Algorithm-MinPerfHashTwoLevel-0.10-alt1.x86_64.rpm 0.10 x86_64 Autoimports
perl-Algorithm-MinPerfHashTwoLevel - - -


Name Value
/usr/lib/perl5 - - - - - - - - -
perl( -
perl( -
rpmlib(PayloadIsLzma) -
rpmlib(SetVersions) -
rtld(GNU_HASH) -


Name Value
perl(Algorithm/ = 0.100
perl(Tie/Hash/MinPerfHashTwoLevel/ = 0.100
perl-Algorithm-MinPerfHashTwoLevel = 0.10-alt1


Type URL
Binary Package perl-Algorithm-MinPerfHashTwoLevel-0.10-alt1.i586.rpm
Source Package perl-Algorithm-MinPerfHashTwoLevel-0.10-alt1.src.rpm

Install Howto

  1. Add the following line to /etc/apt/sources.list:
    rpm [Sisyphus] i586 autoimports
    rpm [Sisyphus] noarch autoimports
  2. Update the package index:
    # sudo apt-get update
  3. Install perl-Algorithm-MinPerfHashTwoLevel rpm package:
    # sudo apt-get install perl-Algorithm-MinPerfHashTwoLevel



See Also

Package Description
perl-Algorithm-NCS-0.04-alt1.1.i586.rpm Fast Perl extension for sequence alignment
perl-Algorithm-PageRank-XS-0.04-alt4.1.i586.rpm A Fast PageRank implementation
perl-Algorithm-Permute-0.16-alt2.1.i586.rpm Handy and fast permutation with object oriented interface
perl-Algorithm-RectanglesContainingDot_XS-0.02-alt4.1.i586.rpm perl module Algorithm-RectanglesContainingDot_XS
perl-Algorithm-SISort-0.14-alt4.1.i586.rpm Select And Insert sorting algorithm
perl-Algorithm-SVM-0.13-alt4.1.i586.rpm Perl bindings for the libsvm Support Vector Machine library
perl-Algorithm-Statistic-0.04-alt3.1.i586.rpm different statistical algorithms library
perl-Algorithm-StringHash-FromCSharp35-XS-0.04-alt4.1.i586.rpm C#'s string Hashing Algorithm in V3.5
perl-Algorithm-TrunkClassifier-1.0.1-alt4.1.i586.rpm Implementation of the Decision Trunk Classifier algorithm
perl-Alien-Editline-0.08-alt1.1.i586.rpm Build and make available Editline (libedit)
perl-Alien-FFCall-0.03-alt1.1.i586.rpm Build and install libffcall
perl-Alien-FFI-0.24-alt1.i586.rpm Build and make available libffi
perl-Alien-FreeImage-1.001-alt2.i586.rpm Building freeimage library L<>
perl-Alien-Gimp-0.07-alt3.i586.rpm Alien::Gimp - Encapsulate install info for GIMP
perl-Alien-HIDAPI-0.08-alt1.1.i586.rpm Perl distribution for HIDAPI