C++常见的哈希算法

### C++ 中常用的哈希算法

#### 一、哈希算法概述

哈希算法是一种将任意大小的数据映射到固定大小的数据的方法。该方法具备快速计算、唯一性和固定长度的优点，但也存在哈希冲突和不可逆性的缺点[^3]。

#### 二、C++中的常见哈希算法及其特点

##### 1. **除留余数法**

这是最简单的一种哈希函数设计方式，通过取模运算来决定数据应该存放在哪个桶里：

size_t hash(int key, size_t table_size) {
    return key % table_size;
}

这种方法虽然直观易懂，但在某些情况下可能导致分布不均的问题[^1]。

##### 2. **平方取中法**

对于整型键值而言，先将其平方再从中截取出一部分作为索引也是一种有效的策略：

size_t mid_square_hash(int key, size_t table_size) {
    long square = static_cast<long>(key) * key;
    string strSquare = to_string(square);
    int start_pos = (strSquare.length() / 2) - 2;
    string substr = strSquare.substr(start_pos, 4); // 取中间四位
    return stoi(substr) % table_size;
}

此方法有助于改善因输入序列规律性强而导致的聚集现象。

##### 3. **折叠法**

当面对较长位串形式的关键字时，可采用分组求和的方式构建哈希值：

size_t folding_hash(const std::string& key, size_t table_size) {
    const char* bytes = key.c_str();
    unsigned long sum = 0;
    while (*bytes != '\0') {
        sum += *bytes++;
    }
    return sum % table_size;
}

这种方式特别适合处理字符类型的键值。

##### 4. **随机数法**

利用伪随机数生成器创建难以预测但稳定的哈希结果：

#include <random>
std::default_random_engine generator;

template<typename T>
size_t random_hash(T value, size_t table_size) {
    std::hash<T> hasher;
    auto seed = hasher(value);
    generator.seed(seed);
    uniform_int_distribution<size_t> distribution(0, table_size-1);
    return distribution(generator);
}

此类技术常用于防止恶意攻击者故意制造碰撞的情况[^2]。

#### 三、线性探测解决哈希冲突

为了应对不可避免的哈希冲突问题，在`HashTable`类模板的基础上实现了基于线性探测机制的插入操作：

bool insert(const K& key, const V& val) {
    size_t index = this->hash(key);

    while (_tables[index]._state == EXIST && _tables[index]._kv.first != key) {
        ++index %= _tables.size(); // 循环查找下一个可用槽位
    }

    if (_tables[index]._state != EXIST || _tables[index]._kv.first == key) {
        _tables[index]._kv = make_pair(key, val);
        _tables[index]._state = EXIST;
        ++_n;
        return true;
    }
    
    return false; // 表已满或其他错误条件
}

上述代码片段展示了如何在线性探查过程中找到合适的位置存放新元素，并妥善处理重复键的情形[^4]。