BPHT - 位打包跳棋哈希表

BPHT 是一个针对快速访问 32 位整数值而设计的专用哈希表，它使用位打包和除法运算。它使用跳棋散列算法 [1] 来解决冲突，并将跳位打包到数据数组中，以避免强制缓存未命中。为了在不显式保存键的情况下保持可调整大小，它使用除法运算 [2] 来恢复哈希值。这种架构允许以常量额外内存进行高效的调整大小操作，但施加了一些限制

• 存储的值必须是 u32
• 哈希值（键）必须是 u32
• 哈希值（键）应该在 0 和 2^{32} - 1 之间均匀分布
• 哈希表的大小（u）必须是 2 的幂

请注意，这 不是 一个通用哈希表。它要求你预先计算哈希值，并且至少有一个要插入的条目数量的粗略估计。

使用方法

BPHT 需要显式传递键值对给表。有两种使用 BPHT 的方法，哈希表模式和计数器模式。

对于哈希表模式，使用 insert(key, value) 方法将条目放入表中，使用 get.(key) 方法检索给定键插入的所有值。在计数模式下，您不需要传递值。使用 increment_count(key) 和 get_count(key) 方法

use bpht;


fn test_hash_table_mode() -> Result<(), &'static str>{
    let h = 8;  // Hopscotch neighborhood size
    let u = 2_u64.pow(25) as usize;  // Initial hash table address space size
    let allow_resize = true;  // Allow the table to perform resize operations
    let mut ht = bpht::BPHT::new(h, u, allow_resize)?;
    
    // these should be hash values
    let keys: Vec<u32> = vec![681141441, 681141441, 4274363488, 2008780323];
    let values =  vec![42, 23, 47, 11];
    for  (key, value) in  keys.iter().zip(values.iter()){
        ht.insert(*key, *value)?;
    }

    assert_eq!(ht.get(681141441), Some(vec![42, 23]));
    assert_eq!(ht.get(4274363488), Some(vec![47]));
    assert_eq!(ht.get(17), None);
    Ok(())
}


fn test_counting_mode() -> Result<(), &'static str>{
    let h = 8;  // Hopscotch neighborhood size
    let u = 2_u64.pow(25) as usize;  // Initial hash table address space size
    let allow_resize = true;  // Allow the table to perform resize operations
    let mut ht = bpht::BPHT::new(h, u, allow_resize)?;
    
    // these should be hash values
    let keys: Vec<u32> = vec![681141441, 681141441, 4274363488, 2008780323];
    // Count the number of times keys are encountered
    for  key in keys {
        ht.increment_count(key)?;
    }

    assert_eq!(ht.get_count(681141441), Some(2));
    assert_eq!(ht.get_count(4274363488), Some(1));
    assert_eq!(ht.get_count(17), None);
    Ok(())
}


fn main() -> Result<(), &'static str>{
    test_hash_table_mode()?;
    test_counting_mode()?;
    Ok(())
}

实现细节

除法运算

密钥被分成地址（log_2(u)高位）和余数（也称为指纹；32 - log_2(u)低位）。

Example: u = 2^{22}
=> 22           address bits (a)
=> 32 - 22 = 10 remainder bits (r)

Key as
Bit vector: 0b_00000000_00000000_11111100_00101010
               |-----------22---------||---10----|
Quotiented: 0b_aaaaaaaa_aaaaaaaa_aaaaaarr_rrrrrrrr

Address:   0b_111111
Remainder: 0b_101010

这种设置被选择，因为它可以通过移动一个余数位到地址位来实现高效的调整大小操作。然而，请注意，输入小的密钥很容易导致跳棋街区溢出。

位打包

BPHT的底层数组中的每个条目都包含以下信息，这些信息被打包到64位中

|        32 bits value           | up to (32 - H) remainder bits | H hop bits |
|vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv|rrrrrrr.............rrrrrrrrrrr|hhh......hhh|

由于这种设计，哈希表的大小引入了可能的跳位数的最大数量。

参考文献

[1] Herlihy等：http://people.csail.mit.edu/shanir/publications/disc2008_submission_98.pdf

[2] Knuth，Donald E. 计算机编程艺术：排序与搜索。第3卷。Pearson Education，1997。