C++中哈希：数据定位的奇妙探索

文章标题：

C++中哈希：数据定位的深度剖析

文章内容：

文章目录

• 1.哈希的本质是什么？
• 2.哈希的常见实现途径
  • 2.1 直接定址之法
  • 2.2 除留余数之法
  • 3.哈希冲突的产生
• 4.解决哈希冲突的办法
  • 4.1 闭散列策略
  • 4.1.1 线性探测详解
    • 4.1.1.1 哈希表的基础数据架构
    • 4.1.1.2 哈希表中key的转换处理
    • 4.1.1.3 哈希表的插入操作
    • 4.1.1.4 哈希表的查找过程
    • 4.1.1.5 哈希表的删除操作
  • 4.1.2 二次探测解析
  • 4.1.3 线性与二次探测的对比
  • 4.2 开散列策略
  • 4.2.1 哈希桶机制
    • 4.2.1.1 哈希表的基本数据构成
    • 4.2.1.2 哈希表的插入流程
    • 4.2.1.3 哈希表的查找步骤
    • 4.2.1.4 哈希表的删除操作
  • 4.3 开散列与闭散列的对比

哈希是一种将任意大小的数据映射为固定长度数值（哈希值）的机制，通过哈希函数实现，其核心目标是高效地进行数据的存储、查找与验证。

1.哈希的本质是什么？

在学习哈希之前，传统的数据查找多基于顺序表、树形结构等方式。随着数据量增大，数据的随机性和容量问题愈发突出。

理想搜索模式：无需比较，直接从表中获取目标元素。若构建存储结构，使元素存储位置与关键码通过函数(hashFunc)建立一一映射，查找时可快速定位。由此诞生了平均时间复杂度近乎O(1)的数据查找方式——哈希（散列）。

2.哈希的常见实现途径

2.1 直接定址之法

对于相对集中的数据范围，可采用直接定址法。例如最大数为30、最小数为15时，创建大小为15的数组映射值。

优点：简单、分布均匀；缺点：需事先知晓关键字分布；适用场景：适用于小规模连续数据，数据分散时不适用，易致空间浪费。

2.2 除留余数之法

除留余数法通过固定哈希函数计算数据位置。设散列表地址数为m，取不大于m且最接近的质数p为除数，依哈希函数Hash(key) = key% p(p<=m)转换关键码为哈希地址。

3.哈希冲突的产生

运用除留余数法时，不同key可能除出相同余数，导致同一位置冲突，即哈希冲突（哈希碰撞）。

4.解决哈希冲突的办法

4.1 闭散列策略（开放定址法）

当哈希冲突且表未填满时，可将key存于冲突位置的下一个空位置。

4.1.1 线性探测详解

通过哈希表实现剖析线性探测：

4.1.1.1 哈希表的基础数据架构

enum STATE
{
    EXIST,
    EMPTY,
    DELETE
};

template<class K, class V>
struct HashData
{
    pair<K, V> _kv;
    STATE _state = EMPTY;
};

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
public:
    HashTable()
    {
        _table.resize(10);
    }

private:
    vector<HashData<K, V>> _table;
    size_t _n = 0; // 存储有效数据的个数
};

_kv存键值对，_state跟踪位置状态：EXIST（已占用）、EMPTY（空）、DELETE（已删除）。用状态表示清晰，避免值为零的干扰。

4.1.1.2 哈希表中key的转换处理

template<class K>
struct DefaultHashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};

template<>
struct DefaultHashFunc<string>
{
    size_t operator()(const string& str)
    {
        // BKDR
        size_t hash = 0;
        for (auto ch : str)
        {
            hash *= 131;
            hash += ch;
        }

        return hash;
    }
};

整数等走默认DefaultHashFunc，string走特化版本，避免强转问题，通过BKDR处理防冲突。

4.1.1.3 哈希表的插入操作

bool Insert(const pair<K, V>& kv)
{
    // 扩容
    if (_n * 10 / _table.size() >= 7)
    {
        size_t newSize = _table.size() * 2;
        HashTable<K, V, HashFunc> newHT;
        newHT._table.resize(newSize);

        for (size_t i = 0; i < _table.size(); i++)
        {
            if (_table[i]._state == EXIST)
            {
                newHT.Insert(_table[i]._kv);
            }
        }

        _table.swap(newHT._table);
    }

    HashFunc hf;
    size_t hashi = hf(kv.first) % _table.size();
    while (_table[hashi]._state == EXIST)
    {
        ++hashi;
        hashi %= _table.size();
    }

    _table[hashi]._kv = kv;
    _table[hashi]._state = EXIST;
    ++_n;

    return true;
}

插入时用线性探测解决冲突，负载因子0.7扩容，重新映射数据。

4.1.1.4 哈希表的查找过程

HashData<const K, V>* Find(const K& key)
{
    HashFunc hf;
    size_t hashi = hf(key) % _table.size();
    while (_table[hashi]._state != EMPTY)
    {
        if (_table[hashi]._state == EXIST
            && _table[hashi]._kv.first == key)
        {
            return (HashData<const K, V>*) & _table[hashi];
        }

        ++hashi;
        hashi %= _table.size();
    }

    return nullptr;
}

循环找空位置前的元素，避免已删除值。

4.1.1.5 哈希表的删除操作

bool Erase(const K& key)
{
    HashData<const K, V>* ret = Find(key);
    if (ret)
    {
        ret->_state = DELETE;
        --_n;

        return true;
    }

    return false;
}

修改状态删除。

4.1.2 二次探测解析

二次探测基于平方序列探测：
- 核心公式：h(i) = (h₀ + i²) % table_size（h₀为初始哈希值，i为探测次数，table_size为素数表大小）。
- 示例：table_size=7，h₀=3，探测序列为3→4→0→5→2→6→1。
- 表大小需为素数，合数会导致死循环。

4.1.3 线性与二次探测的对比

4.2 开散列策略（哈希桶）

闭散列空间利用率低，用拉链法（哈希桶）将数据挂成单链表。

4.2.1 哈希桶机制

4.2.1.1 哈希表的基本数据构成

template<class K, class V>
struct HashNode
{
    pair<K, V> _kv;
    HashNode<K, V>* _next;

    HashNode(const pair<K, V>& _kv)
        :_kv(kv)
        , _next(nullptr)
    {}
};

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
    typedef HashNode<K, V> Node;
public:
    HashTable()
    {
        _table.resize(10, nullptr);
    }

    ~HashTable()
    {
        for (size_t i = 0; i < _table.size(); i++)
        {
            Node* cur = _table[i];
            while (cur)
            {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }

            _table[i] = nullptr;
        }
    }
private:
    vector<Node*> _table; // 指针数组
    size_t _n = 0; // 存储有效数据个数
};

vector<Node*>存储指针，析构释放节点。

4.2.1.2 哈希表的插入流程

bool Insert(const pair<K, V>& kv)
{
    if (Find(kv.first))
    {
        return false;
    }

    HashFunc hf;

    if (_n == _table.size())
    {
        size_t newSize = _table.size() * 2;
        vector<Node*> newTable;
        newTable.resize(newSize, nullptr);

        for (size_t i = 0; i < _table.size(); i++)
        {
            Node* cur = _table[i];
            while (cur)
            {
                Node* next = cur->_next;

                size_t hashi = hf(cur->_kv.first) % newSize;
                cur->_next = newTable[hashi];
                newTable[hashi] = cur;

                cur = next;
            }

            _table[i] = nullptr;
        }

        _table.swap(newTable);
    }

    size_t hashi = hf(kv.first) % _table.size();
    Node* newnode = new Node(kv);
    newnode->_next = _table[hashi];
    _table[hashi] = newnode;
    ++_n;
    return true;
}

负载因子1扩容，头插挂桶。

4.2.1.3 哈希表的查找步骤

Node* Find(const K& key)
{
    HashFunc hf;
    size_t hashi = hf(key) % _table.size();
    Node* cur = _table[hashi];
    while (cur)
    {
        if (cur->_kv.first == key)
        {
            return cur;
        }

        cur = cur->_next;
    }

    return nullptr;
}

遍历桶查找。

4.2.1.4 哈希表的删除操作

bool Erase(const K& key)
{
    HashFunc hf;
    size_t hashi = hf(key) % _table.size();
    Node* prev = nullptr;
    Node* cur = _table[hashi];
    while (cur)
    {
        if (cur->_kv.first == key)
        {
            if (prev == nullptr)
            {
                _table[hashi] = cur->_next;
            }
            else
            {
                prev->_next = cur->_next;
            }

            delete cur;
            return true;
        }

        prev = cur;
        cur = cur->_next;
    }

    return false;
}

修改指针删除节点。

4.3 开散列与闭散列的对比

链地址法需增设指针，看似增加存储，但开放地址法需大量空闲空间，链地址法更节省空间。