Parallel-HashMap项目中自定义哈希器的构造方法详解

理解Parallel-HashMap的自定义哈希器

在Parallel-HashMap项目中，自定义哈希器是实现高效哈希表的关键组件。与标准库中的unordered_map不同，Parallel-HashMap提供了更灵活的自定义哈希器构造方式，允许开发者在初始化时传递参数给哈希器。

自定义哈希器的基本结构

一个完整的自定义哈希器通常包含两个主要部分：哈希函数(KeyHasher)和键比较函数(KeyEqualTo)。这两个组件共同决定了哈希表如何处理键的存储和查找。

哈希函数(KeyHasher)的实现

哈希函数的核心是重载operator()，它接收键类型作为参数并返回size_t类型的哈希值。在Parallel-HashMap中，哈希器可以包含构造函数，允许在初始化时传递必要参数：

struct KeyHasher {
    // 成员变量
    uint8_t prefix;
    uint32_t k;
    uint64_t* pows;
    Buf2bit<> *seqBuf;
    
    // 默认构造函数
    KeyHasher() {}
    
    // 带参数的构造函数
    KeyHasher(Buf2bit<> *seqBuf, uint8_t prefix, uint32_t k) 
        : prefix(prefix), k(k), seqBuf(seqBuf) {
        pows = new uint64_t[prefix];
        for(uint8_t p = 0; p<prefix; ++p)
            pows[p] = (uint64_t) pow(4,p);
    }
    
    // 哈希函数
    std::size_t operator()(const Key& key) const {
        uint64_t fw = 0, rv = 0, offset = key.getKmer();
        
        for(uint8_t c = 0; c<prefix; ++c) {
            fw += seqBuf->at(offset+c) * pows[c];
            rv += (3-seqBuf->at(offset+k-1-c)) * pows[c];
        }
        return fw < rv ? fw : rv;
    }
};

键比较函数(KeyEqualTo)的实现

键比较函数用于确定两个键是否相等，特别是在哈希冲突时：

struct KeyEqualTo {
    Buf<uint8_t> *seqBuf, *seqBuf2;
    
    KeyEqualTo(Buf<uint8_t> *seqBuf = NULL, Buf<uint8_t> *seqBuf2 = NULL) 
        : seqBuf(seqBuf), seqBuf2(seqBuf2) {}
    
    bool operator()(const Key& key1, const Key& key2) const {
        uint8_t *lhs = seqBuf->seq+key1.getKmer(), *rhs = seqBuf2->seq+key2.getKmer();
        
        for(uint32_t i = 0; i<kLen; ++i) {
            if(lhs[i] != rhs[i])
                break;
            if (i == kLen-1)
                return true;
        }
        for(uint32_t i = 0; i<kLen; ++i) {
            if(lhs[i] != 3-rhs[kLen-i-1])
                return false;
        }
        return true;
    }
};

在Parallel-HashMap中使用自定义哈希器

初始化Parallel-HashMap时，可以通过构造函数传递自定义的哈希器和键比较函数：

// 直接初始化方式
phmap::parallel_hash_map<Key, Value, KeyHasher, KeyEqualTo> 
    my_map(0, KeyHasher(seqBuf, prefix, k), KeyEqualTo(seqBuf, seqBuf2));

// 动态分配方式
ParallelMap* map = new ParallelMap(0, KeyHasher(seqBuf, prefix, k), KeyEqualTo(seqBuf, prefix, k));

最佳实践和注意事项

1. 内存管理：如果哈希器内部动态分配了内存(如示例中的pows数组)，需要确保在哈希器生命周期结束时正确释放。

2. 线程安全：Parallel-HashMap设计用于并发环境，确保哈希器中的成员访问是线程安全的。

3. 性能考虑：哈希函数应该尽可能高效，因为它会在每次查找、插入和删除操作中被调用。

4. 哈希质量：良好的哈希函数应该尽可能均匀地分布键，减少冲突。

5. 构造参数：合理设计构造函数参数，确保哈希器可以获取计算哈希值所需的所有外部数据。

通过这种灵活的自定义哈希器机制，Parallel-HashMap能够适应各种复杂的键类型和哈希需求，为高性能计算场景提供了强大的支持。