帮酷LOGO
  • 显示原文与译文双语对照的内容
Bloom-filter based minimal perfect hash function library

  • 源代码名称:BBHash
  • 源代码网址:http://www.github.com/rizkg/BBHash
  • BBHash源代码文档
  • BBHash源代码下载
  • Git URL:
    git://www.github.com/rizkg/BBHash.git
  • Git Clone代码到本地:
    git clone http://www.github.com/rizkg/BBHash
  • Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/rizkg/BBHash
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
  • Build Status

    BBHash

    BBHash是构建最小完美哈希函数的简单库。 它被设计用来处理大规模数据集。 函数比它的他最先进的库要大一些,但是需要大约 3位/元素( 与 emphf lib的2.62位/元素相比),但构造不需要额外的内存。

    它很容易包含在其他项目的( 只包含一个. h 文件) 中,并且没有依赖关系。

    引用

    arXiv上提供了预印本: https://arxiv.org/abs/1702.03154

    用法

    下面是一个演示如何在 std::vector <u_int64_t> 中生成和查询带有输入键的mphf的简单示例。 输入键也可以从磁盘文件或者某些用户定义的迭代器中读取。

     #include"BooPHF.h"
    //tells bbhash to use included hash function working on u_int64_t input keys :
     typedef boomphf::SingleHashFunctor<u_int64_t> hasher_t;
     typedef boomphf::mphf <u_int64_t, hasher_t> boophf_t;
    std::vector<u_int64_t> input_keys;
    //
    ... fill the input_keys vector
    //build the mphf 
    boophf_t * bphf = new boomphf::mphf<u_int64_t,hasher_t>(input_keys.size(),input_keys,nthreads);
    //query the mphf :
     uint64_t idx = bphf->lookup(input_keys[0]);
    用户定义类型支持

    主分支只适用于普通的旧数据类型( POD ) 。 若要使用其他类型,请使用"AllTypes"分支( 它运行速度缓慢) 。 AllTypes分支包含一个带字符串的示例代码。 "internal_hash"支持使用不支持复制或者赋值运算符的类型,而无需在 I/O 操作中使用 128位/键。 因此,如果键是 64位整数,"internal_hash"将执行2 次i/o 操作。 但是如果你的键超过 128位,那么"internal_hash"分支将比主分支快。

    如何运行测试

    文件 example.cpp, 中提供了一个示例用法,并运行: ( params是 nb_elements nb_threads )

    make
    ./example 100000000 1

    File包含更多选项,使用。/bootest来检查散列函数的正确性,并使用-bench来测试查询性能。

    下面是一个示例输出:

    $./Bootest 100000000 8 -check -bench
    key file generated 
    Construct a BooPHF with 100000000 elements 
    [Building BooPHF] 100 % elapsed: 0 min 31 sec remaining: 0 min 0 sec
    BooPHF constructed perfect hash for 100000000 keys in 30.95s
    Bitarray 305808384 bits (99.49 %) (array + ranks )
    final hash 1557024 bits (0.51 %) (nb in final hash 4634)
    boophf bits/elem : 3.073654
     --- boophf working correctly --- 
    bench lookups sample size 9999872 
    BBhash bench lookups average 258.06 ns +- stddev 5.55 % (fingerprint 5000111281850410) 
    作者

    ,Rizk,Antoine Limasset,Rayan Chikhi

    guillaume.rizk@algorizk.com




    Copyright © 2011 HelpLib All rights reserved.    知识分享协议 京ICP备05059198号-3  |  如果智培  |  酷兔英语