【C++】2.7 哈希表及其实现（附代码）

用户11952558

发布于 2026-01-09 14:14:28

1010

一. 哈希表的使用

代码用法几乎与map和set一样

区别：

哈希表为单向迭代器
哈希表遍历为无序
哈希表增删查改为O(1)

同样支持multi的键值冗余

二、基本概念

哈希表本质：通过哈希函数将N个值映射到M个值中（M >= N）
直接定址法：关键字集中，不用哈希函数如：将英文字母映射成数字，记录在数组中统计字母出现个数
哈希碰撞：不同值，但是映射到相同位置
负载因子：N/M

三、哈希函数

好的哈希函数可以让N尽可能均匀分布在M中

1. 除法散列法（除留余数法）

H(key)=key%M

M应避免为某些值如2的幂，10的幂

2的幂：设m为2^k，那么余数只会为m的最低k位比特，造成大量冲突
10的幂：同理，余数位m的k位，造成冲突

2. 乘法散列法

对哈希表的大小M没有要求取k*A（0<A<1）的小数部分，再*M（按比例映射） A可以取根号5-1/2(黄金分割数)

3. 全域散列法

为防止固定的哈希函数的服务器被攻击新增两个随机数a,b

((a\*k+b)%p)%M

其中，p为较大的质数，a，b为随机整数(a为[1,p-1],b为[0,p-1)) 在任务开始前随机选取，但再映射，查找时a,b值不变

四、开放寻址法哈希表

1. 枚举状态

enum state
{
    EXIST,
    EMPTY,
    DELETE
};

为什么要有DELETE状态？ 原因：表大小为11，如果插入12（->1）,23(->1,冲突，->2) 我们删除12，如果直接将1的状态设置为empty，那我们查找23时，会找到1，发现为empty，就会返回找不到，但实际上时有23的

2. 成员，初始化

template<class K,class V>
struct hashdata
{
    std::pair<K, V> _kv;
    state _state=EMPTY;
};

template<class K, class V>
class hash
{
public:
    hash()
        :_tables(23)
        ,_n(0)
    { }
private:
    std::vector<hashdata<K, V>> _tables;
    size_t _n;
};

3. 插入

bool insert(const std::pair<K,V>& kv)
{
    size_t hash0 = kv.first % _tables.size();
    size_t hashi = hash0;
    size_t i = 1;
    int flag = 1;
    while (_tables[hashi]._state == EXIST)
    {
        hashi = (hash0 + i) % _tables.size();
        ++i;
    }
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_n;
    return true;
}

当位置存在时，就一直找，找到不为存在时就插入

(1) 二次探测：由于直接这么探测，要是数据堆积那么效率较低因此，可以将+i改成+-i方，让数据更加分散其它都一样，将hash0 + i改为hash+i*i即可

(2) 双重散列法 由于二次探测在冲突时+-的值时一样的，依旧不能解决堆积问题因此，可以再用一个独立的函数去计算+-的值要求：函数值<M且与M互质（否则就是在原地几个数中踏步）

4. 扩容

将原来的vector拷贝到新的更大的vector 但是由于size不一样，开放寻址的_tables.size()爷不一样，因此需要重新建立关系并且，不是满了扩容，而是当负载超过一定数时就扩容

if (_n * 100 / _tables.size() >= 70)
{
    hash<K, V> newhash;
    newhash._tables.resize(2 * _tables.size());
    for (auto& e : _tables)
    {
        if (e._state == EXIST)
        {
            newhash.insert(e._kv);
        }
    }
    _tables.swap(newhash._tables);
}

可以参考现代写法，建一个新的哈希表类，再复用插入逻辑，再交换两个vector

5. 质数处理

2 * _tables.size()由于新哈希表的大小为两倍以前的，因此一定不是质数解决方案：弄一个质数数组，达到负载就取新的值

newhash._tables.resize(prim(_tables.size()+1));

写了个二分查找，找到最小的大于s的数

inline size_t prim(size_t s)
{
    static const size_t prime_list[] =
    {
        53, 97, 193, 389, 769,
        1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433,
        1572869, 3145739, 6291469, 12582917, 25165843,
        50331653, 100663319, 201326611, 402653189, 805306457,
        1610612741, 3221225473, 4294967291
    };
    const size_t n = sizeof(prime_list) / sizeof(prime_list[0]);
    size_t left = 0, right = n;
    while (left < right)
    {
        size_t mid = left + (right - left) / 2;
        if (prime_list[mid] < s)
            left = mid + 1;
        else
            right = mid;
    }
    if (left < n)
        return prime_list[left];
    return prime_list[n - 1];
}

6. Find

hashdata<K, V>* Find(const K& key)
{
    size_t hash0 = key % _tables.size();
    size_t hashi = hash0;
    size_t i = 1;
    while (_tables[hashi]._state != EMPTY)
    {
        if (_tables[hashi]._state == EXIST
            && _tables[hashi]._kv.first == key)
        {
            return &_tables[hashi];
        }
        hashi = (hash0 + i) % _tables.size();
        ++i;
    }
    return nullptr;
}

7. 转无符号整型

由于上面写的代码仅仅是针对于无符号整型的但是其它的可以用仿函数的方式转

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

template<>
struct hashfunc<std::string>
{
    size_t operator()(const std::string& str)
    {
        size_t hash = 0;
        for (auto&e:str)
        {
            hash += e;
            hash *= 131;
        }
        return hash;
    }
};

在内置类型，如double等可以直接强转但是，string也可能出现在哈希表中，因此对模板进行特化，优先走特化函数因此，哈希表要转2次，传值->无符号整型->哈希函数映射哈希值

BKDR哈希 String如何转无符号整型如果将每一位简单相加，那么很容易冲突因此，可以加一位再乘一个质数（选择131）以减少冲突

8. 自定义类和哈希函数

struct date
{
    int _year; int _month; int _day;
    date(int year=1,int month=1,int day=1)
        :_year(year)
        ,_month(month)
        ,_day(day)
    { }
    bool operator == (const date & d)
    {
        return _year == d._year && _month == d._month && _day == d._day;
    }
};

struct cmp
{
    size_t operator()(const date& d) const
    {
        size_t has = 0;
        has += d._year; has *= 10000;
        has += d._month; has *= 100;
        has += d._day;
        return has;
    }
};

因此，哈希表做key的要求：能转为整型，可以有不等于的比较

五、链地址法实现

由于开放寻址法无论怎么探测都无法解决过多数据堆积问题

因此，将哈希表数组中存放链表将冲突的值挂下来这个放地址的东西就叫桶

1. 节点定义

struct hashnode
{
    std::pair<K, V> _kv;
    hashnode* _next;
    hashnode(const std::pair<K,V>&kv)
        :_kv(kv)
        ,_next(nullptr)
    { }
};

为什么单链表：单链表对于哈希表已经足够了，还可节省空间
为什么不用list或forward_list 因为在扩容时，用std的list会自动析构，但是我们其实可以回收利用原先的节点，节省开销

2. 插入加扩容

bool insert(const std::pair<K, V>& kv)
{
    hash ha;
    if (_n * 100 / _tab.size() >= 70)
    {
        hashtab<K, V, hash> newhash;
        newhash._tab.resize(prim(_tab.size() + 1));
        for (int i = 0; i < _tab.size(); i++)
        {
            node* cur = _tab[i];
            while (cur)
            {
                node* next = cur->_next;
                size_t has = ha(cur->_kv.first) % newhash._tab.size();
                cur->_next = _tab[has];
                _tab[has] = cur;
                cur = next;
            }
            _tab[i] = nullptr;
        }
        _tab.swap(newhash._tab);
    }
    size_t has = ha(kv.first) % _tab.size();
    node* newnode = new node(kv);
    newnode->_next = _tab[has];
    _tab[has] = newnode;
    ++_n;
    return 1;
}

由于链地址法没有那么害怕哈希冲突，因此可以忍受较高的负载因子甚至可以满了再扩容但是，由于需要回收利用原先的节点，因此就不能让扩容直接复用插入了，否则会浪费插入节点选择头插

3. 查询和删除

Iterator Find(const K& key)
{
    KofT kot;
    hash _hash;
    size_t hashi = _hash(key) % _tab.size();
    node* cur = _tab[hashi];
    while (cur)
    {
        if (kot(cur->_data) == key)
        {
            return Iterator(cur, this);
        }
        cur = cur->_next;
    }
    return End();
}

bool Erase(const K& key)
{
    KofT kot;
    size_t hashi = key % _tab.size();
    node* prev = nullptr;
    node* cur = _tab[hashi];
    while (cur)
    {
        if (kot(cur->_data) == key)
        {
            if (prev == nullptr)
            {
                // 头结点
                _tab[hashi] = cur->_next;
            }
            else
            {
                // 中间节点
                prev->_next = cur->_next;
            }
            delete cur;
            --_n;
            return true;
        }
        else
        {
            prev = cur;
            cur = cur->_next;
        }
    }
    return false;
}

用哈希函数找到桶的地址，再头插到对应地点查询返回迭代器和bool类型的pair值

六、哈希表其它接口

rehash 由于哈希表扩容的代价非常大，因此在开始前先预留好桶的大小 Reserve也是同理但是reserve会预留冗余值
bucket_count和bucket_size bucket_count:桶的数量 bucket_size：第n个桶有多少个元素
load_factor 当前负载因子大小 max_load_factor 修改最大负载因子

七、封装和模拟实现

1. 迭代器成员声明

template<class K,class T,class ref,class ptr,class KofT,class hash>
struct uniterator
{
    typedef hashtab<K, T, KofT, hash> utb;
    typedef uniterator<K, T, ref, ptr, KofT, hash> self;
    typedef unordered_node<T> node;
    node* _node;
    const utb* _utb;
    uniterator(node* __node, const utb* __utb)
        :_node(__node)
        ,_utb(__utb)
    { }
};

(1) 模板的作用 由于需要普通迭代器和const迭代器因此模板需要ref和ptr参数，并且由于需要算哈希函数，因此需要仿函数KofT取出class T的T中的key 此外，在遍历时需要计算出从哪里开始，需要哈希函数需要桶的指针，因此需要K和T

(2) 通指针要用const 因为调用const迭代器时为了值不被修改，因此这么声明

ConstIterator Begin() const

Const表示this指针指向对象为const，因此构造函数传也需要为const，否则权限放大

2. 迭代器成员函数

ref operator*()
{
    return _node->_data;
}

ptr operator->()
{
    return &(_node->_data);
}

bool operator!=(const self& s)
{
    return _node != s._node;
}

3. 迭代器++

self& operator++()
{
    if (_node->_next)
    {
        _node = _node->_next;
    }
    else
    {
        KofT kot;
        hash ha;
        size_t hashi = ha(kot(_node->_data)) % _utb->_tab.size();
        ++hashi;
        while (hashi < _utb->_tab.size())
        {
            _node = _utb->_tab[hashi];
            if (_node)
                break;
            else
                ++hashi;
        }
        // 所有桶都走完了，end()给的空标识的_node
        if (hashi == _utb->_tab.size())
        {
            _node = nullptr;
        }
    }
    return *this;
}

当前链表后一位依旧有数：到下一个节点
后一位没有数：到桶的下一位有链表节点的地方

4. 封装

Map:

template<class K,class V,class hash= hashfunc<K>>
class unorderedmap
{
    struct KofT
    {
        const K& operator()(const std::pair<K, V>& kv)
        {
            return kv.first;
        }
    };
    typedef typename hashtab<K, std::pair<const K, V>, KofT, hash>::Iterator iterator;
    typedef typename hashtab<K, std::pair<const K, V>, KofT, hash>::ConstIterator const_iterator;
public:
    iterator begin()
    {
        return _ht.Begin();
    }
    iterator end()
    {
        return _ht.End();
    }
    const_iterator begin() const
    {
        return _ht.Begin();
    }
    const_iterator end() const
    {
        return _ht.End();
    }
    std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
    {
        return _ht.Insert(kv);
    }
    V& operator[](const K& k)
    {
        std::pair<iterator, bool> ret = insert({ k,V() });
        return ret.first->second;
    }
    iterator Find(const K& key)
    {
        return _ht.Find(key);
    }
    bool Erase(const K& key)
    {
        return _ht.Erase(key);
    }
private:
    hashtab<K, std::pair<const K, V>, KofT, hash> _ht;
};

Set:

template<class K, class hash = hashfunc<K>>
class unorderedset
{
    struct KofT
    {
        const K& operator()(const K& k) const
        {
            return k;
        }
    };
    typedef typename hashtab<K, K, KofT, hash>::Iterator iterator;
    typedef typename hashtab<K, K, KofT, hash>::ConstIterator const_iterator;
public:
    iterator begin()
    {
        return _ht.Begin();
    }
    iterator end()
    {
        return _ht.End();
    }
    const_iterator begin() const
    {
        return _ht.Begin();
    }
    const_iterator end() const
    {
        return _ht.End();
    }
    std::pair<iterator, bool> insert(const K& k)
    {
        return _ht.Insert(k);
    }
    K& operator[](const K& k)
    {
        std::pair<iterator, bool> ret = insert(k);
        return ret.first;
    }
    iterator Find(const K& key)
    {
        return _ht.Find(key);
    }
    bool Erase(const K& key)
    {
        return _ht.Erase(key);
    }
private:
    hashtab<K, K, KofT, hash> _ht;
};

和map，set类似，需要key，data（map为<K,V>,set为K）同样需要传keyoft用来取出key值

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3vtuwevgbfms4

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2026-01-08，如有侵权请联系 cloudcommunity@tencent.com 删除

return